根据 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。有人可以澄清一下吗?