133 Clone Graph

133. Clone Graph

1. Question

Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors.
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. 1.
    First node is labeled as0. Connect node0to both nodes1and2.
  2. 2.
    Second node is labeled as1. Connect node1to node2.
  3. 3.
    Third node is labeled as2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
1
2
/ \
3
/ \
4
0 --- 2
5
/ \
6
\_/
Copied!

2. Implementation

(1) BFS
1
/**
2
* Definition for undirected graph.
3
* class UndirectedGraphNode {
4
* int label;
5
* List<UndirectedGraphNode> neighbors;
6
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
7
* };
8
*/
9
public class Solution {
10
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
11
if (node == null) {
12
return null;
13
}
14
15
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
16
Queue<UndirectedGraphNode> queue = new LinkedList<>();
17
18
map.put(node, new UndirectedGraphNode(node.label));
19
queue.add(node);
20
21
while (!queue.isEmpty()) {
22
UndirectedGraphNode curNode = queue.remove();
23
24
for (UndirectedGraphNode nextNode : curNode.neighbors) {
25
if (!map.containsKey(nextNode)) {
26
map.put(nextNode, new UndirectedGraphNode(nextNode.label));
27
queue.add(nextNode);
28
}
29
map.get(curNode).neighbors.add(map.get(nextNode));
30
}
31
}
32
return map.get(node);
33
}
34
}
Copied!
(2) DFS
1
public class Solution {
2
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
3
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
4
5
return dfs(node, map);
6
}
7
8
public UndirectedGraphNode dfs(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
9
if (node == null) {
10
return null;
11
}
12
13
if (map.containsKey(node)) {
14
return map.get(node);
15
}
16
17
UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
18
map.put(node, copy);
19
20
for (UndirectedGraphNode neighbor : node.neighbors) {
21
copy.neighbors.add(dfs(neighbor, map));
22
}
23
return copy;
24
}
25
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度O(n), 空间复杂度O(n)
DFS: 时间复杂度O(n), 空间复杂度O(n)