問題タブ [tarjans-algorithm]

1972 年 9 月の彼の研究論文「有向グラフの基本回路の列挙」で発表されたタージャンのアルゴリズムを使用して、有向グラフのサイクルを決定しようとしています。

Python を使用してアルゴリズムをコーディングし、隣接リストを使用してノード間の関係を追跡しています。

したがって、以下の「G」では、ノード 0 はノード 1 を指し、ノード 1 はノード 4、6、7 を指します... などです。

Tarjan のアルゴリズムは、次のサイクルを検出します。

[2、4]

[2, 4, 3, 6, 5]

[2, 4, 3, 7, 5]

[2、6、5]

[2, 6, 5, 3, 4]

[2、7、5]

[2、7、5、3、4]

[3、7、5]

Tiernanのアルゴリズムも実行しましたが、（正しく）2つの余分なサイクルが見つかりました：

[3,4]

[3,6,5]

Tarjan がこれらの 2 サイクルをスキップする理由を見つけるための助けをいただければ幸いです。おそらく私のコードの問題ですか？

有向グラフですべての基本回路を見つけるための Donal B.Johnson の論文を読んでいました。

この論文で彼は、Tarjan アルゴリズムの最悪のケースは O(V*E (c+1)) であると述べましたが、他の場所では O(V+E) として示されていますが、Johnson の論文はその点を証明するためにいくつかの例を取り上げています。紙の上の図1と図2。

図 2 の例はかなり似ています。O(k) 時間で最初のサイクル 1...k を見つけた後、インデックスが既に定義されているため、他のすべての頂点は単純に返され、さらに k 時間かかるはずです。 k個の頂点なので、それを合計するには、 k**2 ではなく 2k 回にする必要があります。ここでいくつかの点が欠けていますか?

いくつかの例を提案してください、ありがとう

私は強結合成分に対する Tarjan のアルゴリズムを研究していますが、その仕組みは明らかです。とにかく、私が理解できない行があります：

アスタリスクで線をマークしました。バックエッジに遭遇したときにノードの発見インデックス/時間を取得する必要があるのはなぜですか

コンポーネントの値を取得するだけでなく、

これが問題になるケースは考えられません。

誰か教えてください。編集:これは単なるセマンティック要件であると思われます。つまり、 lowlink は、1 つの back-edge のみを持つノードから到達可能な最古の祖先として定義されていますが、これは単なる推測です。

任意のグラフで tarjans アルゴリズムを実行すると、次のグラフのように常にサイクルがあると主張されます。

A -> B -> C

アルゴリズムは、サイクルがあることを教えてくれます。

たとえば、次のようなサイクルがある場合:

A -> B -> C -> A

出力は非常に奇妙です:

これが私の実装です：

しかし、どこが間違っているのかわかりません。私はほぼ1:1のtarjansアルゴリズムと疑似コードに関するウィキペディアの記事に従いました。私はグラフ理論とグラフアルゴリズムに非常に慣れていないので、ここで何が間違いなのか頭を悩ませることはできません。

tarjan() の修正