133. Clone Graph

Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors.

Analysis:

Simply traverse the graph BFS using a queue. Have a map to store mapping relation between old nodes and new nodes. And have a hashSet to store visited nodes.

Complexity:

Time: O(N)

Space: O(N)

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;
        }
        Set<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
        Map<UndirectedGraphNode, UndirectedGraphNode> nodeMap = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        Deque<UndirectedGraphNode> que = new LinkedList<UndirectedGraphNode>();
        que.offer(node);
        while(!que.isEmpty())
        {
            UndirectedGraphNode cur = que.poll();
            if(!visited.contains(cur))
            {
                visited.add(cur);
                UndirectedGraphNode newCur = nodeMap.get(cur) == null ? new UndirectedGraphNode(cur.label) : nodeMap.get(cur);
                nodeMap.put(cur, newCur);
                for(UndirectedGraphNode neighbor : cur.neighbors)
                {
                    UndirectedGraphNode newNeighbor = nodeMap.get(neighbor);
                    if(newNeighbor == null)
                    {
                        newNeighbor = new UndirectedGraphNode(neighbor.label);
                        nodeMap.put(neighbor, newNeighbor);
                    }
                    newCur.neighbors.add(newNeighbor);
                    que.offer(neighbor);
                }
            }
        }
        return nodeMap.get(node);
    }
}