题目：
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
How we serialize an undirected graph:
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
/ \
\_/
Example
return a deep copied graph.
题解：
DFS(recursion)
Solution 1 ()
class Solution {
public:
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> hash;
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (!node) return node;
if(hash.find(node) == hash.end()) {
hash[node] = new UndirectedGraphNode(node -> label);
for (auto neighbor : node -> neighbors) {
(hash[node] -> neighbors).push_back( cloneGraph(neighbor) );
}
}
return hash[node];
}
};DFS(stack)
Solution 2 ()
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (node == nullptr)
return nullptr;
stack<UndirectedGraphNode* > stack;
map<int, UndirectedGraphNode* > visitTable;
UndirectedGraphNode* newnode = new UndirectedGraphNode(node->label);
visitTable[node->label] = newnode;
stack.push(node);
while (!stack.empty()) {
UndirectedGraphNode* cur = stack.top();
stack.pop();
for (auto neighbor : cur->neighbors) {
if (visitTable.find(neighbor->label) == visitTable.end()) {
stack.push(neighbor);
UndirectedGraphNode* newneighbor = new UndirectedGraphNode(neighbor->label);
visitTable[neighbor->label] = newneighbor;
}
visitTable[cur->label]->neighbors.push_back(visitTable[neighbor->label]);
}
}
return newnode;
}
};BFS
Solution 3 ()
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (node == nullptr)
return nullptr;
queue<UndirectedGraphNode* > queue;
map<int, UndirectedGraphNode* > visitTable;
UndirectedGraphNode* newnode = new UndirectedGraphNode(node->label);
visitTable[node->label] = newnode;
queue.push(node);
while (!queue.empty()) {
UndirectedGraphNode* cur = queue.front();
queue.pop();
for (auto neighbor : cur->neighbors) {
if (visitTable.find(neighbor->label) == visitTable.end()) {
UndirectedGraphNode* newneighbor = new UndirectedGraphNode(neighbor->label);
visitTable[neighbor->label] = newneighbor;
queue.push(neighbor);
}
visitTable[cur->label]->neighbors.push_back(visitTable[neighbor->label]);
}
}
return newnode;
}
};