转载

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 };