0

要在有向图 G 中找到强连通分量，首先需要找到一个汇节点。为了找到 sink 节点，DFS 在 G 的逆向图上运行，我们称之为 H。然后具有最高post 编号的节点（标记节点离开的时间）将是 H 中的源节点，因此是 sink 节点在 G 中，使我们能够有效地识别 G 中的汇节点。

与其做所有这些，为什么不简单地使用 G 中帖子编号最低的节点呢？如果在源节点中的图中具有最高职位编号的顶点，是否意味着具有最低职位编号的顶点是汇节点？为什么要通过反向查找源节点来使事情变得过于复杂？为什么不直接使用 G 中 post 编号最小的顶点作为 sink 节点呢？

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 回答