mediumGraphs & BFS/DFS

Clone Graph

Deep-copy a connected undirected graph with vertices labeled 1 through n. Preserve every edge while creating new node objects.

LeetCode ↗

Work through the cases

3 examples

Input notation

n on line 1; then n adjacency-list lines, in vertex order from 1 through n. Use - for a vertex without neighbors.

Expected result

The copied graph in the same format. Check in your code that all node objects are new.

Case 1

Input

Expected output

Case 2

Input

1
-

Expected output

1
-

Case 3

Input

2
2
1

Expected output

2
2
1

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Deep-copy a connected undirected graph; values are unique and n ≤ 100. Copying values is not enough: neighbor pointers must refer to the new nodes, and cycles would loop if we recurse blindly. A map from original node to clone does it. On the first visit we create the clone and recurse on neighbors; a later visit returns the existing clone, which cuts cycles.

We use a hash table g to record the correspondence between each node in the original graph and its copy, and then perform depth-first search.

We define the function dfs(node), which returns the copy of the node. The process of dfs(node) is as follows:

- If node is null, then the return value of dfs(node) is null. - If node is in g, then the return value of dfs(node) is g[node]. - Otherwise, we create a new node cloned and set the value of g[node] to cloned. Then, we traverse all the neighbor nodes nxt of node and add dfs(nxt) to the neighbor list of cloned. - Finally, return cloned.

In the main function, we return dfs(node).

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    private Map<Node, Node> g = new HashMap<>();

    public Node cloneGraph(Node node) {
        return dfs(node);
    }

    private Node dfs(Node node) {
        if (node == null) {
            return null;
        }
        Node cloned = g.get(node);
        if (cloned == null) {
            cloned = new Node(node.val);
            g.put(node, cloned);
            for (Node nxt : node.neighbors) {
                cloned.neighbors.add(dfs(nxt));
            }
        }
        return cloned;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.