确定有向图是否单独连接的最有效方法是什么？

Question

我正在进行一项任务,其中一个问题要求导出一个算法,以检查有向图G =(V,E)是否是单独连接的(对于所有不同的顶点u,最多有一条从u到v的简单路径, v的v

当然你可以蛮力检查它,这就是我现在正在做的事情,但我想知道是否有更有效的方法.有人能指出我正确的方向吗？

Answer 1

这个问题有一个更好的答案.你可以在O(| V | ^ 2)中做到这一点.通过更多努力,您可以在线性时间内完成.

首先,在每个强组件中找到G.的强连接组件,搜索以查找这种情况:1)如果此组件中存在前沿,则它不是单独连接的,2)如果此组件中存在交叉边缘它不是单独连接的,3)如果树的顶端至少有两个后边缘u,对于u的正确祖先,则它不是单独连接的.

这可以在O(E)中完成.(我认为除了案例3.我无法很好地实现它!).

如果上述情况均未发生,则应检查G ^ SCC上是否存在交叉边缘或前沿(图G,强组件替换为单个节点),因为我们没有后备,可以通过在O(| V | ^ 2)中对该图的每个顶点重复dfs.

Answer 2

你尝试过DFS吗？

Run DFS for every vertex in the graph as source
    If a visited vertex is encountered again, the graph is not singly connected
repeat for every unvisited vertex.
The graph is singly connected.

复杂度 O(v^2), o(v) dfs 不重复。