我正在完成一项任务，其中一个问题要求推导出一种算法来检查有向图G=(V,E)是否为单连通（对于所有不同的顶点u,v，从u到v最多只有一条简单路径）。
当然，您可以采用暴力方式进行检查，这也是我目前正在做的事情，但我想知道是否有更有效的方法。有谁能指点我一下吗？
6个回答
4
这个问题有更好的答案。你可以在O（|V|^2）内完成，如果花费更多的努力，你甚至可以在线性时间内完成。
首先，找到G的强连通分量。在每个强连通分量中，你需要搜索以下情况： 1）如果在这个分量中存在前向边，则它不是单向连通的； 2）如果在这个分量中存在横叉边，则它不是单向连通的； 3）如果在以顶点u为根的树中有至少两条回溯边，指向u的适当祖先，则它不是单向连通的。
这可以在O（E）内完成。（我认为除了第三种情况之外，其他情况都能很好地实现！）
如果上述情况都没有发生，你应该检查G^SCC上是否存在横叉边或前向边（将强连通分量替换为单个节点的图G）。由于我们没有回溯边，因此可以通过在该图的每个顶点上重复dfs来完成，时间复杂度为O（|V|^2）。
首先，找到G的强连通分量。在每个强连通分量中，你需要搜索以下情况： 1）如果在这个分量中存在前向边，则它不是单向连通的； 2）如果在这个分量中存在横叉边，则它不是单向连通的； 3）如果在以顶点u为根的树中有至少两条回溯边，指向u的适当祖先，则它不是单向连通的。
这可以在O（E）内完成。（我认为除了第三种情况之外，其他情况都能很好地实现！）
如果上述情况都没有发生，你应该检查G^SCC上是否存在横叉边或前向边（将强连通分量替换为单个节点的图G）。由于我们没有回溯边，因此可以通过在该图的每个顶点上重复dfs来完成，时间复杂度为O（|V|^2）。
- Morteza Milani
4
如果跨边是从另一棵树的根到另一棵树的一个子节点，那该怎么办？这是一条完全合法的边。 - Brahadeesh
为什么后向边很重要？它们不是在简单路径上永远不会被遍历吗？ - pkoch
@pkoch，他已经在3）中说过了，如果以顶点u为根的树中有两个反向边指向u的祖先，则它不是单连通的，因为具有一个反向边的有向环仍然是一个单连通图。 - WY Hsu
第三点可以简单地使用数组来计算从某个顶点的反向边数。每当反向边指向SCC中的适当祖先时，我们将arr[v]增加1。当它达到>=2时，我们就中断它。这个问题与在线性顺序的顶点中找到唯一路径图非常相似。必须使用SCC来解决这类问题。使用SCC和SCC图可以使许多检查变得简单。 - Akash
3
你尝试过 深度优先搜索（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，因无重复。
- sud03r
7
我在其他地方读到过，对整个树运行一次DFS应该就足够了。是否有必要在每个顶点上运行？ - zebraman
只需为每个未访问的顶点重复即可，但您必须重新遍历所有下游内容（即使标记为“未访问”）。因此，您需要“曾经访问过”和“本次访问过”的标记。 - Rex Kerr
运行一次DFS不应该就足够了吗？在运行DFS之后，我们检查是否存在交叉边和前向边，然后就完成了。是否存在这样的情况，即运行一次带有检查交叉边和前向边的DFS不足以满足要求，因为在任何两个节点u和v之间存在超过一条路径时，都会在我们的DFS中显示出来？ - Saher Ahwal
4如果DFS森林中的树之间有交叉边，那么这些交叉边不会违反单连通图的定义。这些交叉边可能是从节点u到节点v的唯一路径上的边。 - Carl G
在这种情况下，运行一次 DFS 并检查是否存在前向边或树内跨边是否足够？这样的时间复杂度将为 O(V + E) ... - xdavidliu
显示剩余2条评论
0
我想到了以下解法:
1) 从任意一个顶点开始运行DFS，如果所有顶点都被DFS覆盖且没有正向边(否则不能覆盖所有顶点)，则该顶点可能是一个潜在的候选。
2) 如果在DFS中找到了一条从第j层到第i层的反向边，则在此之后找到的任何其他顶点都不应该有指向任何低于第j层的顶点的反向边，并且每个顶点都必须可以通过第二次DFS到达根节点。
如果正确的话，这样可以在线性时间内完成。
2) 如果在DFS中找到了一条从第j层到第i层的反向边，则在此之后找到的任何其他顶点都不应该有指向任何低于第j层的顶点的反向边，并且每个顶点都必须可以通过第二次DFS到达根节点。
如果正确的话，这样可以在线性时间内完成。
- Prashant
0
我不同意它的复杂度会是O(V^2)，因为在DFS中，我们并不像算法导论书中所说的那样为每个顶点调用它，语法是DFS(G)。我们只为整个图调用DFS，而不是单个顶点，不像BFS。因此，在这种情况下，根据我的理解，我们只需要调用一次DFS来检查它。如果再次遇到已访问的顶点，则该图不是单连通的（当然，对于每个不连通的组件，我们必须调用它，但它已经包含在代码中）。因此，复杂度将是O(V+E)。由于E=V，因此复杂度应该是O(V)。
- Harsh Sharma
0
看一下简单路径的定义。循环图可以是单连通的。DFS 对于 A->B, B->A 这种单连通的情况无法工作。
以下论文使用强连通分量来解决这个问题。
- K.Miao
-2
从每个顶点运行一次深度优先搜索。当且仅当一个连通分量内没有前向边和交叉边时，图形才是单连通的。
复杂度：O(V.E)
- imonkey
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接