Clone Graph

Question

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Node {
public int val;
public List neighbors;
}

Test case format:

For simplicity sake, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.

LeetCodeleetcode.com/problems/clone-graph

Solution

/*
@param: Node
@return: Node 
Algorithm: bfs遍历deep copy
*/
public Node cloneGraph(Node node) {
    if ( node == null ) return null;
    
    Map<Node, Node> map = new HashMap<>();
    Set<Node> set = new HashSet<>();
    Queue<Node> queue = new LinkedList<>();
    
    queue.offer(node);
    set.add(node);
    map.put(node, new Node(node.val, new ArrayList<>()));        
    while (!queue.isEmpty()){            
        Node cur = queue.poll();

        for ( Node temp : cur.neighbors){
            if ( !set.contains(temp)){
                set.add(temp);
                queue.offer(temp);
                map.put(temp,new Node(temp.val, new ArrayList<>()));
            }
            map.get(cur).neighbors.add(map.get(temp));
        }
    }        
    return map.get(node);         
}