java - Handling duplicate nodes in Breadth First Search -

imagine there graph. nodes of form graphnode. graph can have duplicate nodes. have bfs on graph. not know entire graph in beginning, i.e., there no way index nodes of graph. eg, root node given input bfs function.

this definition of graphnode, , cannot altered.

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

what best way handle visited nodes in bfs algorithm ? remember graph has duplicate nodes, i.e. multiple nodes same key. , not want delete or ignore duplicates.

why duplicate keys matter 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 value " + node.val);         // visit(visitednode)         if (node.left != null) queue.add(node.left);         if (node.right != null) queue.add(node.right);     } } 

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