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 node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1 / \ / \ 0 --- 2 / \ \_/
这题只需一边遍历一遍复制就可以了。
因此至少可以用三种方法：
1、广度优先遍历(BFS)
2、深度优先遍历(DFS)
2.1、递归
2.2、非递归
解法一：广度优先遍历
变量说明：
映射表m用来保存原图结点与克隆结点的对应关系。
映射表visited用来记录已经访问过的原图结点，防止循环访问。
队列q用于记录广度优先遍历的层次信息。
1 /** 2 * Definition for undirected graph. 3 * struct UndirectedGraphNode { 4 * int label; 5 * vector 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 // map from origin node to copy node15 unordered_map m;16 unordered_map visited;17 queue q;18 q.push(node);19 while(!q.empty())20 { // BFS21 UndirectedGraphNode* front = q.front();22 q.pop();23 24 if(visited[front] == false)25 {26 visited[front] = true;27 28 UndirectedGraphNode* cur;29 if(m.find(front) == m.end())30 {31 cur = new UndirectedGraphNode(front->label);32 m[front] = cur;33 }34 else35 {36 cur = m[front];37 }38 for(int i = 0; i < front->neighbors.size(); i ++)39 {40 if(m.find(front->neighbors[i]) == m.end())41 {42 UndirectedGraphNode* nei = new UndirectedGraphNode(front->neighbors[i]->label);43 m[front->neighbors[i]] = nei;44 cur->neighbors.push_back(nei);45 46 q.push(front->neighbors[i]);47 }48 else49 {50 cur->neighbors.push_back(m[front->neighbors[i]]);51 }52 }53 }54 }55 return m[node];56 }57 };
解法二：递归深度优先遍历(DFS)
1 /** 2 * Definition for undirected graph. 3 * struct UndirectedGraphNode { 4 * int label; 5 * vector neighbors; 6 * UndirectedGraphNode(int x) : label(x) {}; 7 * }; 8 */ 9 class Solution {10 public:11 map m;12 13 UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) 14 {15 if(node == NULL)16 return NULL;17 18 if(m.find(node) != m.end()) //if node is visited, just return the recorded nodeClone19 return m[node];20 21 UndirectedGraphNode *nodeClone = new UndirectedGraphNode(node->label);22 m[node] = nodeClone;23 for(int st = 0; st < node->neighbors.size(); st ++)24 {25 UndirectedGraphNode *temp = cloneGraph(node->neighbors[st]);26 if(temp != NULL)27 nodeClone->neighbors.push_back(temp);28 }29 return nodeClone;30 }31 };
解法三：非递归深度优先遍历(DFS)
深度优先遍历需要进行邻居计数。如果邻居已经全部访问，则该节点访问完成，可以出栈，否则就要继续处理下一个邻居。
1 /** 2 * Definition for undirected graph. 3 * struct UndirectedGraphNode { 4 * int label; 5 * vector neighbors; 6 * UndirectedGraphNode(int x) : label(x) {}; 7 * }; 8 */ 9 10 struct Node11 {12 UndirectedGraphNode *node;13 int ind; //next neighbor to visit14 Node(UndirectedGraphNode *n, int i): node(n), ind(i) {}15 };16 17 class Solution {18 public:19 UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {20 if(node == NULL)21 return NULL;22 // map from origin node to copy node23 unordered_map m;24 unordered_map visited;25 stack stk;26 Node* newnode = new Node(node, 0);27 stk.push(newnode);28 visited[newnode->node] = true;29 while(!stk.empty())30 { // DFS31 Node* top = stk.top();32 UndirectedGraphNode* topCopy;33 if(m.find(top->node) == m.end())34 {35 topCopy = new UndirectedGraphNode(top->node->label);36 m[top->node] = topCopy;37 }38 else39 topCopy = m[top->node];40 41 if(top->ind == top->node->neighbors.size())42 //finished copying its neighbors 43 stk.pop();44 else45 {46 while(top->ind < top->node->neighbors.size())47 {48 if(m.find(top->node->neighbors[top->ind]) == m.end())49 {50 UndirectedGraphNode* neiCopy = new UndirectedGraphNode(top->node->neighbors[top->ind]->label);51 m[top->node->neighbors[top->ind]] = neiCopy;52 topCopy->neighbors.push_back(neiCopy);53 if(visited[top->node->neighbors[top->ind]] == false)54 {55 visited[top->node->neighbors[top->ind]] = true;56 Node* topnei = new Node(top->node->neighbors[top->ind], 0);57 stk.push(topnei);58 }59 top->ind ++;60 break;61 }62 else63 {64 topCopy->neighbors.push_back(m[top->node->neighbors[top->ind]]);65 top->ind ++;66 }67 }68 }69 }70 return m[node];71 }72 };
转自：