## Thursday, November 20, 2014

### [LeetCode] 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 `#`.
1. First node is labeled as `0`. Connect node `0` to both nodes `1` and `2`.
2. Second node is labeled as `1`. Connect node `1` to node `2`.
3. Third node is labeled as `2`. Connect node `2` to node `2` (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
```       1
/ \
/   \
0 --- 2
/ \
\_/```

BFS遍历：

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32``` ```class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(!node) return NULL; UndirectedGraphNode *p1 = node; UndirectedGraphNode *p2 = new UndirectedGraphNode(node->label); unordered_map ht; queue q; q.push(node); ht[node] = p2; while(!q.empty()) { p1 = q.front(); p2 = ht[p1]; q.pop(); for(int i=0; ineighbors.size(); i++) { UndirectedGraphNode *nb = p1->neighbors[i]; if(ht.count(nb)) { p2->neighbors.push_back(ht[nb]); } else { UndirectedGraphNode *temp = new UndirectedGraphNode(nb->label); p2->neighbors.push_back(temp); ht[nb] = temp; q.push(nb); } } } return ht[node]; } }; ```

DFS遍历：

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30``` ```class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(!node) return NULL; unordered_map ht; stack s; s.push(node); ht[node] = new UndirectedGraphNode(node->label); while(!s.empty()) { UndirectedGraphNode *p1 = s.top(), *p2 = ht[p1]; s.pop(); for(int i=0; ineighbors.size(); i++) { UndirectedGraphNode *nb = p1->neighbors[i]; if(ht.count(nb)) { p2->neighbors.push_back(ht[nb]); } else { UndirectedGraphNode *temp = new UndirectedGraphNode(nb->label); p2->neighbors.push_back(temp); ht[nb] = temp; s.push(nb); } } } return ht[node]; } }; ```