CODEWITHSUNDEEP
graph
Jason Ni
Jason Ni

Reputation: 159

Why wrong with the breadth first search of graph

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);
            }
        }
    }
}

why the result is : 1 2 3 4 5 5 5, the 5 shows up three times?

Upvotes: 1

Views: 35

Answers (1)

advocateofnone
advocateofnone

Reputation: 2541

The problem with your code is that you should mark a node visited just before pushing it in the queue. Say we have a graph with three nodes 1 to 3. And the edges are (1-2) , (1-3) , (3-2). Now you push say 1 first, according to your code you pop 1 mark it as visited and push 2 and 3 ( say in this order ). Now you pop 2 and mark it visited. Now amongst neighbors of 2, 3 is still marked unvisited so you push it again. So node 3 ends up multiple times in the queue in bfs. I don't know what language you have written the code in but I have made the change hope syntax is correct

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);
            }
        }
    }
  }

Do comment if I made a mistake in code or if you still have a doubt.

Upvotes: 1

Related Questions