☰

有向グラフ内のどのサイクル検出が O(n^2) よりも効率的ですか? [closed] 質問する

tag-icon • tag-icon algorithm graph-theory directed-graph
有向グラフ内のどのサイクル検出が O(n^2) よりも効率的ですか? [closed] 質問する

有向グラフ内のサイクルを検出するのに O(n^2) よりも時間効率の良いアルゴリズムはありますか?

実行する必要のあるジョブのスケジュールを表す有向グラフがあり、ジョブがノード、依存関係がエッジです。このグラフ内のサイクルが循環依存関係につながるエラーケースを検出する必要があります。

ベストアンサー1

Tarjan の強連結成分アルゴリズムO(|E| + |V|)時間計算量があります。

その他のアルゴリズムについては、強く連結されたコンポーネントWikipediaで。

おすすめ記事