# 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)


---

# 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://longxingtan.gitbook.io/mle-interview/01_leetcode/08_bfs/133.-clone-graph.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.