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

Question

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

•使用队列执行简单的BFS遍历，同时保持队列中排队的节点的父节点。

•如果遇到具有邻居u的节点v，使得v已被访问但v不是u的父节点，则意味着图中存在循环。] >

伪代码

：

#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
上述方法是有效的，除非在两个顶点之间有1个以上的边缘，例如在以下情况下，我们在顶点0和1之间有2条边：

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

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

Edit

：我也在有向图上尝试了相同的逻辑，并且我面临类似的问题，即当我有一个从顶点0到顶点1的有向边，而另一个有从顶点1的有向边时的情况]顶点0

我是编程和学习算法的新手，当我读到BFS可用于循环检测时，我正在研究BFS。我试图在带有邻接表的无向图G上实现相同的目标...

Answer 1

我在Stack Exchange的Computer Science Forum处得到了我问题的答案。这是答案的link，我从那里复制@Simon Weber发表的内容