有向グラフですべての基本回路を見つけるための 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 のアルゴリズム」は、強連結成分のアルゴリズムではありません。それは彼の基本回路を列挙するためのアルゴリズムです。ただし、元の論文では、この方法は最悪の場合の O((V + E) * (C + 1)) 時間がタイトであると記載されています。Tarjan がこの境界 (2 つの回路を見つける間の O(V + E) 時間) を証明するために使用する引数が、Johnson の論文 (2 つの回路を見つける間の O(V * E) 時間) で突然変更されていることに注意してください。私はこれらのアルゴリズムのどちらにも詳しくないので、どちらが正しいとは言えません。簡単な検索では、Johnson のアルゴリズムの方が漸近的に高速であると見なされているようですが (両方の方法が同じ時間の複雑さを主張しているにもかかわらず)、Tarjan の論文で時間の複雑さを反証する情報源はどこにも見つかりませんでした。