为什么图的广度优先搜索错误

Question

public static void BFS(TTNode node){
    Set<TTNode> accessedNodes = new HashSet<TTNode>();
    Queue<TTNode> queue = new LinkedList<TTNode>();
    queue.offer(node);
    while (!queue.isEmpty()){
        TTNode accessingNode = queue.poll();
        System.out.println(accessingNode.payload);
        accessedNodes.add(accessingNode);
        for (TTNode child : accessingNode.children){
            if (!accessedNodes.contains(child)){
                queue.offer(child);
            }
        }
    }
}

为什么结果是：1 2 3 4 5 5 5，5出现了3次？

Answer 1

你的代码的问题是你应该标记一个刚刚访问过的节点将其推入队列。假设我们有一个包含三个节点 1 到 3 的图。还有边是（1-2），（1-3），（3-2）。现在你先按 say 1，根据你的代码，你弹出 1 将其标记为已访问并按 2 和 3（按此顺序说）。现在弹出 2 并将其标记为已访问。现在在 2 的邻居中，3 仍然标记为未访问，因此您再次推送它。所以节点 3 在 bfs 的队列中多次结束。我不知道您用什么语言编写了代码，但我已经进行了更改希望语法正确

public static void BFS(TTNode node){
    Set<TTNode> accessedNodes = new HashSet<TTNode>();
    Queue<TTNode> queue = new LinkedList<TTNode>();
    queue.offer(node);
    accessedNodes.add(node);
    while (!queue.isEmpty()){
        TTNode accessingNode = queue.poll();
        System.out.println(accessingNode.payload);
        for (TTNode child : accessingNode.children){
            if (!accessedNodes.contains(child)){
                accessedNodes.add(child);
                queue.offer(child);
            }
        }
    }
  }

如果我在代码中犯了错误或者您仍然有疑问，请发表评论。

为什么图的广度优先搜索错误

Why wrong with the breadth first search of graph

graph