LeetCode 算法题之CloneGraph

一个无向图，深度克隆一份无向图出来；

这个题目本身并不是很难，主要是要深度克隆，所以采用hash表来进行存储旧的节点和新的节点的地址，采用BFS遍历，算法如下：

 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         if(node==NULL)
13         return NULL;
14         unordered_set<int> visted;//保存访问过的节点label
15         unordered_map<int,UndirectedGraphNode*> pointMap;//保存节点的新地址
16         queue<UndirectedGraphNode*> qu;
17         qu.push(node);
18         UndirectedGraphNode *newNode=new UndirectedGraphNode(node->label);
19         UndirectedGraphNode *startNode=newNode;
20         pointMap.insert(make_pair(node->label,newNode));
21         while(!qu.empty())
22         {
23             UndirectedGraphNode *oldNode=qu.front();
24             newNode=pointMap.find(oldNode->label)->second;
25             qu.pop();
26             for(vector<UndirectedGraphNode*>::iterator iter=oldNode->neighbors.begin();iter!=oldNode->neighbors.end();iter++)
27             {
28                 
29                 if(visted.find((*iter)->label)==visted.end()&&(pointMap.find((*iter)->label)==pointMap.end()))
30                 {
31                    UndirectedGraphNode *q=new UndirectedGraphNode((*iter)->label);
32                    pointMap.insert(make_pair((*iter)->label,q));
33                     qu.push(*iter);
34                     newNode->neighbors.push_back(q);
35                 }
36                 else
37                 {
38                     newNode->neighbors.push_back(pointMap.find((*iter)->label)->second);
39                 }
40             }
41             visted.insert(oldNode->label);
42 
43         }
44         return startNode;
45         
46         
47     }
48 };

最开始的时候遇到一个问题：Output exceed;看不懂什么意思，而且本机上返回的结果看起来似乎也没有问题。于是我在visual studio中逐步调试，最后发现问题在于29行，原来我只有一个判断if(visited.find((*iter)->label)!=visited.end()),这样子即使导致一些节点被多次推入队列，于是new了太多的节点，所以出现了output exceed,如三角形无向图1，2，3，节点3 在访问节点1的时候会推入队列，访问节点2的时候又会推入队列，所以复制了两遍节点3。