問題タブ [tarjans-algorithm]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - 再帰的アルゴリズムの反復バージョンは低速です
Tarjanの強連結成分（SCC）の反復バージョンを実装しようとしています。これは、便宜上ここに複製されています（出典： http： //en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm）。
私の反復バージョンは、次のノード構造体を使用しています。
反復バージョンで行ったことは次のとおりです。
私の反復バージョンが実行され、再帰バージョンと同じ出力が得られます。問題は、反復バージョンが遅いことです。理由はわかりません。誰かが私の実装についての洞察を私に与えることができますか？再帰的アルゴリズムを繰り返し実装するためのより良い方法はありますか？
python - Python での Tarjan の強連結成分アルゴリズムが機能しない
ウィキペディアによると、Tarjan の強連結成分アルゴリズムを Python で実装しましたが、うまくいきません。アルゴリズムは非常に短く、違いを見つけることができないため、なぜ機能しないのかわかりません。元の紙を調べてみましたが、見つかりませんでした。
これがコードです。
必要に応じて、グラフを視覚的に確認できます。ご覧のとおり、これはウィキペディアの疑似コードをかなり前向きに翻訳したものです。ただし、これは出力です。
強連結成分は 3 つではなく、1 つだけにする必要があります。質問がすべての面で正しいことを願っています。そうでない場合は申し訳ありません。いずれにせよ、ありがとうございました。
c# - タージャン サイクル検出ヘルプ C#
これは、tarjan のサイクル検出の実用的な C# 実装です。
アルゴリズムはここにあります: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
DepGraph は単なる Vertex のリストであることに注意してください。Vertex には、エッジを表す他の Vertex のリストがあります。また、index と lowlink は -1 に初期化されます
編集:これは機能しています...結果を誤解しただけです。
java - Tarjan アルゴリズムの Java 実装を実行しようとしています
wikipediaから Tarjan Java 実装を実行しようとしています。私の最終的な目標は、特定のポイントにいくつかの println を挿入することです。これにより、コードをさらに理解できるようになります。
私はこれまで何をしてきたか
- これら3つのソースコードをコピーして貼り付けました
a) Tarjan ソース コード b) Edge ソース コード c) Node ソース コード j は、同じフォルダー内の 3 つの個別のファイルにあります。
- helloworld の例を実行することができました (残念ながら、私の Java のバックグラウンドはほとんどゼロです。最後に Java をコーディングしたのは、何年も前の宿題でした)。
私が直面している具体的な問題は何ですか? 3つのエラーが発生します:
対応する行: 9、28、14 はこれらです
追加の説明 は、これが実際のエラーなのか、それとも何か間違っているのかがわからないため、取得したエラーの種類をタイトルとして付けませんでした。ファイルを含める必要があるかもしれません知る）。コードが既にあるので、実行するのが簡単であることを期待して、これを投稿しています。
よろしくお願いします！
graph - Tarjan のアルゴリズムを学ぶにはどうすればよいですか?
ウィキペディアから 3 時間かけてタージャンのアルゴリズムを学ぼうとしてきましたが、頭も尻尾もわかりません。:(
http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1
なぜ DFS ツリーのサブツリーなのですか? (実際、DFS はフォレストを生成しますか? o_O) そして、なぜそれがルートであるv.lowlink=v.indexことを意味するのでしょうか?v
誰かが私にこれを説明してくれますか/このアルゴリズムの背後にある直感や動機を教えてください。
algorithm - Tarjan の SCC アルゴリズムでローリンクとはどういう意味ですか?
次のリンクのコードを読んでいましたhttp://www.cosc.canterbury.ac.nz/tad.takaoka/alg/graphalg/sc.txt 「低リンク」という言葉にぶつかり続けましたが、それが何を意味するのか考えてください。これはかなり初心者の質問であることは知っていますが、誰かが私に説明してもらえますか? ありがとう。
algorithm - Tarjan のアルゴリズムにおけるクロスリンク
scc に関する Tarjan の論文を読んでいます。
この論文では、特定の頂点のローリンクは次のように定義されています。
LOWLINK (v) は、v と同じコンポーネント内にある最小の頂点であり、0 個以上のツリー アークとそれに続く多くても 1 つのリーフまたはクロス リンクをトラバースすることによって到達できます。
特定の scc 内の 2 つの頂点からクロス リンク エッジを経由するパスの状況を思いつくことはできません。これは、scc 全体が dfs 検索によって派生した 1 つのツリー内にある必要があるためです。誰かがこれを少し説明できますか？