Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms

Problem: Clone Graph

Explore how to clone a connected, undirected graph by applying breadth-first search to traverse nodes and create deep copies. Learn to use a hash map to track cloned nodes and replicate neighbor relationships efficiently, ensuring you understand the process, time, and space complexity involved in graph cloning with Python.

We'll cover the following...

Statement

You are given a reference to a node in a connected, undirected graph. Your task is to return a deep copy (clone) of the entire graph.

Each node in the graph contains:

  • An integer value (data)

  • A list of its neighboring nodes (neighbors)

Examples

canvasAnimation-image
1 / 3

Try it yourself!

Implement your solution in the following coding playground.

Python
usercode > clone_graph.py
# class Node:
#   def __init__(self, d):
#     self.data = d
#     self.neighbors = []
from Node import *
def cloneGraph(root):
    
    # Replace this placeholder return statement with your code
    return root
Clone Graph

Solution

The core idea behind cloning a connected, undirected graph is to traverse the original graph using breadth-first search (BFS) while simultaneously building a copy of each node and replicating the neighbor relationships. We use a hash map (cloneMap) that maps each original node to its corresponding cloned node. This serves two purposes: it tracks which nodes have already been visited (preventing infinite loops in the undirected graph) and provides constant-time access to the cloned counterpart of any original node when wiring up neighbor lists. Starting from the given node, we explore level by level. For every neighbor encountered, we either create ...