[LintCode/LeetCode] Clone Graph [BFS/DFS]

NO IMAGE

Problem

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

return a deep copied graph.

Example

How we serialize an undirected graph.
Nodes are labeled uniquely.
As an example, consider the serialized graph {0,1,2#1,2#2,2}

Note

開始看這道題目的時候,沒有看懂queue和hashmap的作用。
複製一個無向圖,先分析圖的結構:label

public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
UndirectedGraphNode root = new UndirectedGraphNode(node.label);//複製根節點
Queue<UndirectedGraphNode> queue = new LinkedList<>();
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
queue.offer(node);//queue放入根結點
map.put(node, root);//map放入根結點和它的複製結點
while (!queue.isEmpty()) {
UndirectedGraphNode cur = queue.poll();//取出queue中(同一層)的結點進行BFS
for (UndirectedGraphNode n: cur.neighbors) {
//對沒有複製過的結點進行復制,並將這個結點放入queue
if (!map.containsKey(n)) {
map.put(n, new UndirectedGraphNode(n.label));
queue.offer(n);
}
//連線複製結點和複製neighbor結點
map.get(cur).neighbors.add(map.get(n));
}
}
return root;
}
}

DFS


public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
return cloneNode(node, map);
}
private UndirectedGraphNode cloneNode(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
if (node == null) return node;
if (map.containsKey(node)) {
return map.get(node);
} else {
UndirectedGraphNode nodeCopy = new UndirectedGraphNode(node.label);
map.put(node, nodeCopy);
for (UndirectedGraphNode child : node.neighbors) {
nodeCopy.neighbors.add(cloneNode(child, map));
}
return nodeCopy;
}
}
}