My code:
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null)
return null;
/** tracker the origin node and the copied node (map) */
HashMap<UndirectedGraphNode, UndirectedGraphNode> tracker = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
/** for bfs */
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
queue.offer(node);
while (!queue.isEmpty()) {
UndirectedGraphNode temp = queue.poll();
UndirectedGraphNode copy;
/** copy this node if necessary*/
if (!tracker.containsKey(temp)) {
copy = new UndirectedGraphNode(temp.label);
tracker.put(temp, copy);
}
else {
copy = tracker.get(temp);
}
/** copy the whole neighbors list */
ArrayList<UndirectedGraphNode> copyList = new ArrayList<UndirectedGraphNode>();
/**
* if already exists in tracker, this node has already been copied or is waiting to be copied in the queue
* if not exists in tracker, this node has not been copied and is not in the queue
*/
for (UndirectedGraphNode elem : temp.neighbors) {
if (!tracker.containsKey(elem)) {
UndirectedGraphNode copyElem = new UndirectedGraphNode(elem.label);
copyList.add(copyElem);
tracker.put(elem, copyElem);
queue.offer(elem);
}
else {
copyList.add(tracker.get(elem));
}
}
copy.neighbors = copyList;
}
return tracker.get(node);
}
}
这道题目也是好几天前做的了，基本忘了思路。
是用bfs来复制整个graph的。然后把已经复制好的放入HashMap中。
没有复制好的，要么在队列中，要么不在队列中，并且不在HashMap中。
每次就是把每个结点对应的相邻结点组成的ArrayList做出来。那么有两种情况。
如果相邻结点，不在HashMap中，那么就彻底的复制下该结点，塞入ArrayList中，同时放入HashMap中。并且插入队列中。
如果在，那么就取出来，塞入ArrayList中。
访问每个结点时也是这么操作。看看在不在HashMap中，如果是，就没必要再深拷贝一下了。
然后队列中的每个结点都必须访问，复制。
队列保证队列中的元素，必须是未被拷贝并访问过的。
这道题目我做出来的时候还多用了一个HashSet,所以时间慢了很多。然后后来看了答案，精简之后，发现可以用HashMap完成两者的工作，于是，速度大大得讲了下来！
Anyway, Good luck, Richardo!
思路还是比较明显的，dfs或者bfs
BFS:
My code:
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
Queue<UndirectedGraphNode> qm = new LinkedList<UndirectedGraphNode>();
UndirectedGraphNode root = node;
UndirectedGraphNode rootm = clone(root);
map.put(root, rootm);
q.offer(root);
qm.offer(rootm);
while (!q.isEmpty()) {
UndirectedGraphNode curr = q.poll();
UndirectedGraphNode currm = qm.poll();
for (UndirectedGraphNode nei : curr.neighbors) {
if (map.containsKey(nei)) {
currm.neighbors.add(map.get(nei));
}
else {
UndirectedGraphNode neim = clone(nei);
currm.neighbors.add(neim);
map.put(nei, neim);
q.offer(nei);
qm.offer(neim);
}
}
}
return rootm;
}
private UndirectedGraphNode clone(UndirectedGraphNode node) {
return new UndirectedGraphNode(node.label);
}
}
搞两个队列追踪原结点和镜像结点。搞一个hashmap存储已经copy过的结点。
然后每次从队列拿出第一个元素，遍历他的邻居。
如果已经存在过map中，说明已经copy过了，就直接拿来用，不用再塞进队列了。
如果没有存在，那就copy下，然后塞进队列。
从队列里面出来的每个元素，都是之前没copy过的，这次操作结束后，就会全部copy好。
差不多就这么个思路。
DFS:
My code:
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
return helper(node);
}
private UndirectedGraphNode helper(UndirectedGraphNode node) {
UndirectedGraphNode nodem = clone(node);
map.put(node, nodem);
for (UndirectedGraphNode nei : node.neighbors) {
if (!map.containsKey(nei)) {
UndirectedGraphNode neim = helper(nei);
nodem.neighbors.add(neim);
}
else {
nodem.neighbors.add(map.get(nei));
}
}
return nodem;
}
private UndirectedGraphNode clone(UndirectedGraphNode node) {
return new UndirectedGraphNode(node.label);
}
}
这个思路就比较直观了。
Anyway, Good luck, Richardo! -- 09/09/2016
