**Difficulty: Medium**

**Frequency: N/A**

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

.

- First node is labeled as
`0`

. Connect node`0`

to both nodes`1`

and`2`

. - Second node is labeled as
`1`

. Connect node`1`

to node`2`

. - 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 / \ \_/

**Test Cases:**

**Solution 1:**

**Data structure:**

**Steps:**

**Complexity:**

Runtime:

Space:

**Code:**

/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */ class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (!node) return NULL; UndirectedGraphNode *p1 = node; UndirectedGraphNode *p2 = new UndirectedGraphNode(node->label); unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> m; queue<UndirectedGraphNode*> q; q.push(node); m[node] = p2; while (!q.empty()) { p1 = q.front(); p2 = m[p1]; q.pop(); for (int i = 0; i < p1->neighbors.size(); i++) { UndirectedGraphNode *nb = p1->neighbors[i]; if (m.count(nb)) { p2->neighbors.push_back(m[nb]); } else { UndirectedGraphNode *tmp = new UndirectedGraphNode(nb->label); p2->neighbors.push_back(tmp); m[nb] = tmp; q.push(nb); } } } return m[node]; } };

**Solution 2:**

**Data structure:**

**steps:**

**Complexity**:

Runtime:

Space:

**Code**:

**Submission errors:**

**Things to learn:**

Advertisements

[…] Clone Graph […]

LikeLike

[…] Clone Graph […]

LikeLike