Clone Graph Part I

发表于 更新于 分类于 阅读次数： 阅读次数： Disqus：

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.