我可以在没有父图的情况下检测无向图中的循环吗？

Question

我正在尝试检测无向图是否包含循环。这是我的伪代码：

BFSVisit(node, visited){ // Visiting all nodes in the graph that can be reached from "node"
    containsCycle ← false
    visited.add(node)
    queue ← empty queue
    queue.add(node)
    while (queue is not empty){
        thisNode ← queue.pop()
        for (neighbor in thisNode.edges){
            if (neighbor is in visited and neighbor != thisNode){
                containsCycle ← true
            }
            if (neighbor is not in visited){
                visited.add(neighbor)
                queue.add(neighbor)
            }
        }
    }
    return containsCycle
} 

但是，chatgpt 告诉我我的代码是错误的，特别是第一个 if 测试，我打算在其中检查循环。我认为我可以通过检查不是当前节点的父节点的节点是否已被访问来检测循环。如果这个条件为真，那么我们就有了一个循环。在我看来，thisNode 是 for 循环中每个节点的父节点。

我见过人们使用父地图的其他解决方案，我可以这样做，但我想看看是否还有其他方法来解决问题。

Answer 1

算法不正确。它没有实现您所描述的内容：

我认为我可以通过检查不是当前节点的父节点的节点是否已被访问来检测循环

我猜你认为你已经通过执行此检查实现了“不是父级”规则：

neighbor != thisNode

，但这只是检查边缘是否是自引用。我们应该在这里检查一下

neighbor != parentOf(thisNode)

。

想象一下下面的图表：

        1
       /
      2

很明显这个图没有循环，但是当我们在节点 1 处启动函数时，我们得到：

• 首先队列有1，该节点被标记为已访问。
• 在循环的第一次迭代中，节点 1 从队列中弹出
• 第一个（也是唯一的）邻居是 2，它尚未被访问，因此它被标记为已访问并添加到队列中。队列现在有一个条目。
• 在循环的第二次迭代中，节点 2 从队列中弹出
• 第一个（也是唯一的）邻居是 1（它不是

  thisNode

  ，即 2），并且它已被访问过，因此该函数断定存在循环，这显然是错误的。

正如您自己所说，当前节点的“父节点”应从邻居列表中排除。这就是为什么某些算法使用父映射的原因。实现此目的的另一种方法是将（节点，父级）对推入队列。或者您可以将

visited

集扩展到地图，这样它既可以提供“已访问”功能，也可以提供“父级”功能。这是实现第一个想法的改编伪代码：

BFSVisit(node, visited){
    containsCycle ← false
    visited.add(node)
    queue ← empty queue
    queue.add((node, null))  // The parent of the first node is null (i.e. no parent)
    while (queue is not empty){
        (thisNode, parent) ← queue.pop()
        for (neighbor in thisNode.edges){
            if (neighbor is in visited and neighbor != parent){  // compare with parent
                containsCycle ← true
                break // No need to continue
            }
            if (neighbor is not in visited){
                visited.add(neighbor)
                queue.add((neighbor, thisNode)) // thisNode is the parent of neighbor
            }
        }
    }
    return containsCycle
}