0

有向グラフGで強連結成分を見つけるには、最初にシンクノードを見つける必要があります。シンクノードを見つけるために、DFSはGの逆グラフで実行されます-それをHと呼びましょう。次に、ポスト番号が最も高いノード（ノードをマークした時間）がHのソースノードになり、したがってシンクノードになります。 Gで、Gのシンクノードを効果的に識別できるようにします。

これらすべてを行う代わりに、Gで投稿番号が最も小さいノードを使用してみませんか？ソースノードのグラフでポスト番号が最も高い頂点が、ポスト番号が最も小さい頂点がシンクノードであるということにはなりませんか？逆にソースノードを見つけることで物事を複雑にしすぎるのはなぜですか？Gのポスト番号が最も小さい頂点をシンクノードとして使用しないのはなぜですか？

4

1 に答える 1

1

流しではないかもしれません。たとえば、グラフのsからのDFSの場合

s->a
^  |
|  v
c<-b
   |
   v
   d

トラバーサルは

enter(s)
enter(a)
enter(b)
enter(c)
leave(c)
enter(d)
leave(d)
leave(b)
leave(a)
leave(s)

したがって、cの投稿番号は最小ですが、シンクではありません。

于 2012-06-18T13:56:32.507 に答える