Search Graph Node

LeetCode LintCode

This problem is very similar to Clone Graph, we use Queue to assist traverse the graph, and use a HashSet to mark the nodes that have been visited.

We poll a node from the queue to traverse it, first we check if this node has mapped to the value of the target. Then we check its neighbors, if a neighbor has not been visited, we mark it visited and offer it to the queue to be waiting for traverse next time.

It's a very straightforward BFS template question.

public class Solution {
    /**
     * @param graph a list of Undirected graph node
     * @param values a hash mapping, <UndirectedGraphNode, (int)value>
     * @param node an Undirected graph node
     * @param target an integer
     * @return the a node
     */
    public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
                                          Map<UndirectedGraphNode, Integer> values,
                                          UndirectedGraphNode node,
                                          int target) {
     if (node == null || graph == null) {
        return null;
     }
     Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
     HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
     queue.offer(node);
     visited.add(node);
     while (!queue.isEmpty){
        UndirectedGraphNode temp = queue.poll();
        if (values.get(temp) == target){
            return temp;
        }
        for (UndirectedGraphNode nei : temp.neighbors) {
            if (!visited.contains(nei)){
                queue.offer(nei);
                visited.add(nei);
            }
        }
        return null;
    }
}
                                          }