java - 单连通有向图

Question

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

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

Answer 1

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

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

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