题目链接: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 node 0 to both nodes 1 and 2.
- Second node is labeled as 1. Connect node 1 to node 2.
- 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
/ \
\_/
这道题的要求是克隆一个无向图。
一个小技巧就是用hash表将图中节点与克隆的对应节点关联起来。剩下的就可以用BFS或DFS进行遍历图,当遍历到某一节点时,如果hash表中没有与之对应的克隆的节点,就需要为该节点新建一节点。
-
BFS
时间复杂度:O(n)
空间复杂度:O(n)
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 == NULL)
return NULL;
unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> map;
map[node] = new UndirectedGraphNode(node -> label);
queue<UndirectedGraphNode *> q;
q.push(node);
while(!q.empty())
{
UndirectedGraphNode *temp = q.front();
q.pop();
for(int i = 0; i < temp -> neighbors.size(); ++ i)
{
if(map.find(temp -> neighbors[i]) == map.end())
{
map[temp -> neighbors[i]] = new UndirectedGraphNode(temp -> neighbors[i] -> label);
q.push(temp -> neighbors[i]);
}
(map[temp] -> neighbors).push_back(map[temp -> neighbors[i]]);
}
}
return map[node];
}
};
-
DFS
时间复杂度:O(n)
空间复杂度:O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution
{
unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> map;
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node)
{
if(node == NULL)
return NULL;
if(map.find(node) == map.end())
{
map[node] = new UndirectedGraphNode(node -> label);
for(auto n : node -> neighbors)
(map[node] -> neighbors).push_back(cloneGraph(n));
}
return map[node];
}
};