LeetCode OJ 133题:Clone Graph – 青藜学士

题目如下:

题目挺长的,其实只需要关注第一行就OK了。这道题思路挺明显的,对于图来说要么BFS,要么DFS,至于具体细节,我觉得与138题:Copy List with Random Pointer很像。在BFS或DFS过程中,可能要调整顶点的邻接点,这个时候不要忘了它的邻接点可能还没有创建。所以,有以下思路:

遍历两遍无向图。第一遍,创建所有结点,不用保存顶点间关系。第二遍,调整顶点间关系。顶点间关系保存在neighbors中,为了能够找到新创建顶点的位置,第一遍遍历时候需要保存原顶点与新顶点指针的一一对应关系,这里可用map或unordered_map保存。

这里我说的有点啰嗦,请看代码中注释就明白了。这里,我采用BFS遍历。时间复杂度为O(N),空间复杂度也为O(N)。

1 /**
2 * Definition for undirected graph.
3 * struct UndirectedGraphNode {
4 * int label;
5 * vector<UndirectedGraphNode *> neighbors;
6 * UndirectedGraphNode(int x) : label(x) {};
7 * };
8 */
9 class Solution {
10 public:
11 UndirectedGraphNode* cloneGraph(UndirectedGraphNode *node)
12 {
13 if (node == NULL)
14 {
15 return NULL;
16 }
17
18 map<UndirectedGraphNode*, UndirectedGraphNode*> gphMap;
19 queue<UndirectedGraphNode*> gphQue;
20
21 //创建所有顶点
22 gphQue.push(node);
23 while (!gphQue.empty())
24 {
25 UndirectedGraphNode *tmp = gphQue.front();
26 gphQue.pop();
27
28 if (gphMap.find(tmp) == gphMap.end())
29 {
30 UndirectedGraphNode *newNode = new UndirectedGraphNode(tmp->label);
31 gphMap[tmp] = newNode;
32
33 for (int i = 0; i != tmp->neighbors.size(); ++i)
34 {
35 gphQue.push(tmp->neighbors[i]);
36 }
37 }
38 }
39
40 //调整顶点间关系
41 gphQue.push(node);
42 while (!gphQue.empty())
43 {
44 UndirectedGraphNode *tmp = gphQue.front();
45 gphQue.pop();
46
47 UndirectedGraphNode *exitNode = gphMap[tmp];
48 if (exitNode->neighbors.empty() && !tmp->neighbors.empty())
49 {
50 for (int i = 0; i != tmp->neighbors.size(); ++i)
51 {
52 exitNode->neighbors.push_back(gphMap[tmp->neighbors[i]]);
53 gphQue.push(tmp->neighbors[i]);
54 }
55 }
56 }
57
58 return gphMap[node];
59 }
60 };

其实上面这种方法,是挺清楚直观的。但还是要考虑一下,能不能优化一下,只遍历一次。反正,我参加面试时,面试官说:”只遍历一次,找出(实现)…。其实,实现起来并不难,只需要把两部分遍历的操作合并起来就好了。下面我分别给出BFS和DFS算法,两种算法的时间复杂度都是O(N),空间复杂度也都是O(N)。

实现图拷贝的BFS算法如下:

1 class Solution {
2 public:
3 UndirectedGraphNode *cloneGraph(const UndirectedGraphNode *node)
4 {
5 if (node == NULL)
6 {
7 return NULL;
8 }
9
10 map<const UndirectedGraphNode*, UndirectedGraphNode*> gphMap;
11 queue<const UndirectedGraphNode *> gphQue;
12
13 gphQue.push(node);
14 gphMap[node] = new UndirectedGraphNode(node->label);
15 while (!gphQue.empty())
16 {
17 const UndirectedGraphNode *tmp = gphQue.front();
18 gphQue.pop();
19
20 for (int i = 0; i != tmp->neighbors.size(); ++i)
21 {
22 if (gphMap.find(tmp->neighbors[i]) == gphMap.end())
23 {
24 //build the vertex
25 UndirectedGraphNode *newNode = new UndirectedGraphNode(tmp->neighbors[i]->label);
26 gphMap[tmp->neighbors[i]] = newNode;
27 gphMap[tmp]->neighbors.push_back(newNode); //Adjust the Vertex
28 gphQue.push(tmp->neighbors[i]);
29 }
30 else
31 {
32 gphMap[tmp]->neighbors.push_back(gphMap[tmp->neighbors[i]]);
33 }
34 }
35 }
36
37 return gphMap[node];
38 }
39 };

 

实现图拷贝的DFS算法如下:

1 class Solution {
2 public:
3 UndirectedGraphNode *cloneGraph(const UndirectedGraphNode *node)
4 {
5 if(node == NULL)
6 {
7 return NULL;
8 }
9
10 map<const UndirectedGraphNode*, UndirectedGraphNode*> gphMap;
11
12 return GphClone(node, gphMap); //or return gphMap[node]
13 }
14 private:
15 // DFS
16 static UndirectedGraphNode* GphClone(const UndirectedGraphNode *node,
17 map<const UndirectedGraphNode*, UndirectedGraphNode*> &gphMap)
18 {
19 // a copy already exists
20 if (gphMap.find(node) != gphMap.end())
21 {
22 return gphMap[node];
23 }
24
25 UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
26 gphMap[node] = newNode;
27
28 for (int i = 0; i != node->neighbors.size(); ++i)
29 {
30 newNode->neighbors.push_back(GphClone(node->neighbors[i], gphMap));
31 }
32
33 return newNode;
34 }
35 };

 虽然时间复杂度都是O(N),但从提交结果看,DFS好像快一点,这个不懂。

本文链接:LeetCode OJ 133题:Clone Graph,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量