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 only one given 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

Main function

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return null;
    // Step 1 Find all vertices
    Set<UndirectedGraphNode> vertices = new HashSet<>();
    bfsExplore(node, vertices);
    // Step 2 Clone all vertices
    Map<UndirectedGraphNode, UndirectedGraphNode> origClone = new HashMap<>();
    for (UndirectedGraphNode v : vertices) {
        UndirectedGraphNode newVertex = new UndirectedGraphNode(v.label);
        origClone.put(v, newVertex);
    }
    // Step 3 Clone all edges
    for (UndirectedGraphNode v : origClone.keySet()) {
        for (UndirectedGraphNode ne : v.neighbors) {
            origClone.get(v).neighbors.add(origClone.get(ne));
        }
    }
    return origClone.get(node);
}

BFS explore

private void bfsExplore(UndirectedGraphNode node, Set<UndirectedGraphNode> vertices) {
    Queue<UndirectedGraphNode> queue = new LinkedList<>();
    queue.offer(node);
    vertices.add(node);

    while (!queue.isEmpty()) {
        UndirectedGraphNode current = queue.poll();
        for (UndirectedGraphNode ne : current.neighbors) {
            if (vertices.contains(ne)) {
                continue;
            }
            queue.offer(ne);
            vertices.add(ne);
        }
    }
}

DFS Approach

DFS is OP. Just beware of the possible (call) stack overflow. We want to DFS visit a node and return the this node and all its neighbors and neighbors' neighbors ...

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return null;
    Map<UndirectedGraphNode, UndirectedGraphNode> origClone = new HashMap<>();
    return dfsClone(node, origClone);
}

dfsClone will return the cloned node and its neighbors ...

private UndirectedGraphNode dfsClone(UndirectedGraphNode node, 
        Map<UndirectedGraphNode, UndirectedGraphNode> origClone) {
    // already visited
    if (origClone.get(node) != null) {
        return origClone.get(node);
    }
    // dfs
    UndirectedGraphNode cloneRoot = new UndirectedGraphNode(node.label);
    origClone.put(node, cloneRoot);
    for (UndirectedGraphNode  n : node.neighbors) {
        cloneRoot.neighbors.add(dfsClone(n, origClone));
    }
    // after the fully explored from this node
    return cloneRoot;   
}