# 133 Clone Graph

## 133. Clone Graph

## 1. Question

Clone an undirected graph. Each node in the graph contains a`label`and a list of its`neighbors`.

**OJ's undirected graph serialization:**

Nodes are labeled uniquely. We use`#`as a separator for each node, and`,`as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph`{0,1,2#1,2#2,2}`.

The graph has a total of three nodes, and therefore contains three parts as separated by`#`.

1. First node is labeled as`0`. Connect node`0`to both nodes`1`and`2`.
2. Second node is labeled as`1`. Connect node`1`to node`2`.
3. Third node is labeled as`2`. Connect node`2`to node`2`(itself), thus forming a self-cycle.

Visually, the graph looks like the following:

```
       1
      / \
     /   \
    0 --- 2
         / \
         \_/
```

## 2. Implementation

**(1) BFS**

```java
/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }

        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();

        map.put(node, new UndirectedGraphNode(node.label));
        queue.add(node);

        while (!queue.isEmpty()) {
            UndirectedGraphNode curNode = queue.remove();

            for (UndirectedGraphNode nextNode : curNode.neighbors) {
                if (!map.containsKey(nextNode)) {
                    map.put(nextNode, new UndirectedGraphNode(nextNode.label));
                    queue.add(nextNode);
                }
                map.get(curNode).neighbors.add(map.get(nextNode));
            }
        }
        return map.get(node);
    }
}
```

**(2) DFS**

```java
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();

        return dfs(node, map);
    }

    public UndirectedGraphNode dfs(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
        if (node == null) {
            return null;
        }

        if (map.containsKey(node)) {
            return map.get(node);
        }

        UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
        map.put(node, copy);

        for (UndirectedGraphNode neighbor : node.neighbors) {
            copy.neighbors.add(dfs(neighbor, map));
        }
        return copy;
    }
}
```

## 3. Time & Space Complexity

BFS: 时间复杂度O(n), 空间复杂度O(n)

DFS: 时间复杂度O(n), 空间复杂度O(n)


---

# 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://protegejj.gitbook.io/algorithm-practice/leetcode/graph/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.