3

根据 CLRS 第 3 版中可用的定义,单连通有向图是这样一种图,其中对于每一对顶点 (u,v),从 u->v 至多有 1 条唯一路径。现在我读过的大多数答案都表明我们从图中的每个顶点运行 DFS,如果在任何情况下我们找到Cross edgeForward edge,那么图不是单连接的。我可以理解前向边的概念,但是在这张图上运行这个算法

1 --> 2 <-- 3 会给我们的结果是它不是单连接的,而这个图是单连接的。我们有一个从 3 -> 2 或 1 -> 2 的交叉边,这取决于哪个顶点开始了整个过程(1 或 3)。如果我们从顶点 2 开始 DFS,那么我们有 2 个交叉边 1 -> 2 和 3 -> 2。有人可以澄清一下吗?

4

1 回答 1

1

建议从每个节点运行 DFS 的答案意味着一旦无法继续(没有离开的传出边)就应该停止 DFS,而不是从不同的节点开始。

在这种情况下,在您的示例中,您将从 1 开始 (wlo),发现 2,然后就完成了。没有后边
接下来,是一个全新的 DFS,从 3 开始,发现 2,然后完成,再次没有后边。

这个想法基本上是通过定义来验证属性。您从每个节点执行 DFS,u直到您发现每个节点v最多有一个路径 from uto v(DFS 已用尽),或者您在某个点找到第二条路径 from uto v,然后您就完成了。

于 2014-11-24T08:06:42.117 回答