Clone Graph

Question (LC.133)

Given a node in undirected graph, clone this graph.

Return a node in the cloned (deep copy) graph.

Analysis

Well we have to assume this graph is connected. Otherwise, there's no way to get to all vertices from the given vertex.

BFS Approach

The question wants you to recreate an adjacency list with the given start node.

Step 1 explore the whole graph by BFS
to find all the vertices first
Step 2 Clone all vertices (label)
Map<oldVertex, clonedVertex>
Step 3 Clone all edges (neighbors)
for each node copy the edge

Code

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return null;
    // Step 1 Find all vertices
    Set<UndirectedGraphNode> verSet = new HashSet<>();
    exploreGraph(node, verSet);
    // Step 2 Deep copy nodes
    Map<UndirectedGraphNode, UndirectedGraphNode> mapOC = new HashMap<>();
    for (UndirectedGraphNode org : verSet) {
        UndirectedGraphNode copy = new UndirectedGraphNode(org.label);
        mapOC.put(org, copy);
    }
    // Step 3 Copy all the edges
    for (UndirectedGraphNode org : mapOC.keySet())
        for (UndirectedGraphNode orgEdge : org.neighbors)     
            mapOC.get(org).neighbors.add(mapOC.get(orgEdge));
    return mapOC.get(node);
}

Graph explore with DFS

private void exploreGraph(UndirectedGraphNode start, Set<UndirectedGraphNode> verSet) {
    // stop search
    if (verSet.contains(start)) {
        return;
    }
    // previsit
    verSet.add(start);
    // depth first search
    for (UndirectedGraphNode neighbor : start.neighbors) {
        exploreGraph(neighbor, verSet);
    }
    // postvisit do nothing
}

Graph explore with BFS

private void exploreGraph(UndirectedGraphNode start, Set<UndirectedGraphNode> verSet) {
    // init queue
    Queue<UndirectedGraphNode> queue = new LinkedList<>();
    queue.offer(start);
    verSet.add(start);
    // bfs
    UndirectedGraphNode current;
    while (!queue.isEmpty()) {
        current = queue.poll();
        for (UndirectedGraphNode neighbor : current.neighbors) {
            if (!verSet.contains(neighbor)) {
                queue.offer(neighbor);
                verSet.add(neighbor);
            }
        }
    }
}

One-Go Approach

DFS is shorter to write because of the power of recursion. Just beware of the possible (call) stack overflow. We can intelligently utilize all the properties of DFS to produce the concise code below. During the previsit phrase, we can deep copy all the vertices. During backtracking, we can copy all the outgoing edges (neighbors) for that node using the base case to get the reference. When we are finished with the current node, we can return it to the previous node as a reference to its outgoing edge.

public UndirectedGraphNode cloneGraph(UndirectedGraphNode start) {
    if (start == null) return start;
    Map<UndirectedGraphNode, UndirectedGraphNode> mapOC = new HashMap<>();
    return cloneDFS(start, mapOC);
}

private UndirectedGraphNode cloneDFS(UndirectedGraphNode current, 
                 Map<UndirectedGraphNode, UndirectedGraphNode> mapOC) {
    // base case 
    if (mapOC.containsKey(current)) {
        return mapOC.get(current); 
    }
    // pre visit deep copy the vertex
    UndirectedGraphNode currentCopy = new UndirectedGraphNode(current.label);
    mapOC.put(current, currentCopy);
    // DFS
    for (UndirectedGraphNode neighbor : current.neighbors) {
        // backtrack to copy all the outgoing edges
        currentCopy.neighbors.add(cloneDFS(neighbor, mapOC));
    }
    // post visit return the resolved vertex
    return mapOC.get(current);
}