Clone Graph

Clone Graph

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

How we serialize an undirected graph:

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

Example:

return a deep copied graph.

分析：

返回一个给定图的深拷贝。可以用BFS也可以用DFS。

Code：

BFS:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // write your code here
        if (node == nullptr) return nullptr;

        unordered_map<int, UndirectedGraphNode *> visited;
        queue<UndirectedGraphNode *> q;
        q.push(node);

        UndirectedGraphNode *rs = new UndirectedGraphNode(node->label);
        visited[node->label] = rs;

        while (!q.empty()) {
            UndirectedGraphNode *curr = q.front();
            q.pop();

            for (int i = 0; i < curr->neighbors.size(); i++) {
                if (visited.find(curr->neighbors[i]->label) == visited.end()) {
                    rs = new UndirectedGraphNode(curr->neighbors[i]->label);
                    
                    visited[curr->neighbors[i]->label] = rs;
                    q.push(curr->neighbors[i]);
                    visited[curr->label]->neighbors.push_back(rs);
                }
                else {
                    visited[curr->label]->neighbors.push_back(visited[curr->neighbors[i]->label]);
                }
            }
        }

        return visited[node->label];
    }
};

DFS:

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
33
34
35
36
37
38
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // write your code here
        if (node == nullptr) return nullptr;
        
        unordered_map<int, UndirectedGraphNode *> visited;
        return cloneGraph(node, visited);
    }
    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node, unordered_map<int, UndirectedGraphNode *> &visited) {
        UndirectedGraphNode *rs = new UndirectedGraphNode(node->label);
        visited[node->label] = rs;
        
        for (int i = 0; i < node->neighbors.size(); i++) {
            if (!visited[node->neighbors[i]->label]){
                rs->neighbors.push_back(cloneGraph(node->neighbors[i], visited));
            }
            else{
                rs->neighbors.push_back(visited[node->neighbors[i]->label]);
            }
        }
        
        return rs;
    }
};