Nicksxs's Blog

What hurts more, the pain of hard work or the pain of regret?

0%

Clone Graph Part I

problem

1
2
3
4
5
6
Clone a graph. Input is a Node pointer. Return the Node pointer of the cloned graph.

A graph is defined below:
struct Node {
vector neighbors;
}

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef unordered_map<Node *, Node *> Map;

Node *clone(Node *graph) {
if (!graph) return NULL;

Map map;
queue<Node *> q;
q.push(graph);

Node *graphCopy = new Node();
map[graph] = graphCopy;

while (!q.empty()) {
Node *node = q.front();
q.pop();
int n = node->neighbors.size();
for (int i = 0; i < n; i++) {
Node *neighbor = node->neighbors[i];
// no copy exists
if (map.find(neighbor) == map.end()) {
Node *p = new Node();
map[node]->neighbors.push_back(p);
map[neighbor] = p;
q.push(neighbor);
} else { // a copy already exists
map[node]->neighbors.push_back(map[neighbor]);
}
}
}

return graphCopy;
}

anlysis

using the Breadth-first traversal
and use a map to save the neighbors not to be duplicated.

请我喝杯咖啡