重複の可能性：
有向グラフでサイクルを検出するための最良のアルゴリズム
これは、有向グラフがダグであるかどうかをチェックするアルゴリズムを設計する宿題です。
私が考えることができるより良いアルゴリズムは次のとおりです：
ステップ1：出力エッジのみを持つノードを見つけます。そのようなノードがない場合、これらはサイクルです
ステップ2：そのノードでDFSを開始します。各エッジをトラバースし、エッジがすでにスタック上にあるノードを指しているかどうかを確認します。そのようなエッジが見つからない場合、その連結成分にサイクルはありません。
しかし、私を混乱させるのは、グラフが隣接行列として表され、隣接がリンクされている場合の時間計算量です。
隣接行列の場合はO（V ^ 2）、リンクリストの場合はO（V + E）にする必要がありますか？
そしてもう1つの質問は、グラフがダグの場合はトポロジカル順序を出力し、そうでない場合は円を出力するpesdooコードを作成する方法です。