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.

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