問題タブ [tarjans-algorithm]

Tarjan の強連結成分アルゴリズムは、グラフ内にある基本的なサイクルまたはすべてのサイクルのみを見つけることができますか?

Matlab を使用した tarjan プログラムのこのコード ソースがあります。このエラーは、プログラムを実行すると表示されます。どうすれば修正できますか

問題は星の間のccにあります

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

http://en.algoritmy.net/article/44220/Tarjans-algorithm

強く接続されたコンポーネントに対する Tarjan のアルゴリズムの私の Ruby バージョンでは、このバグを理解できません。Kosaraju-Sharir アルゴリズムが動作するようになり、Ruby の Tarjan アルゴリズムがいくつかのグラフで動作します。しかし、接続されるべき2つのコンポーネントが接続されていません---「10」と「11、12、9」

入力ファイルはこの有向グラフです: http://algs4.cs.princeton.edu/42directed/tinyDG.txt

単一のコンポーネントを作成しようとするこの最後のループでは、「10」(スタックの最後のアイテム) から始まりますが、現在の頂点 (「親」) も「10」です! これにより、ループが別のコンポーネントとして「10」を切り捨てられます。スタックの最新のアイテムが親ノードと同じなのはなぜですか? ["12"、"11"、"9"、そして "10"] を収集した後、コンポーネントの END にのみ "10" が表示されることを期待します。「10」が最後ではなく最初に表示されるため、この問題が発生します。どうすれば修正できますか？

私のRubyコード:

Tarjan のアルゴリズムを使用して強連結成分の実装に取り​​組んでいます。ノードとエッジのリンクされたリストとして入力を与えています。ただし、gcc コンパイラは、再帰関数で毎回セグメンテーション違反を発生させます (while ループで、頂点の隣接ノードをチェックしています)。

このコードの何が問題なのか分かりますか?

解析ツリーの属性の循環依存関係のコンテキストで次の行に出くわしたとき、「コンパイラ: Aho、Ullman、Sethi、および Lam による Principles, Techniques and Tools」から Syntax Directed Definition を研究していました。

特定の SDD が変換しなければならない解析ツリーのいずれかに循環性が存在するかどうかを判断することは、計算上困難です。(セクション: 5.1.2)

http://cs.nyu.edu/courses/fall12/CSCI-GA.2130-001/lecture8.pdfにも記載されています

サイクルの検出には指数関数的な時間の複雑さがあります

しかし、O(E+V) のサイクルを見つけることができる Tarjan の強連結成分アルゴリズムがあります。では、なぜ上記の情報源はこれと矛盾しているのでしょうか?

私が欠けているものを誰か教えてもらえますか？

この質問は関連していますが、最近質問されたものと同じではありませんhere .

ウィキペディアの疑似コードを読んだところです。

2 つの非常に基本的な質問があるため、明らかに適切に理解していなかったに違いありません。

1. と言うときif (w is in S)、要素はインデックスによって順序付けられるため、この操作は O(N) または少なくとも O(logN) の複雑さではありませんか? ルート ノードからアクセスできる新しいノードごとにこれを実行する必要があるため、全体的な複雑さはありませんO(NlogN)。さらに、S はスタックであるため、概念的には最上位の要素のみにアクセスできる必要があります。その中で検索を実装するにはどうすればよいでしょうか? ここでは、二分探索木の方が優れたデータ構造であるべきではありませんか?

2. この部分では:

   そうでなければ (w は S にある) then
   v.lowlink := min(v.lowlink, w.index)

w.indexand notを使用する特定の理由はありw.lowlinkますか? 使用する利点はw.lowlink、前の質問 (リンクされた質問) に回答できることです。SCC 内のLLsすべてのノードの は、すべてのノードで同じであることが保証されます。

有向グラフの各頂点に、外向きのパス (同じ頂点を指すことができる) が正確に 4 つあるという特定の問題があります。

最初は開始頂点しかなく、DFS を使用してすべての頂点とエッジを検出/列挙します。

その後、Tarjan のアルゴのようなものを使用して、グラフを強く接続されたコンポーネントに分割できます。

私の質問は、グラフを発見してからアルゴリズムを適用するよりも効率的な方法があるかどうかです。たとえば、2 つの部分を組み合わせてより効率的にする方法はありますか?