algorithm - 如何检测有向图是否是唯一连通的？

Question

如果每对顶点之间恰好存在一条路径，则称有向图是唯一连通的。如何识别图是否具有此属性？这需要按顺序完成O(n+m)，其中n是图的顶点数，m是边。

很明显，图中不应该有任何交叉边或前边。但是后边呢？

Answer 1

如果每一对节点之间恰好有一条有向路径，则

• 每个节点必须至少有一个出边（否则没有从该节点到其他节点的路径）
• 没有一个节点可以有多个出边（如果有一条从 X 到 Y 的边和一条从 X 到 Z 的边，并且有从 Y 到 T 和从 Z 到 T 的路径，那么从 X 有多个路径到 T)

但是现在，每个节点都有一个出边，并且每个节点都可以从其他节点到达，所以图必须是一个有向循环。

在 O(n) 时间内检查是微不足道的。

编辑：正如 Erik P 在评论中指出的那样，此论点仅适用于所讨论的路径是简单路径的情况。同样，大小为 3 的图可能需要特殊处理，因为上面的 XYZT 推理不适用，这意味着图的节点 X、Y、Z 以及从 X 到 Y 和 Z 以及从 Y 和 Z 的边到 X 是合法的。