[解決済み】有向グラフのサイクルを検出する最適なアルゴリズム【クローズド

質問

有向グラフ内のサイクルを検出する効率的なアルゴリズムはあるか？

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

どのように解決するのですか？

タージャンの強連結成分アルゴリズム があります。 O(|E| + |V|) の時間複雑性を持つ。

その他のアルゴリズムについては 強連結成分 をWikipediaに掲載しています。