BFS 和 DFS 解决 LeetCode133. Clone Graph

Posted on | In | |

题目描述

133 Clone Graph
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
     / \
     \_/

题目虽然讲了很多内容，包括OJ中序列化的图的表示法，但是题目所要求的复制一个图，实际上只是考察了图的遍历。根据给定的一个UndirectedGraphNode* node，由该点出发，遍历整个图，并以此创建一个新的和原来一样的无向图即可。

算法分析

图的遍历可以用DFS和BFS实现。这题唯一需要注意的地方在于，在创建新图时，要确认新建结点的“时机”以及连接节点的方式，不要重复new同一个结点。例如，假设给定的图为：

1
0 -- 1

使用DFS，先访问0，然后访问0的临接结点1，而在访问了1之后，要准确地将先前创建的新的0结点放入1的neighbors中，否则会导致图的结构错误。这里，我采用了map<int, UndirectedGraphNode*>来解决。既可以保证不重复创建结点，又能根据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
// DFS version
class Solution {

public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) {
            return NULL;
        }
        node_map[node->label] = new UndirectedGraphNode(node->label);
        dfs(node);
        return node_map[node->label];
    }
private:
    map<int, UndirectedGraphNode*> node_map;
    void dfs(UndirectedGraphNode* &node) {
        for (int i = 0; i < node->neighbors.size(); i++) {
            UndirectedGraphNode* neighbor = node->neighbors[i];
            if (node_map[neighbor->label] == NULL) {
                node_map[neighbor->label] = new UndirectedGraphNode(neighbor->label);
                dfs(neighbor);
            }
            node_map[node->label]->neighbors.push_back(node_map[neighbor->label]);
        }
    }
};

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
// BFS version:
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
    if (!node) {
        return NULL;
    }
    map<int, UndirectedGraphNode*> node_map;
    node_map[node->label] = new UndirectedGraphNode(node->label);
    queue<UndirectedGraphNode*> que;
    que.push(node);
    while (!que.empty()) {
        UndirectedGraphNode* temp = que.front();
        que.pop();
        for (int i = 0; i < temp->neighbors.size(); i++) {
            UndirectedGraphNode* neighbor = temp->neighbors[i];
            if (node_map[neighbor->label] == NULL) {
                node_map[neighbor->label] = new UndirectedGraphNode(neighbor->label);
                que.push(neighbor);
            }
            node_map[temp->label]->neighbors.push_back(node_map[neighbor->label]);
        }
    }
    return node_map[node->label];
    }
};

本文为博主原创文章，转载请注明出处。