これは、データ構造とアルゴリズム解析の第3版の質問です。これは私たちの試験でも尋ねられました。 隣接リストによって表されるグラフを位相トポロジでソートするアルゴリズムを書き留め、アルゴリズムが見つかった場合にそのアルゴリズムがサイクルを出力するように修正されます（ ）。まず、あなたの考えをいくつかの文で説明してください。 文。 （深さ優先探索を使用しないでください、私たちは、基本的なトポロジカル 一種のちょうど変更をしたい。）トポロジカルソートによるサイクルの印刷（検出しない）
そして答えは： 何の頂点が入次数0を持っていない場合は、私たちが持つ頂点を逆方向にトレースすることにより、サイクルを見つけることができます 正の確度;トレースバックの各頂点は正の実数を持つので、最終的には 頂点に2回到達し、サイクルが見つかった。
私はバックトレース部分を理解していませんでした。「トレースバック」とはどういう意味ですか、この回答の擬似コードはどのようになりますか？助けをお待ちしています。
Kahnsアルゴリズムは、確度0のノードを選択し、そのすべての出て行くエッジを除去することによって作用する（これは、0度の新しいノードを生成する可能性がある）。 0以上のノードが見つからない場合（グラフは現在空ではない）、サイクルを含んでいます。
サイクルを印刷するには、任意の場所から開始し、受信エッジに従います。有限の数のノードがあるので、ある時点で2回目にノードに到達する必要があります。これはあなたのサイクルです。それを印刷し、もう一度実行してください。
私たちのグラフがあると言う：このグラフの
a --> b
b --> c, d
c --> b
反転は、その後
a <--
b <-- a, c
c <-- b
d <-- b
トポロジカルソートがaで開始し、それを削除します。 bは現在b <-- c
となりました。ここでは、dのように開始し、後方に検索します。
d <-- b <-- c <-- b
これまでにbを見てきたので、それはサイクルの一部でなければなりません。印刷するには、再度リンクをたどり、b <-- c <-- bを取得します。
デッドエンドがある場合（aなど）、サイクルを検出する前にすでにトポロジカルソートアルゴリズムによって削除されていました。