次のリンクのコードを読んでいましたhttp://www.cosc.canterbury.ac.nz/tad.takaoka/alg/graphalg/sc.txt 「低リンク」という言葉にぶつかり続けましたが、それが何を意味するのか考えてください。これはかなり初心者の質問であることは知っていますが、誰かが私に説明してもらえますか? ありがとう。
質問する
2582 次
1 に答える
7
リンクされた記事で述べたように：
このアルゴリズムは、頂点が初めて訪問されたときの訪問番号と同じ値が最初に割り当てられる低リンク番号も維持します。
言い換えれば、低リンク値は、最初の DFS 中にノードが持つ番号と最初は等しくなります。最初に訪問したノードの場合、値は 0 になります。2 番目のノードの場合、値は 1 になります。3 番目のノードの値は 2、4 番目のノードの値は 3 などです。
そこから、特定のノードがたまたまどの SCC にあるかを追跡するために、低リンク値が更新されます。最初は各ノードが独自の SCC にあると見なしますが、2 つの異なるノードが同じ SCC で、これらすべてのノードの低リンク値を更新して、それらがすべて同じになるようにします。
お役に立てれば！
于 2012-06-28T22:55:05.637 に答える