java - 单连通有向图

Question

根据 CLRS 第 3 版中的定义，单连通有向图是指对于每对顶点 (u,v)，从 u->v 至多有一条唯一路径的图。现在我读过的大部分答案都表明我们从图中的每个顶点运行 DFS，如果在任何情况下我们都找到了交叉边或前向边，则该图不是单连通的。我可以理解前向边缘的概念，但在此图上运行此算法

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

Answer 1

建议从每个节点运行 DFS 的答案意味着您应该在无法继续(没有离开边缘)时停止 DFS，而不是从不同的节点开始。

在这种情况下，在您的示例中，您将从 (w.l.o) 1 开始，发现 2，然后您就完成了。没有后边缘
接下来，是一个全新的DFS，从3开始，发现2，然后完成，同样没有后缘。

这个想法基本上是通过定义来验证属性。您从每个节点 u 执行 DFS，直到您发现对于每个 v 最多只有一条从 u 到 v 的路径(DFS 耗尽)或者你在某个时候找到了从 u 到 v 的第二条路径，然后你就完成了。