0

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

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

• 如果我遇到一个节点，该节点u的邻居已经被访问但不是其父节点，则意味着图中存在循环。vvvu

伪代码：

#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和之间有 2 条边1：

包含循环的图

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

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

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

4

1 回答 1

0

我在Stack Exchange的计算机科学论坛上得到了我的问题的答案。这是答案的链接，我正在从那里复制@Simon Weber发布的相同内容

如果案例到达您看到已访问节点的案例但它是当前节点的父节点，您只需检查它们之间是否存在双刃。如何做到这一点取决于您的数据结构，但如果您的邻接列表已排序，则仅相当于搜索边缘并检查它在那里的频率。

我看到的另一个问题是您的邻接列表实际上不包含任何边缘加倍的信息。

对于有向图，您可以完全摆脱“父检查”，因为这种情况出现的唯一时间是当您有两条边从u到 时v，反之亦然。

此外，如果图未连接，请注意，您的 BFS 不会覆盖所有图，因此您需要再次从未访问的顶点开始另一个 BFS。这对于有向图尤其重要，因为即使该图可能是连接的，您的 BFS 也可能不会涵盖所有这些。

于 2019-10-15T10:15:10.567 回答