BFS

There are two things need to be prepared

  1. Queue<> queue = new LinkedList<>()
  2. 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;
}

results matching ""

    No results matching ""