Leetcode - Clone Graph

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