# 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;        
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/618.search-graph-nodes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.