Handling duplicate nodes in Breadth First Search

Question

Imagine there is a graph. The nodes are of the form GraphNode. The graph can have duplicate nodes. We have to do a BFS on the graph. We do not know the entire graph in the beginning, i.e., there is no way to index the nodes of the graph. For eg, only the root node is given as the input to the BFS function.

This is the definition of a GraphNode, and it cannot be altered.

public class GraphNode {
  int val;
  GraphNode left;
  GraphNode right;
  GraphNode(int x) { val = x; }
}

What is the best way to handle visited nodes in the BFS algorithm ? Remember that the graph has duplicate nodes, i.e. multiple nodes with the same key. And we do not want to delete or ignore the duplicates.

Bulla

Answer 1

Why would those duplicate keys matter for your breadth-first traversal?

E.g.

static void breadthFirstVisit(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println("visiting node with value " + node.val);
        // visit(visitedNode)
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

or like so omitting duplicates

 static void breadthFirstVisit(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList();
    Set<TreeNode> visited = new HashSet();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println("visiting node with value " + node.val);
        // visit(visitedNode)
        if (node.left != null && !visited.contains(node.left)) {
            queue.add(node.left);
            visited.add(node.left);
        } 
        if (node.right != null && !visited.contains(node.right)) {
            queue.add(node.right);
            visited.add(node.right);
        } 
    }
}

Batch

Thanks for the reply @Horse Badorties. What if two nodes have a common child. Let say node A and node B have the common child C. Once we append C to the queue after visiting A, then if we don't have a check of which all nodes are being visited, we will append node C again when we visit B. This way the entire subtree rooted at C will be appended to the queue twice and will be traversed twice. Reference: topcoder.com/community/data-science/data-science-tutorials/… – Bulla

that would not be a tree though. – Batch

I started the question with by stating that it is a graph. – Bulla

ok, TreeNode got me confused I guess. I'll add a second answer - no idea how to show code in a comment... ;-) – Batch

Oh my bad. I'll edit that in the question right away. Thanks. – Bulla

Ok, I understood my confusion. I was creating a HashSet of type Integer, instead of TreeNode/GraphNode. This way we won't traverse an already queue-appended node, but won't omit any other node having a val which has already been seen before. Thank you. – Bulla