/
Solution.java
71 lines (64 loc) · 2.38 KB
/
Solution.java
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
* Time : O(N); Space : O(N)
* @tag : Depth-first Search; Breadth-first Search; Graph
* @by : Steven Cooks
* @date: Jun 26, 2015
*******************************************************************************
* Description:
*
* Clone an undirected graph. Each node in the graph contains a label and
* a list of its neighbors.
*
* Visually, the graph looks like the following:
*
* 1
* / \
* / \
* 0 --- 2
* / \
* \_/
*******************************************************************************
* {@link https://leetcode.com/problems/clone-graph/ }
*/
package _133_CloneGraph;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import com.leetcode.UndirectedGraphNode;
/** see test {@link _133_CloneGraph.SolutionTest } */
public class Solution {
// BFS version, see also
// For each node, building neighbors for its corresponding copy node.
// for not copied neighbor, push it to the queue;
// for copied neighbor, get its copy from the cloneMap
// P.S. don't forget to update map when adding node into queue
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return node;
}
UndirectedGraphNode nodeCopy = new UndirectedGraphNode(node.label);
// <Node from given graph, Node that is cloned>
Map<UndirectedGraphNode, UndirectedGraphNode> cloneMap = new HashMap<>();
cloneMap.put(node, nodeCopy);
Queue<UndirectedGraphNode> nodesToCopy = new LinkedList<>();
nodesToCopy.add(node);
while (!nodesToCopy.isEmpty()) {
UndirectedGraphNode graphNode = nodesToCopy.poll();
// clone all neighbors of graph node
for (UndirectedGraphNode neighbour: graphNode.neighbors) {
UndirectedGraphNode neighbourCopy;
if (cloneMap.containsKey(neighbour)) {
neighbourCopy = cloneMap.get(neighbour);
} else {
// for neighbor that has not been copied
neighbourCopy = new UndirectedGraphNode(neighbour.label);
cloneMap.put(neighbour, neighbourCopy);
nodesToCopy.add(neighbour);
}
cloneMap.get(graphNode).neighbors.add(neighbourCopy);
}
}
return nodeCopy;
}
}