Solving Clone Graph in Python: Step-by-Step Guide

Introduction to Clone Graph

The Clone Graph problem is a classic algorithmic challenge frequently encountered in coding interviews and real-world software development. Given a reference to a node in a connected, undirected graph, the task is to return a deep copy (clone) of the entire graph. Each node in the graph contains a value and a list of its neighbors.

While the problem statement sounds simple, it introduces several subtle complexities. Because graphs can contain cycles, a naive recursive copy will result in infinite loops. Additionally, since multiple nodes can share the same neighbor, you must ensure that the cloned graph preserves the exact same structure without duplicating nodes that should be identical.

Problem Statement

Formally, you are given a node class defined as follows:

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

You must implement a function cloneGraph(node) that takes a reference to a starting node and returns a deep copy of the entire graph. If the input node is None, you should return None.

Why Clone Graph Matters

Understanding how to clone a graph is important for several reasons:

• Interview relevance: It is one of the most common graph problems asked at companies like Google, Amazon, and Microsoft. It tests your understanding of graph traversal, hash maps, and recursion.
• Deep copy fundamentals: Many applications require duplicating complex object graphs without sharing references. Mastering this pattern helps in building immutable data structures and snapshot mechanisms.
• Cycle handling: The problem teaches you how to safely traverse cyclic structures, a skill that transfers to dependency resolution, serialization, and memory management tasks.
• Real-world use cases: Cloning graphs is useful in version control systems, game state snapshots, undo/redo features, and configuration management tools.

Understanding the Core Challenge

The main difficulty in cloning a graph is handling cycles and shared references. Consider a graph where node A points to node B, and node B points back to node A. If you simply recursively copy each neighbor, you will endlessly bounce between A and B.

The solution is to maintain a mapping between original nodes and their cloned counterparts. Before cloning a node, check the mapping. If the node has already been cloned, return the existing clone instead of creating a new one. This approach prevents infinite recursion and ensures that shared neighbors are preserved.

Visual Example

Imagine a simple graph with four nodes:

1 -- 2
|    |
4 -- 3

Node 1 has neighbors [2, 4], node 2 has neighbors [1, 3], node 3 has neighbors [2, 4], and node 4 has neighbors [1, 3]. When cloning, you must ensure that the cloned node 1 and cloned node 2 both reference the same cloned node 4, not two separate copies.

Solution 1: Depth-First Search (DFS) Approach

The DFS approach uses recursion combined with a hash map to track visited nodes. It is elegant and closely mirrors the natural structure of the graph.

Step-by-Step Explanation

• Create a dictionary called cloned that maps original nodes to their clones.
• If the input node is None, return None.
• If the node is already in the dictionary, return its clone immediately.
• Otherwise, create a new node with the same value.
• Add the mapping to the dictionary before recursing into neighbors to handle cycles.
• Recursively clone each neighbor and append it to the new node's neighbor list.
• Return the cloned node.

DFS Implementation

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


def cloneGraph(node):
    if node is None:
        return None

    cloned = {}

    def dfs(original):
        # If already cloned, return the existing clone
        if original in cloned:
            return cloned[original]

        # Create a new node with the same value
        copy = Node(original.val)
        cloned[original] = copy

        # Recursively clone all neighbors
        for neighbor in original.neighbors:
            copy.neighbors.append(dfs(neighbor))

        return copy

    return dfs(node)

How the DFS Solution Handles Cycles

The key insight is that the mapping cloned[original] = copy is set before the recursive calls to neighbors. This means that when a neighbor eventually points back to a node already being processed, the dictionary lookup will find it and return the in-progress clone. This breaks the cycle and prevents infinite recursion.

Solution 2: Breadth-First Search (BFS) Approach

For developers who prefer iterative solutions or want to avoid recursion depth limits on very large graphs, BFS is an excellent alternative. It uses a queue to process nodes level by level.

Step-by-Step Explanation

• Create a dictionary cloned to map original nodes to their clones.
• Create the clone of the starting node and add it to the dictionary.
• Initialize a queue with the original starting node.
• While the queue is not empty, dequeue a node.
• For each neighbor of the dequeued node, if it has not been cloned yet, create a clone and enqueue the original neighbor.
• Append the neighbor's clone to the current clone's neighbor list.

BFS Implementation

from collections import deque

def cloneGraph(node):
    if node is None:
        return None

    cloned = {}
    cloned[node] = Node(node.val)
    queue = deque([node])

    while queue:
        current = queue.popleft()

        for neighbor in current.neighbors:
            if neighbor not in cloned:
                cloned[neighbor] = Node(neighbor.val)
                queue.append(neighbor)

            cloned[current].neighbors.append(cloned[neighbor])

    return cloned[node]

Testing Your Solution

To verify that your clone function works correctly, you should build a test graph, clone it, and then compare the structures. Remember that the cloned nodes must be different objects from the originals, but the structure and values must match.

Test Code Example

def build_test_graph():
    # Build the graph: 1 -- 2 -- 3 -- 4 -- 1
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)

    node1.neighbors = [node2, node4]
    node2.neighbors = [node1, node3]
    node3.neighbors = [node2, node4]
    node4.neighbors = [node1, node3]

    return node1


def verify_clone(original, clone, visited=None):
    if visited is None:
        visited = set()

    if id(original) == id(clone):
        raise AssertionError("Clone shares reference with original!")

    if original.val != clone.val:
        raise AssertionError(f"Value mismatch: {original.val} vs {clone.val}")

    if len(original.neighbors) != len(clone.neighbors):
        raise AssertionError("Neighbor count mismatch")

    visited.add(id(original))

    for orig_n, clone_n in zip(original.neighbors, clone.neighbors):
        if id(original) not in visited:
            verify_clone(orig_n, clone_n, visited)


# Run the test
original_graph = build_test_graph()
cloned_graph = cloneGraph(original_graph)
verify_clone(original_graph, cloned_graph)
print("All tests passed!")

Time and Space Complexity Analysis

Both the DFS and BFS solutions have the same complexity characteristics:

• Time complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. Each node is visited exactly once, and each edge is traversed exactly once.
• Space complexity: O(V), because the hash map stores one entry per node, and in the worst case the recursion stack or queue holds up to V nodes.

These complexities are optimal because you must visit every node and edge at least once to produce a complete copy.

Best Practices

1. Always Use a Visited Map

Never attempt to clone a graph without a hash map or dictionary to track already-cloned nodes. Without it, cyclic graphs will cause infinite loops or stack overflow errors.

2. Register Clones Early

In the DFS approach, add the node to the mapping before recursing into its neighbors. This is critical for handling cycles correctly. If you add it after the recursive calls, back-edges will not find the clone and will create duplicates.

3. Prefer Iterative BFS for Large Graphs

Python has a default recursion limit of around 1000. For very deep or large graphs, the recursive DFS may hit this limit. The iterative BFS approach avoids this issue entirely. If you prefer DFS, you can convert it to an iterative version using an explicit stack.

4. Handle the Empty Graph Edge Case

Always check whether the input node is None at the beginning of your function. This is a common edge case in interviews and real-world usage.

5. Keep Node Construction Consistent

When creating cloned nodes, initialize them with the same default structure as the original class. If the original node class has additional attributes beyond val and neighbors, make sure to copy those as well.

Common Mistakes to Avoid

• Forgetting the visited map: This is the most common mistake and leads to infinite recursion on cyclic graphs.
• Registering clones too late: Adding the clone to the map after processing neighbors causes duplicate nodes for back-edges.
• Using shallow copy: Calling copy.copy() or copy.deepcopy() directly on a node will not correctly clone the entire graph structure in the way the problem expects.
• Ignoring the None input: Failing to handle None input causes AttributeError exceptions.

Extending to Directed Graphs

The same approach works for directed graphs with minimal modification. Since directed graphs have one-way edges, you simply follow the neighbor pointers as they are. The visited map still handles cycles, which are common in directed graphs as well.

def cloneDirectedGraph(node):
    if node is None:
        return None

    cloned = {}

    def dfs(original):
        if original in cloned:
            return cloned[original]

        copy = Node(original.val)
        cloned[original] = copy

        for neighbor in original.neighbors:
            copy.neighbors.append(dfs(neighbor))

        return copy

    return dfs(node)

Conclusion

Cloning a graph is a foundational problem that every developer should master. It combines graph traversal techniques with careful reference management, teaching lessons that extend far beyond the interview room. Whether you choose the recursive DFS approach for its elegance or the iterative BFS approach for its safety with large inputs, the core principle remains the same: use a hash map to track cloned nodes and register each clone before exploring its neighbors. By following the patterns and best practices outlined in this guide, you will be well-equipped to handle not only the Clone Graph problem but also any deep-copy scenario involving complex, interconnected data structures.