Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
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 #.
0. Connect node 0 to both nodes 1 and 2.1. Connect node 1 to node 2.2. Connect node 2 to node 2 (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<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 // map from origin node to copy node 15 unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> m; 16 unordered_map<UndirectedGraphNode *, bool> visited; 17 queue<UndirectedGraphNode*> q; 18 q.push(node); 19 while(!q.empty()) 20 {// BFS 21 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 else 35 { 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 else 49 { 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<UndirectedGraphNode *> neighbors; 6 * UndirectedGraphNode(int x) : label(x) {}; 7 * }; 8 */ 9 class Solution { 10 public: 11 map<UndirectedGraphNode *, UndirectedGraphNode *> 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 nodeClone 19 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<UndirectedGraphNode *> neighbors; 6 * UndirectedGraphNode(int x) : label(x) {}; 7 * }; 8 */ 9 10 struct Node 11 { 12 UndirectedGraphNode *node; 13 int ind; //next neighbor to visit 14 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 node 23 unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> m; 24 unordered_map<UndirectedGraphNode *, bool> visited; 25 stack<Node*> stk; 26 Node* newnode = new Node(node, 0); 27 stk.push(newnode); 28 visited[newnode->node] = true; 29 while(!stk.empty()) 30 {// DFS 31 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 else 39 topCopy = m[top->node]; 40 41 if(top->ind == top->node->neighbors.size()) 42 //finished copying its neighbors 43 stk.pop(); 44 else 45 { 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 else 63 { 64 topCopy->neighbors.push_back(m[top->node->neighbors[top->ind]]); 65 top->ind ++; 66 } 67 } 68 } 69 } 70 return m[node]; 71 } 72 };
转自：http://www.cnblogs.com/ganganloveu/p/4119462.html
133. Clone Graph (3 solutions)——无向无环图复制
原文：http://www.cnblogs.com/zl1991/p/6972288.html