LeetCode 133: Clone Graph Solution in Python – A Step-by-Step Guide

What Is LeetCode 133: Clone Graph?

In LeetCode 133: Clone Graph, you’re given a reference to a node in an undirected graph, represented as an adjacency list where each Node has a val (1 to 100) and a list of neighbors. Your task is to return a deep copy of the graph, meaning a new graph with identical structure and values, but distinct objects. For example, with a graph [[2,4],[1,3],[2,4],[1,3]] (nodes 1, 2, 3, 4 with connections), you return a new graph mirroring it.

Problem Statement

• Input: A Node object (reference to a node in the graph).
• Output: A Node object—the root of the cloned graph.
• Rules:
• Graph is undirected (edges are bidirectional).
• Graph may have cycles.
• No duplicate edges or self-loops.
• Return a deep copy (new objects, same structure).

Constraints

• Number of nodes: 0 <= n <= 100
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• No repeated edges or self-loops.

Examples

• Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
• Output: A new graph with same structure (nodes 1, 2, 3, 4 connected as input).
• Why: Clones nodes 1→2,4, 2→1,3, etc.
• Input: adjList = [[]]
• Output: A single node with no neighbors.
• Why: One node, no connections.
• Input: adjList = []
• Output: None
• Why: Empty graph.

Understanding the Problem: Copying the Graph

To solve LeetCode 133: Clone Graph in Python, we need to create a deep copy of an undirected graph, duplicating each node and its neighbor list while preserving the structure, including cycles. A naive approach—copying without tracking—could lead to infinite loops with cycles or duplicate nodes. Instead, we’ll use traversal with a mapping to track cloned nodes:

• Best Solution (DFS with Hash Map): O(n) time, O(n) space—recursive and efficient.
• Alternative Solution (BFS with Queue): O(n) time, O(n) space—iterative and queue-based.

Let’s dive into the Best Solution—DFS with a hash map—and break it down step-by-step.

Best Solution: DFS with Hash Map

Why This Is the Best Solution

The DFS with hash map approach is the top choice because it’s both efficient—O(n) time and O(n) space—and naturally suits the recursive nature of graph traversal. It uses a hash map to track cloned nodes, avoiding cycles and redundant copies, while building the graph depth-first. It’s like exploring the friend network, copying each person as you go, and linking them to their buddies—elegant and fast!

How It Works

Here’s the strategy:

• Step 1: Hash Map:
• visited: Maps original node to its clone.
• Step 2: DFS Function:
• clone(node): Returns clone of node.
• If node in visited, return its clone.
• Create new node with node.val.
• Recursively clone and append neighbors.
• Step 3: Start:
• Call clone on input node, handle null case.

Step-by-Step Example

Example: adjList = [[2,4],[1,3],[2,4],[1,3]]

• Graph:

1 -- 2 | | 4 -- 3

• Initial Call: clone(node1), visited = {}.
• Node 1:
• Not in visited, create clone1 (val=1).
• visited[1] = clone1.
• Neighbors: 2, 4.
• Node 2:
• Create clone2 (val=2), visited[2] = clone2.
• Neighbors: 1, 3.
• Node 1: Already in visited, append clone1 to clone2.neighbors.
• Node 3: Create clone3 (val=3), visited[3] = clone3.
• Node 3 neighbors: 2, 4.
• Node 2: Append clone2.
• Node 4: Create clone4 (val=4), visited[4] = clone4.
• Node 4 neighbors: 1, 3.
• Node 1: Append clone1.
• Node 3: Append clone3.
• Append clone4 to clone3.neighbors.
• Append clone3 to clone2.neighbors.
• Node 4:
• Already in visited, append clone4 to clone1.neighbors.
• Node 1:
• Append clone2 to clone1.neighbors.
• Result: Cloned graph mirroring original.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        # Step 1: Handle null case and initialize visited
        if not node:
            return None
        visited = {}

        # Step 2: DFS helper function
        def clone(node):
            # If node already cloned, return its clone
            if node in visited:
                return visited[node]

            # Create new node with same value
            clone_node = Node(node.val)
            visited[node] = clone_node

            # Recursively clone neighbors
            for neighbor in node.neighbors:
                clone_node.neighbors.append(clone(neighbor))

            return clone_node

        # Step 3: Start cloning
        return clone(node)

• Line 4-6: Return None for empty graph, initialize hash map.
• Line 9-19: DFS helper:
• Line 11-12: Return existing clone if visited.
• Line 15-16: Create and map new node.
• Line 18-19: Clone and append neighbors.
• Line 22: Start from input node.
• Time Complexity: O(n)—each node and edge visited once.
• Space Complexity: O(n)—hash map and recursion stack.

This is a graph-copying maestro!

Alternative Solution: BFS with Queue

Why an Alternative Approach?

The BFS with queue approach offers an iterative alternative—O(n) time, O(n) space—using a queue to process nodes level by level. It’s useful for avoiding recursion stack limits and provides a breadth-first perspective. It’s like copying the friend network layer by layer, ensuring everyone’s linked—methodical and explicit!

How It Works

• Step 1: Queue starting node, use hash map.
• Step 2: BFS to clone nodes and neighbors.
• Step 3: Return root of cloned graph.

Step-by-Step Example

Example: adjList = [[2,4],[1,3],[2,4],[1,3]]

• Initialize: queue = [node1], visited = {node1: clone1}.
• Node 1:
• Clone1 (val=1), neighbors: 2, 4.
• Queue: [node2, node4].
• visited[node2] = clone2, visited[node4] = clone4.
• Append clone2, clone4 to clone1.neighbors.
• Node 2:
• Clone2 (val=2), neighbors: 1, 3.
• Node 1: Append clone1.
• Node 3: visited[node3] = clone3, append clone3, queue: [node4, node3].
• Node 4:
• Clone4 (val=4), neighbors: 1, 3.
• Append clone1, clone3.
• Node 3:
• Clone3 (val=3), neighbors: 2, 4.
• Append clone2, clone4.
• Result: Cloned graph.

Code for BFS Approach

Copy codeclass Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None

        # Step 1: Initialize queue and visited
        queue = deque([node])
        visited = {node: Node(node.val)}

        # Step 2: BFS to clone
        while queue:
            current = queue.popleft()
            clone_node = visited[current]

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

        # Step 3: Return root
        return visited[node]

• Line 4-6: Handle empty graph.
• Line 9-10: Queue root, map to clone.
• Line 13-19: BFS loop:
• Line 15-19: Clone unvisited neighbors, link them.
• Time Complexity: O(n)—each node processed once.
• Space Complexity: O(n)—queue and hash map.

It’s a queue-driven duplicator!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n) time, O(n) space, recursive and concise.
• Cons: Recursion stack (O(n) worst case).
• BFS (Alternative):
• Pros: O(n) time, O(n) space, iterative control.
• Cons: Slightly more verbose.

DFS wins for simplicity.

Additional Examples and Edge Cases

• [[]]: Single node cloned.
• [[2],[1]]: Two nodes connected.
• []: None.

Both handle these perfectly.

Complexity Breakdown

• DFS: Time O(n), Space O(n).
• BFS: Time O(n), Space O(n).

DFS’s elegance shines.

Key Takeaways

• DFS: Dive and clone!
• BFS: Queue and copy!
• Cloning: Track with a map.
• Python Tip: Dicts optimize—see [Python Basics](/python/basics).

Final Thoughts: Duplicate the Network

LeetCode 133: Clone Graph in Python is a graph-copying adventure. The DFS approach clones with flair, while BFS offers a steady alternative. Want more graph fun? Try LeetCode 207: Course Schedule or LeetCode 200: Number of Islands. Ready to clone? Head to Solve LeetCode 133 on LeetCode and copy that graph today!