> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/08_bfs/133.-clone-graph.md).

# 133. Clone Graph

<https://leetcode.com/problems/clone-graph/>

## solution

* bfs

```python
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return node

        node_dict = {}
        node_dict[node.val] = Node(node.val)  # 遍历copy时，快速定位已有Node, 用于neighbor关系。顺便记录了已遍历过的
        queue = collections.deque([node])

        while queue:
            cur = queue.popleft()  # 注意这里不能和node重名, 用于最后输出

            for neighbour in cur.neighbors:
                if neighbour.val not in node_dict:
                    node_dict[neighbour.val] = Node(neighbour.val)
                    queue.append(neighbour)  # 注意: 放在if里避免了重复遍历相同，因此没有创建额外的visited

                # 这里每次append, 而不是一个层之后 neighbor=clone_neighbor
                node_dict[cur.val].neighbors.append(node_dict[neighbour.val])

        return node_dict[node.val]
```

时间复杂度：O(V+E)\
空间复杂度：O(V+E)

* dfs

```python
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        visited = defaultdict(Node)

        def clone(node):
            if not node:
                return

            if node in visited:
                return visited[node]

            clone_node = Node(node.val)
            visited[node] = clone_node

            for nei in node.neighbors:
                clone_node.neighbors.append(clone(nei))
            return clone_node

        return clone(node)
```

## follow up

[138. Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/)

```python
# 第一遍生成copy的node生成记录hash指向；第二遍把next和random point指向关联

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:  # 注意空
          return

        mydict = {}  # 关键是记录original到clone的关系，
        cur = head  # 后续还需要用到head
        while cur:
            mydict[cur] = Node(cur.val)
            cur = cur.next

        cur = head
        while cur:
            mydict[cur].next = mydict.get(cur.next, None)  # next和random都可能为None, 因此都用get
            mydict[cur].random = mydict.get(cur.random, None)
            cur = cur.next

        return mydict[head]
```

时间复杂度：O(n)\
空间复杂度：O(n)

* 不使用hashmap, O(1)空间复杂度

```python
# 首先把clone node链接到原有链表，再拷贝random节点引用

class Solution:
    def copyRandomList(self, head):
        node = head
        while node:
            copy = Node(node.label)
            next = node.next
            node.next = copy
            copy.next = next
            node = next

        node = head
        head2 = node.next
        while node:
            copy = node.next
            next = copy.next
            if next:
                copy.next = next.next
            if node.random:
                copy.random = node.random.next
            node = next

        return head2
```

[1490. Clone N-ary Tree](https://leetcode.com/problems/clone-n-ary-tree/description/)

```python
```

[1485 Clone Binary Tree With Random Pointer](/mle-interview/01_leetcode/07_dfs/1485.-clone-binary-tree-with-random-pointer.md)