問題タブ [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.
algorithm - Tarjanアルゴリズムでインデックス配列を1つだけ使用できますか?
Tarjan アルゴリズムには 2 つのインデックス配列があり、1 つは発見された順序でノードに連続番号を付けます。もう 1 つは、v から v のサブツリーを介して到達可能な最小のインデックスを表します。これは、アルゴリズムの擬似コードです。
しかし、低い配列は削除できると思います。アルゴリズムは次のように変更されます
小さなグラフでいくつかのテストを行いましたが、結果は標準の tarjan と同じです。しかし、すべての種類のグラフで強連結成分をうまく見つけることができるかどうかはわかりません。このアルゴリズムは正しいか、弱いテストケースしかパスできません。
data-structures - Tarjan Algorithm 、バックエッジの場合、ロータイムではなくディスカバリータイムを取っているのはなぜですか?
eq2: low[a] = min(low[a],low[b]) の代わりに eq1: low[a]=min(low[a],discovery[b]) と言う理由を誰でも説明できますか? a から b へのバックエッジがある場合
私は多くのケースを試しましたが、すべてのケースで eq2 は tarjan アルゴリズムで正常に動作します
eq1 と eq2 の動作が異なる例が存在する場合は、回答で言及してください