618.Search Graph Nodes

1.description(Medium)

Given aundirected graph, anodeand atarget, return the nearest node to given node which value of it is target, returnNULLif you can't find.

There is amappingstore the nodes' values in the given parameters.

Notice

It's guaranteed there is only one available solution

Example

2------3  5
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      1 --4
Give a node 1, target is 50

there a hash named values which is [3,4,10,50,50], represent:
Value of node 1 is 3
Value of node 2 is 4
Value of node 3 is 10
Value of node 4 is 50
Value of node 5 is 50

Return node 4

2.Code

经典的graph中的BFS，这里没有size,因为没有层数这个概念，加了hashset去记录有没有访问过这个点。

Version 1:简洁版

class UndirectedGraphNode {
          int label;
          ArrayList<UndirectedGraphNode> neighbors;
          UndirectedGraphNode(int x) { 
              label = x; 
              neighbors = new ArrayList<UndirectedGraphNode>(); 
          }
      };
public class Solution_618 {
     /**
     * @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 || values==null){
            return node;
        }
        Queue<UndirectedGraphNode> queue=new LinkedList<UndirectedGraphNode>();
        HashSet<UndirectedGraphNode> set=new HashSet<UndirectedGraphNode>();
        queue.offer(node);
        set.add(node);

        while(!queue.isEmpty()){

            UndirectedGraphNode current=queue.poll();
            if(values.get(current)==target){
                return current;
            }

            ArrayList<UndirectedGraphNode> arr=current.neighbors;
            for(UndirectedGraphNode element : arr){
                if(!set.contains(element)){
                    queue.offer(element);
                    set.add(element);
                }                
            }
        }
        return null;        
    }        
}

Version 2:啰嗦版

 public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
                                          Map<UndirectedGraphNode, Integer> values,
                                          UndirectedGraphNode node,
                                          int target) {
        if(node==null || graph==null || values==null){
            return node;
        }
        LinkedList<UndirectedGraphNode> queue=new LinkedList<UndirectedGraphNode>();
        HashSet<UndirectedGraphNode> set=new HashSet<UndirectedGraphNode>();
        queue.offer(node);
        set.add(node);
        while(!queue.isEmpty()){
                UndirectedGraphNode current=queue.poll();
                if(values.get(current)==target){
                    return current;
                }
                ArrayList<UndirectedGraphNode> arr=current.neighbors;
                for(UndirectedGraphNode element : arr){
                    if(!set.contains(element)){
                        if(values.get(element)==target)
                        {
                            return element;
                        }
                        else{
                            queue.offer(element);
                            set.add(element);
                        }
                    }
                }
        }
        return null;        
    }