Introduction

Clone Graph is one of the most important Graph Traversal interview problems.

You are given:

Connected Graph

Goal:

Create a deep copy of the graph.

Requirements:

New Nodes
New Edges
Same Structure

Example

 1 -- 2 |    |
 4 -- 3

Output:

Cloned Graph1 -- 2
|    |
4 -- 3

Key Observation

Each original node should map to:

Exactly one cloned node.

Use:

Hash Map
original → clone

to avoid:

Duplicate nodes Infinite loops

Algorithm

1. Create clone node.
2. Store in map.
3. Traverse neighbors.
4. Clone neighbors.
5. Connect cloned edges.

DryRun

Input:

1 → [2,4]
2 → [1,3]
3 → [2,4]
4 → [1,3]

Mapping:

1 → clone1
2 → clone2
3 → clone3
4 → clone4

Answer:

Deep Copy Created

Approach : DFS

Explanation

For every node:

  1. Check map.
  2. If already cloned, return clone.
  3. Create new clone.
  4. Clone all neighbors.
  5. Connect neighbors.

Practice

Complexity Analysis

DFS
Time Complexity: O(V + E)
Space Complexity: O(V)

BFS
Time Complexity: O(V + E)
Space Complexity: O(V)

Why This Problem is Important

  • Graph Traversal
  • DFS
  • BFS
  • Hash Maps
  • Deep Copy Concepts

Common Beginner Mistakes

  • Creating duplicate nodes
  • Forgetting visited map
  • Infinite recursion
  • Shallow copying
  • Missing edge connections

Interview Tip

Always explain:

One Original Node = One Clone Node

Use a map to maintain this relationship.

Related Questions

  • Number of Islands
  • Course Schedule
  • Graph Valid Tree
  • Number of Connected Components
  • Pacific Atlantic Water Flow

Final Takeaway

Clone Graph is the foundation of graph copying problems.

It teaches:

  • DFS
  • BFS
  • Graph Traversal
  • Deep Copy Techniques

Mastering Clone Graph makes advanced graph cloning and traversal questions significantly easier.