# 咸糖记录编程的地方

/

## 数据结构 4.图

133. Clone Graph

Given a reference of a node in a `connected` undirected graph, return a `deep copy `(clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. ``````
Input:
{"\$id":"1","neighbors":[{"\$id":"2","neighbors":[{"\$ref":"1"},{"\$id":"3","neighbors":[{"\$ref":"2"},{"\$id":"4","neighbors":[{"\$ref":"3"},{"\$ref":"1"}],"val":4}],"val":3}],"val":2},{"\$ref":"4"}],"val":1}

Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

``````

``````/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;

public Node() {}

public Node(int _val,List<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
Map<Integer,Node> map = new HashMap<>();
public Node cloneGraph(Node node) {
if(node == null){
return null;
}

return dfs(node);
}

public Node dfs(Node node){
if(node == null){
return null;
}
if (map.containsKey(node.val)){
return map.get(node.val);
}

Node res =  new Node(node.val, new ArrayList<Node>());

map.put(res.val,res);
for (Node neighbor : node.neighbors)
res.neighbors.add(dfs(neighbor));
return res;

}
}
``````