Search Nearest Target Node

Question (LI.618)

Given a node in an undirected graph and a target, find the nearest node that is the target. If the target doesn't exist in the graph, return null.

Example

I: node_1, 50
2------3  5
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      1 --4

{node_1: 3, node_2: 4, node_3: 10, node_4: 50, node_5: 50}
O: node_4

Approach

We want to find the nearest node from a given node. BFS is the perfect candidate for that job.

Code

public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
                                      Map<UndirectedGraphNode, Integer> map,
                                      UndirectedGraphNode start,
                                      int target) {
    // init queue and set
    Queue<UndirectedGraphNode> queue = new LinkedList<>();
    Set<UndirectedGraphNode> visited = new HashSet<>();
    queue.offer(start);
    // breadth first search
    UndirectedGraphNode current;
    while (!queue.isEmpty()) {
        current = queue.poll();
        if (!visited.contains(current)) {
            visited.add(current);
            if (map.get(current) == target) {
                return current;
            }
            for (UndirectedGraphNode neighbor : current.neighbors) {
                queue.offer(neighbor);
            }
        }
    }
    return null;
}