graph - Union-Find算法并判断图中一条边是否属于圈

Question

我正在阅读一本关于算法的书(“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 by depthFirstSearch() led to a cycle with other element of edges. This was due to the fact that if vertices v and u belonged to edges, then the edge(vu) was disregarded by depthFirstSearch(). A problem arises when depthFirstSearch() 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) 的边连接不同集合中的顶点。

但是，我仍然不知道如何快速检查边缘是否是循环的一部分。谁能给我一个与上述联合查找问题相关的算法的粗略解释？

Answer 1

粗略的解释可能是检查链接是否为反向链接，只要有反向链接，就有循环，只要有循环，就有反向链接(对于有向图和无向图都是如此)。

反向链接是从后代指向父节点的边，您应该知道，当使用 DFS 算法遍历图时，您构建了一个森林，而父节点是在遍历后期标记为完成的节点。

我给了你一些指向哪里看的指示，让我知道这是否有助于你澄清你的问题。