BFS
There are two things need to be prepared
- Queue<> queue = new LinkedList<>()
- HashSet<> visited = new HashSet<>()
In the while loop, we process on the node which polled from queue instead of process node who is going to add to queue.
Search Graph Nodes
public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
Map<UndirectedGraphNode, Integer> values,
UndirectedGraphNode node,
int target) {
Queue<UndirectedGraphNode> q = new LinkedList<>();
HashSet<UndirectedGraphNode> visited = new HashSet<>();
visited.add(node);
q.offer(node);
while (!q.isEmpty()) {
UndirectedGraphNode temp = q.poll();
if (values.get(temp) == target) {
return temp;
}
for (UndirectedGraphNode x : temp.neighbors) {
if (!visited.contains(x)) {
q.offer(x);
visited.add(node);
}
}
}
return null;
}