###### tags: `Leetcode` `medium` `graph` `python`

# 133. Clone Graph

## [題目連結:] https://leetcode.com/problems/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 value (```int```) and a list (```List[Node]```) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

**Test case format:**

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with ```val == 1```, the second node with ```val == 2```, and so on. The graph is represented in the test case using an adjacency list.

**An adjacency list** is a collection of unordered **lists** used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with ```val = 1```. You must return the **copy of the given node** as a reference to the cloned graph.


#### [圖片來源:] https://leetcode.com/problems/clone-graph/

## 解題想法:
* 題目為要求克隆一個無向圖
* 因為node.val不重複
* 可以將新建立的clone node存於hashMap中
* key: 原node.val
* val: clone node
* 遍歷原始node的鄰居
* 判斷是否該鄰居有clone出現在hashMap:
* 若有: 表示有clone了，直接連結
* 若沒有:
* 遞迴鄰居，並將其結果連結到當前clone.beibors

## Python:

class Node(object):
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        #dfs
        #存已建立的cloneNode
        visitMap={}
        return self.dfs(node,visitMap)
    def dfs(self,node,visitMap):
        if not node:
            return
        cloneNode=Node(node.val)
        #存值於map以免重複遍歷
        visitMap[node.val]=cloneNode
        #找其鄰居
        for bro in node.neighbors:
            if bro.val in visitMap: #已經記錄過該node
                cloneNode.neighbors.append(visitMap[bro.val])
            else: #dfs繼續往找
                newNode=self.dfs(bro,visitMap)
                cloneNode.neighbors.append(newNode)
        return cloneNode