我正在阅读一本关于算法的书(“C++ 中的数据结构和算法”)并且遇到了以下练习:
Ex. 20. Modify
cycleDetectionDFS()
so that it could determine whether a particular edge is part of a cycle in an undirected graph.
在关于图表的章节中,这本书是这样写的:
Let us recall from a preceding section that depth-first search guaranteed generating a spanning tree in which no elements of
edges
used bydepthFirstSearch()
led to a cycle with other element ofedges
. This was due to the fact that if vertices v and u belonged toedges
, then the edge(vu) was disregarded bydepthFirstSearch()
. A problem arises whendepthFirstSearch()
is modified so that it can detect whether a specific edge(vu) is part of a cycle (see Exercise 20). Should such a modified depth-first search be applied to each edge separately, then the total run would be O(E(E+V)), which could turn into O(V^4) for dense graphs. Hence, a better method needs to be found.The task is to determine if two vertices are in the same set. Two operations are needed to implement this task: finding the set to which a vertex v belongs and uniting two sets into one if vertex v belongs to one of them and w to another. This is known as the union-find problem.
稍后,作者描述了如何将两个集合合并为一个集合,以防传递给函数 union(edge e)
的边连接不同集合中的顶点。
但是,我仍然不知道如何快速检查边缘是否是循环的一部分。谁能给我一个与上述联合查找问题相关的算法的粗略解释?
最佳答案
粗略的解释可能是检查链接是否为反向链接,只要有反向链接,就有循环,只要有循环,就有反向链接(对于有向图和无向图都是如此)。
反向链接是从后代指向父节点的边,您应该知道,当使用 DFS 算法遍历图时,您构建了一个森林,而父节点是在遍历后期标记为完成的节点。
我给了你一些指向哪里看的指示,让我知道这是否有助于你澄清你的问题。
关于graph - Union-Find算法并判断图中一条边是否属于圈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17503934/