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

Problem: Clone Graph

Explore how to perform a deep copy of a connected, undirected graph by implementing a breadth-first search approach. Learn to map original nodes to their clones using a hash map to avoid revisiting nodes and correctly replicate neighbor relationships. This lesson helps you implement and understand the cloning process along with its time and space complexity considerations.

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)

  • An array of its neighboring nodes (neighbors)

Examples

canvasAnimation-image
1 / 3

Try it yourself!

Implement your solution in the following coding playground.

Java
usercode > CloneGraph.java
import java.util.*;
public class CloneGraph{
    public static Node clone(Node root) {
        // Replace this placeholder return statement with your code
        return root;
    }
}
Clone Graph

Solution

Here is the updated explanation and solution steps with all code terms syntax highlighted:

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 HashMap (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 a new clone (if unseen) or retrieve the existing clone, then add it to the current cloned node's neighbors list.

Now, let's look at the solution steps below:

  • If the input node is null, return null immediately, since there is no graph to clone. ...