> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/618.search-graph-nodes.md).

# 618.Search Graph Nodes

## 1.description(Medium)

Given a`undirected graph`, a`node`and a`target`, return the nearest node to given node which value of it is target, return`NULL`if you can't find.

There is a`mapping`store 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;        
    }
```