Clone Graph in Python (DFS Approach) – Deep Copy with Cycles Explained

Clone Graph Problem – DFS Based Solution in Python

The Clone Graph problem is a classic graph traversal question where the goal is to create a deep copy of a connected undirected graph. Each node contains a value and a list of its neighboring nodes.

The challenge lies in correctly handling cycles and repeated references without creating duplicate nodes or falling into infinite recursion.

---

Problem Overview

You are given a reference to a node in a connected undirected graph. Each node has:

• An integer value val
• A list of neighboring nodes neighbors

Your task is to return a deep copy of the entire graph.

---

Key Insight

Graphs can contain cycles, meaning a node can be revisited during traversal. To avoid cloning the same node multiple times, we use a hash map to keep track of already cloned nodes.

This solution uses Depth First Search (DFS) with a dictionary called visited:

• Key → Original node
• Value → Cloned node

---

DFS-Based Cloning Strategy

1. If the node is null, return None.
2. If the node is already cloned, return it from visited.
3. Create a new copy of the node.
4. Store the cloned node in visited.
5. Recursively clone all neighbors.

---

Python Implementation

from collections import deque
from typing import Optional

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        visited = {}

        def clone(node):
            if node in visited:
                return visited[node]

            copy = Node(node.val)
            visited[node] = copy

            for n in node.neighbors:
                copy.neighbors.append(clone(n))

            return copy

        return clone(node) if node else None

---

Why This Approach Works

• ✔ Prevents infinite loops caused by cycles
• ✔ Ensures each node is cloned exactly once
• ✔ Preserves the exact graph structure

---

Time and Space Complexity

Metric	Complexity
Time Complexity	O(V + E)
Space Complexity	O(V)

Where V is the number of vertices and E is the number of edges.

---

Reference Code

You can find the complete solution here:

https://github.com/RohitSingh-04/Python-Solutions/blob/main/LC133.py

This approach is highly recommended for interviews as it clearly demonstrates graph traversal, recursion, and handling of cyclic data structures.