Thursday, July 24, 2014

Clone Graph

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

BFS: 用一个HashMap存储已经生成过的点,避免重复生成相同的点。
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = 
        new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        queue.offer(node);
        map.put(node, new UndirectedGraphNode(node.label));
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();
            UndirectedGraphNode newcur = map.get(cur);
            for (UndirectedGraphNode neig : cur.neighbors) {
                //if contains, this node has already been searched
                if (!map.containsKey(neig)) {
                    map.put(neig, new UndirectedGraphNode(neig.label));
                    queue.offer(neig);
                }
                newcur.neighbors.add(map.get(neig));
            }
        }
        return map.get(node);
    }
}

No comments:

Post a Comment