在无向图中使用BFS进行循环检测时如何处理两个顶点之间的平行边？

Question

我是编程和学习算法的新手，当我读到 BFS 可以用于循环检测时，我正在研究 BFS。我尝试在具有邻接列表表示的无向图 G 上实现相同的功能。我的做法如下：

• Do a simple BFS Traversal using a Queue while maintaining the parent node of nodes enqueued in the queue.

• If I come across a node u that has a neighbor v such that v is already visited but v is not the parent of u then that means there is cycle in the graph.

伪代码:

#adjList is the adjacency list given as a dictionary
#myQueue is a double-sided queue containing node and its parent node ([Node, parNode])
#visited is a set containing visited nodes

while(myQueue):
    currNode, parNode = myQueue.pop() #dequeue operation
    visited.add(currNode) #Marking currNode as visited
    for childNode in adjList[currNode]: #Traversing through all children of currNode
        if currNode not in visited:
            myQueue.appendleft([childNode, currNode]) #Enqueue operation
        else:
            if childNode!=parNode: #Main logic for cycle detection
                print('CYCLE DETECTED')
                break

上述方法有效，除非我在 2 个顶点之间有超过 1 条边，例如在以下情况下，我们在顶点 0 和 1 之间有 2 条边：

上图的邻接表为：adjList = {0:[1, 1, 2], 1:[0, 0], 2:[0]}。在这里我们可以清楚地看到该图包含一个循环（在邻接表表示中，1 在 0 的邻接表中出现两次，而 0 在 0 中出现两次1 的邻接表）但是上面的算法无法检测到相同的，因为当 BFS 到达顶点 1 时，顶点 0 已经被访问但是顶点 0 也是顶点 1 的父节点，所以这个循环不会被发现。

我的问题是如何修改上述算法来检测此类情况？

编辑：我也在有向图上尝试了相同的逻辑，我面临着类似的问题，即当我有一条从顶点 0 到顶点的有向边时1 和另一个从顶点 1 到顶点 0

的有向边

Answer 1

我在 Computer Science Forum of Stack Exchange. Here's the link to the answer and I am copying the same from there as posted by @Simon Weber

得到了问题的答案

If the case arrives where you see the case of a node being already visited but it is the parent of your current node, you just have to check whether there is a double edge between them. How to do that depends on your data structure, but if your adjacency list is sorted it would just amount to searching for the edge and checking how often it is in there.

Another problem I see is that your adjacency list doesn't actually contain any information that the edge is doubled.

For directed graphs, you can just completely get rid of the "parent check", as the only time that case arrives is when you have two edges going from u to v and vice versa.

Additionally, be careful if the graph is not connected, your BFS will not cover all of it, so you would need to start another BFS from an unvisited vertex again. This is especially important for directed graphs, as even if the graph might be connected, your BFS will probably not cover all of it.

在无向图中使用BFS进行循环检测时如何处理两个顶点之间的平行边？

How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?

graph

breadth-first-search

graph-traversal

cycle-detection