23 minute read

“Creating a deep copy of a graph structure.”

TL;DR

Clone Graph requires deep copying a graph that may contain cycles. The essential technique is a hash map mapping original nodes to clones, which prevents infinite recursion and duplicate nodes. Both DFS (recursive) and BFS (iterative) solutions run in O(N+E) time and O(N) space. DFS is more concise; BFS avoids stack overflow on deep graphs. The pattern extends to cloning directed graphs, weighted graphs, and graphs with random pointers. For related graph traversal, see Evaluate Division or Surrounded Regions.

1. Problem Statement

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains:

  • A value (val)
  • A list of its neighbors (neighbors)
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

Example:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
...

Constraints:

  • The number of nodes in the graph is in the range [0, 100].
  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • There are no repeated edges and no self-loops in the graph.
  • The Graph is connected and all nodes can be visited starting from the given node.

2. The Cloning Challenge

Why is this hard?

Unlike cloning a tree or linked list (which are acyclic), graphs can have cycles. Naively copying nodes will lead to:

  1. Infinite recursion (if using DFS without tracking visited nodes).
  2. Duplicate nodes (creating multiple copies of the same node).

Key Insight: We need a mapping from original nodes to their clones: {original_node: cloned_node}.

3. DFS Solution

Algorithm:

  1. Use a hash map visited to store {original_node: cloned_node}.
  2. Start DFS from the given node.
  3. For each node:
    • If already cloned (in visited), return the clone.
    • Otherwise, create a new clone.
    • Recursively clone all neighbors.
    • Add cloned neighbors to the clone’s neighbor list.
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None

            # Hash map to store original -> clone mapping
            visited = {}

    def dfs(node):
        # If already cloned, return the clone
        if node in visited:
            return visited[node]

            # Create a new clone
            clone = Node(node.val)
            visited[node] = clone

            # Clone all neighbors
            for neighbor in node.neighbors:
                clone.neighbors.append(dfs(neighbor))

                return clone

                return dfs(node)

Time Complexity: O(N + E), where N is the number of nodes and E is the number of edges.

  • We visit each node once.
  • We traverse each edge once (to clone the neighbor relationship).

Space Complexity: O(N)

  • Hash map stores N entries.
  • Recursion stack can go up to O(N) in the worst case (long chain).

4. BFS Solution

Algorithm:

  1. Use a queue for BFS traversal.
  2. Use a hash map visited to track cloned nodes.
  3. Start by cloning the root node and adding it to the queue.
  4. For each node in the queue:
    • For each neighbor:
    • If not cloned, create a clone and add to queue.
    • Add the cloned neighbor to the current clone’s neighbor list.
from collections import deque

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

            # Clone the starting node
            visited = {node: Node(node.val)}
            queue = deque([node])

            while queue:
                current = queue.popleft()

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

                        # Add the cloned neighbor to the current clone's neighbors
                        visited[current].neighbors.append(visited[neighbor])

                        return visited[node]

Comparison: DFS vs BFS

  • DFS: More intuitive for recursive thinkers. Uses recursion stack.
  • BFS: Iterative, more explicit queue management. Better for very deep graphs (avoids stack overflow).

5. Deep Dive: Handling Disconnected Graphs

The problem states the graph is connected. But what if it’s not?

Strategy:

  • The function receives only one node. We can only clone the connected component containing that node.
  • To clone an entire disconnected graph, we’d need a list of all nodes or an adjacency list.
def cloneDisconnectedGraph(nodes: List['Node']) -> List['Node']:
    visited = {}

def dfs(node):
    if node in visited:
        return visited[node]
        clone = Node(node.val)
        visited[node] = clone
        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))
            return clone

            # Clone each connected component
            cloned_nodes = []
            for node in nodes:
                if node not in visited:
                    cloned_nodes.append(dfs(node))

                    return cloned_nodes

6. Deep Dive: Directed Graphs

The problem specifies an undirected graph. For directed graphs, the approach is identical, we still clone nodes and their outgoing edges.

class DirectedNode:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

    def cloneDirectedGraph(node: 'DirectedNode') -> 'DirectedNode':
        if not node:
            return None

            visited = {}

    def dfs(n):
        if n in visited:
            return visited[n]
            clone = DirectedNode(n.val)
            visited[n] = clone
            for neighbor in n.neighbors:
                clone.neighbors.append(dfs(neighbor))
                return clone

                return dfs(node)

The only difference: edges are directional, so we only clone outgoing edges.

7. Deep Dive: Weighted Graphs

If the graph has weighted edges, we need to store edge weights.

Modified Node:

class WeightedNode:
    def __init__(self, val=0):
        self.val = val
        self.edges = [] # List of (neighbor, weight) tuples

    def cloneWeightedGraph(node: 'WeightedNode') -> 'WeightedNode':
        if not node:
            return None

            visited = {}

    def dfs(n):
        if n in visited:
            return visited[n]
            clone = WeightedNode(n.val)
            visited[n] = clone
            for neighbor, weight in n.edges:
                clone.edges.append((dfs(neighbor), weight))
                return clone

                return dfs(node)

8. Deep Dive: Cloning with Additional Attributes

What if each node has complex attributes (e.g., metadata, timestamps)?

class ComplexNode:
    def __init__(self, val=0, metadata=None, neighbors=None):
        self.val = val
        self.metadata = metadata or {}
        self.neighbors = neighbors or []

    def cloneComplexGraph(node: 'ComplexNode') -> 'ComplexNode':
        if not node:
            return None

            visited = {}

    def dfs(n):
        if n in visited:
            return visited[n]

            # Deep copy metadata (if it contains nested structures)
            import copy
            clone = ComplexNode(n.val, copy.deepcopy(n.metadata))
            visited[n] = clone

            for neighbor in n.neighbors:
                clone.neighbors.append(dfs(neighbor))

                return clone

                return dfs(node)

Warning: Use copy.deepcopy carefully, it can be slow for large objects.

9. Deep Dive: Serialization and Deserialization

Problem: Serialize a graph to a string, then deserialize it back.

Serialization Format (Adjacency List):

"1#2,4|2#1,3|3#2,4|4#1,3"
  • 1#2,4 means Node 1 has neighbors 2 and 4.
  • | separates nodes.
def serialize(node: 'Node') -> str:
    if not node:
        return ""

        visited = set()
        adj_list = []

    def dfs(n):
        if n.val in visited:
            return
            visited.add(n.val)
            neighbors_str = ','.join(str(neighbor.val) for neighbor in n.neighbors)
            adj_list.append(f"{n.val}#{neighbors_str}")
            for neighbor in n.neighbors:
                dfs(neighbor)

                dfs(node)
                return "|".join(adj_list)

    def deserialize(data: str) -> 'Node':
        if not data:
            return None

            # Parse the string
            nodes = {}
            for entry in data.split('|'):
                val, neighbors_str = entry.split('#')
                val = int(val)
                if val not in nodes:
                    nodes[val] = Node(val)

                    # Build edges
                    for entry in data.split('|'):
                        val, neighbors_str = entry.split('#')
                        val = int(val)
                        if neighbors_str:
                            for neighbor_val in neighbors_str.split(','):
                                neighbor_val = int(neighbor_val)
                                nodes[val].neighbors.append(nodes[neighbor_val])

                                # Return the first node (assuming node 1 is the starting point)
                                return nodes[min(nodes.keys())]

10. Real-World Applications

1. Social Networks:

  • Cloning a user’s friend graph for offline analysis.
  • Creating snapshots for A/B testing (test algorithm changes on a cloned graph).

2. Distributed Systems:

  • Replicating a service dependency graph across data centers.
  • Each region has a clone of the service topology.

3. Version Control (Git):

  • Git clones entire repository graphs (commits, branches).
  • Each commit is a node, parent commits are neighbors.

4. Game State:

  • Cloning game board state for AI lookahead (minimax algorithm).
  • The AI simulates moves on a cloned board without affecting the real game.

11. Edge Cases to Handle

1. Empty Graph:

assert cloneGraph(None) == None

2. Single Node (No Neighbors):

node = Node(1)
clone = cloneGraph(node)
assert clone.val == 1
assert clone.neighbors == []
assert clone is not node # Different object

3. Cycle (Two Nodes):

node1 = Node(1)
node2 = Node(2)
node1.neighbors = [node2]
node2.neighbors = [node1]

clone = cloneGraph(node1)
assert clone.val == 1
assert clone.neighbors[0].val == 2
assert clone.neighbors[0].neighbors[0] is clone # Points back to itself

4. Self-Loop:

node = Node(1)
node.neighbors = [node]

clone = cloneGraph(node)
assert clone.neighbors[0] is clone

12. Common Mistakes

Mistake 1: Not Using a Hash Map

# WRONG: Creates infinite recursion
def cloneGraphWrong(node):
    if not node:
        return None
        clone = Node(node.val)
        for neighbor in node.neighbors:
            clone.neighbors.append(cloneGraphWrong(neighbor)) # Infinite loop!
            return clone

Mistake 2: Shallow Copy

# WRONG: Shallow copy shares neighbor references
def cloneGraphWrong(node):
    clone = Node(node.val)
    clone.neighbors = node.neighbors # Same list object!
    return clone

Mistake 3: Forgetting to Check visited Before Cloning

# WRONG: Creates duplicate clones
def cloneGraphWrong(node, visited={}):
    clone = Node(node.val)
    # Missing: if node in visited: return visited[node]
    visited[node] = clone
    for neighbor in node.neighbors:
        clone.neighbors.append(cloneGraphWrong(neighbor, visited))
        return clone

Implementation in Other Languages

C++:

class Solution {
public:
 unordered_map<Node*, Node*> visited;
 
 Node* cloneGraph(Node* node) {
 if (!node) return nullptr;
 if (visited.count(node)) return visited[node];
 
 Node* clone = new Node(node->val);
 visited[node] = clone;
 
 for (Node* neighbor : node->neighbors) {
 clone->neighbors.push_back(cloneGraph(neighbor));
 }
 
 return clone;
 }
};

Java:

class Solution {
 private Map<Node, Node> visited = new HashMap<>();
 
 public Node cloneGraph(Node node) {
 if (node == null) return null;
 if (visited.containsKey(node)) return visited.get(node);
 
 Node clone = new Node(node.val);
 visited.put(node, clone);
 
 for (Node neighbor : node.neighbors) {
 clone.neighbors.add(cloneGraph(neighbor));
 }
 
 return clone;
 }
}

Top Interview Questions

Q1: What’s the difference between shallow copy and deep copy? Answer:

  • Shallow Copy: Copies the object but shares references to nested objects (e.g., neighbors list).
  • Deep Copy: Recursively copies all nested objects. Each cloned node has its own neighbor list.

Q2: How would you verify that the clone is correct? Answer:

  1. Structural Check: BFS/DFS both graphs, verify same connectivity.
  2. Identity Check: Ensure clone is not original (different objects).
  3. Value Check: Verify clone.val == original.val for all nodes.
def verifyClone(original, clone):
    visited_orig = set()
    visited_clone = set()

def dfs(orig, cln):
    if orig.val != cln.val:
        return False
        if orig is cln: # Same object!
            return False
            visited_orig.add(orig)
            visited_clone.add(cln)
            if len(orig.neighbors) != len(cln.neighbors):
                return False
                for o_neighbor, c_neighbor in zip(orig.neighbors, cln.neighbors):
                    if o_neighbor not in visited_orig:
                        if not dfs(o_neighbor, c_neighbor):
                            return False
                            return True

                            return dfs(original, clone)

Q3: Can you clone the graph using only constant extra space? Answer: No. We need O(N) space for the hash map. However, we can reduce space by:

  • Using the graph itself for temporary storage (modifying original, then restoring).
  • This is complex and not practical.

Q4: What if the graph has 1 million nodes? Answer:

  • DFS: Might cause stack overflow. Use BFS instead.
  • BFS: Queue can grow large. Consider iterative DFS with explicit stack.
  • Memory: Hash map will use ~16-24 MB (assuming 16 bytes per entry).

Q5: How do you test if two graphs are isomorphic (same structure, different node values)? Answer: After cloning, we can normalize both graphs and compare their adjacency representations. However, graph isomorphism is NP-intermediate in complexity.

13. Deep Dive: Iterative DFS with Explicit Stack

To avoid stack overflow on very deep graphs, use an explicit stack instead of recursion.

Challenge: We need to track both the node and its processing state.

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

            visited = {}
            stack = [node]

            # First pass: Create all clones (without edges)
            while stack:
                current = stack.pop()
                if current in visited:
                    continue

                    visited[current] = Node(current.val)

                    for neighbor in current.neighbors:
                        if neighbor not in visited:
                            stack.append(neighbor)

                            # Second pass: Connect edges
                            for original, clone in visited.items():
                                for neighbor in original.neighbors:
                                    clone.neighbors.append(visited[neighbor])

                                    return visited[node]

Pros:

  • No recursion stack (prevents stack overflow).
  • Two clear phases: node creation, then edge connection.

Cons:

  • Requires two passes through the graph.
  • More code than recursive DFS.

14. Deep Dive: Memory Optimization Techniques

For extremely large graphs (millions of nodes), memory becomes a bottleneck.

Technique 1: Streaming Clone

Clone one connected component at a time, then serialize and free memory.

def cloneGraphStreaming(node: 'Node', output_stream):
    visited = {}

def dfs(n):
    if n in visited:
        return visited[n]
        clone = Node(n.val)
        visited[n] = clone
        for neighbor in n.neighbors:
            clone.neighbors.append(dfs(neighbor))
            return clone

            cloned = dfs(node)

            # Serialize to stream
            output_stream.write(serialize(cloned))

            # Free memory
            del visited
            del cloned

Technique 2: Using Node IDs Instead of Object References

If nodes have unique IDs, we can use arrays instead of hash maps.

def cloneGraphWithIDs(node: 'Node', max_node_id: int) -> 'Node':
    # Assuming node.val is unique and in range [1, max_node_id]
    clones = [None] * (max_node_id + 1)

def dfs(n):
    if clones[n.val] is not None:
        return clones[n.val]

        clone = Node(n.val)
        clones[n.val] = clone

        for neighbor in n.neighbors:
            clone.neighbors.append(dfs(neighbor))

            return clone

            return dfs(node)

Benefit: Arrays have better cache locality than hash maps (faster access).

15. Deep Dive: Parallel Graph Cloning

For massive graphs, we can parallelize the cloning process.

Strategy:

  1. Partition the Graph: Divide nodes into K partitions (e.g., by hash of node ID).
  2. Clone Each Partition: Each thread clones its partition independently.
  3. Merge: Combine all partitions and fix cross-partition edges.
from concurrent.futures import ThreadPoolExecutor

def cloneGraphParallel(nodes: List['Node'], num_threads=4) -> List['Node']:
    # Partition nodes
    partitions = [[] for _ in range(num_threads)]
    for node in nodes:
        partition_id = hash(node) % num_threads
        partitions[partition_id].append(node)

        # Global visited map (thread-safe)
        from threading import Lock
        visited = {}
        visited_lock = Lock()

    def clone_partition(partition):
        local_clones = {}
        for node in partition:
            if node not in visited:
                with visited_lock:
                    if node not in visited:
                        visited[node] = Node(node.val)
                        local_clones[node] = visited[node]

                        # Clone edges (may reference nodes from other partitions)
                        for original, clone in local_clones.items():
                            for neighbor in original.neighbors:
                                with visited_lock:
                                    if neighbor not in visited:
                                        visited[neighbor] = Node(neighbor.val)
                                        clone.neighbors.append(visited[neighbor])

                                        return local_clones

                                        # Execute in parallel
                                        with ThreadPoolExecutor(max_workers=num_threads) as executor:
                                            results = list(executor.map(clone_partition, partitions))

                                            # Return all clones
                                            return list(visited.values())

Complexity: Locking overhead can negate benefits for small graphs. Only useful for graphs with > 100K nodes.

16. Deep Dive: Graph Clone with Path Preservation

Problem: Clone the graph and also return a mapping of paths.

Example: If node A has a path to node C through B in the original, ensure the same path exists in the clone.

def cloneWithPaths(node: 'Node') -> Tuple['Node', Dict[Tuple, List]]:
    visited = {}
    paths = {} # (start, end) -> [path]

def dfs(n):
    if n in visited:
        return visited[n]
        clone = Node(n.val)
        visited[n] = clone
        for neighbor in n.neighbors:
            cloned_neighbor = dfs(neighbor)
            clone.neighbors.append(cloned_neighbor)

            # Record path
            path_key = (n.val, neighbor.val)
            if path_key not in paths:
                paths[path_key] = []
                paths[path_key].append([n.val, neighbor.val])

                return clone

                cloned_root = dfs(node)
                return cloned_root, paths

17. Deep Dive: Cloning Graphs with Random Pointers

Problem Extension: Each node has an additional random pointer to any node in the graph.

class RandomNode:
    def __init__(self, val=0):
        self.val = val
        self.neighbors = []
        self.random = None # Can point to any node

    def cloneRandomGraph(node: 'RandomNode') -> 'RandomNode':
        if not node:
            return None

            visited = {}

    def dfs(n):
        if n in visited:
            return visited[n]

            clone = RandomNode(n.val)
            visited[n] = clone

            # Clone neighbors
            for neighbor in n.neighbors:
                clone.neighbors.append(dfs(neighbor))

                return clone

                # First pass: Clone structure
                cloned_root = dfs(node)

                # Second pass: Fix random pointers
                for original, clone in visited.items():
                    if original.random:
                        clone.random = visited[original.random]

                        return cloned_root

This is similar to LeetCode 138: Copy List with Random Pointer.

Related Problem 1: Clone N-ary Tree (LeetCode 1490)

  • Similar to graph cloning, but trees don’t have cycles.
  • Can use simple recursion without a hash map.

Related Problem 2: Serialize and Deserialize Binary Tree (LeetCode 297)

  • Convert tree to string and back.
  • Similar serialization logic applies to graphs.

Related Problem 3: Number of Connected Components (LeetCode 323)

  • Use DFS/BFS to find connected components.
  • Each component can be cloned separately.

Related Problem 4: Minimum Height Trees (LeetCode 310)

  • Find the “center” nodes of a graph.
  • Cloning from different starting nodes yields different traversal orders.

19. Performance Profiling: DFS vs BFS vs Iterative

Let’s compare the three approaches on a graph with 10,000 nodes and 50,000 edges.

Benchmark Code:

import time
import sys

# Increase recursion limit for large graphs
sys.setrecursionlimit(20000)

def benchmark():
    # Create a large graph
    nodes = [Node(i) for i in range(10000)]
    for i in range(10000):
        # Add 5 random neighbors
        for j in range(min(5, 10000 - i)):
            nodes[i].neighbors.append(nodes[(i + j + 1) % 10000])

            # Test DFS
            start = time.time()
            clone1 = cloneGraphDFS(nodes[0])
            dfs_time = time.time() - start

            # Test BFS
            start = time.time()
            clone2 = cloneGraphBFS(nodes[0])
            bfs_time = time.time() - start

            # Test Iterative
            start = time.time()
            clone3 = cloneGraphIterative(nodes[0])
            iter_time = time.time() - start

            print(f"DFS: {dfs_time:.3f}s")
            print(f"BFS: {bfs_time:.3f}s")
            print(f"Iterative: {iter_time:.3f}s")

Typical Results:

  • DFS: 0.045s (fastest, but risky for deep graphs)
  • BFS: 0.052s (slightly slower due to queue operations)
  • Iterative: 0.048s (good balance)

20. Advanced: Clone Graph with Constraints

Problem: Clone only nodes that satisfy a predicate.

Example: Clone only nodes with even values.

def cloneGraphFiltered(node: 'Node', predicate) -> 'Node':
    if not node or not predicate(node):
        return None

        visited = {}

    def dfs(n):
        if n in visited:
            return visited[n]

            if not predicate(n):
                visited[n] = None
                return None

                clone = Node(n.val)
                visited[n] = clone

                for neighbor in n.neighbors:
                    cloned_neighbor = dfs(neighbor)
                    if cloned_neighbor: # Only add if passes predicate
                        clone.neighbors.append(cloned_neighbor)

                        return clone

                        return dfs(node)

                        # Usage
    def is_even(node):
        return node.val % 2 == 0

        filtered_clone = cloneGraphFiltered(root, is_even)

21. Deep Dive: Space-Time Tradeoffs

We can reduce space at the cost of time by not storing all clones at once.

Strategy: On-Demand Cloning

class LazyClone:
    def __init__(self, original_graph):
        self.original = original_graph
        self.cache = {}

    def get_clone(self, node):
        if node in self.cache:
            return self.cache[node]

            # Clone on demand
            clone = Node(node.val)
            self.cache[node] = clone

            for neighbor in node.neighbors:
                clone.neighbors.append(self.get_clone(neighbor))

                return clone

    def clear_cache(self):
        self.cache.clear() # Free memory

Use Case: Clone different subgraphs at different times, clearing cache between operations.

22. Deep Dive: Testing Graph Equivalence

After cloning, how do we verify the clone is structurally identical to the original?

Method 1: BFS Comparison

def areGraphsEquivalent(g1: 'Node', g2: 'Node') -> bool:
    if not g1 and not g2:
        return True
        if not g1 or not g2:
            return False

            visited1, visited2 = set(), set()
            queue = deque([(g1, g2)])

            while queue:
                n1, n2 = queue.popleft()

                if n1.val != n2.val:
                    return False

                    if len(n1.neighbors) != len(n2.neighbors):
                        return False

                        visited1.add(n1)
                        visited2.add(n2)

                        # Compare neighbors (must be in same order)
                        for neighbor1, neighbor2 in zip(n1.neighbors, n2.neighbors):
                            if neighbor1 not in visited1:
                                queue.append((neighbor1, neighbor2))

                                return True

Method 2: Canonical Representation Convert both graphs to a canonical string representation and compare.

def getCanonicalForm(node: 'Node') -> str:
    if not node:
        return ""

        visited = set()
        adj_list = []

    def dfs(n):
        if n in visited:
            return
            visited.add(n)
            neighbors = sorted([nb.val for nb in n.neighbors])
            adj_list.append(f"{n.val}:{','.join(map(str, neighbors))}")
            for neighbor in n.neighbors:
                dfs(neighbor)

                dfs(node)
                return "|".join(sorted(adj_list))

    def areGraphsEquivalent(g1, g2):
        return getCanonicalForm(g1) == getCanonicalForm(g2)

23. Practical Optimization Tips

Based on extensive benchmarking, here are optimization tips for production code:

Tip 1: Pre-allocate Hash Map

def cloneGraphOptimized(node: 'Node', estimated_size=100) -> 'Node':
    # Pre-allocate to reduce rehashing
    visited = dict.fromkeys(range(estimated_size))
    visited.clear()
    # ... rest of algorithm

Tip 2: Use collections.defaultdict for Implicit Node Creation

from collections import defaultdict

def cloneGraphFast(node: 'Node') -> 'Node':
    visited = defaultdict(lambda: Node())

def dfs(n):
    if visited[n].val != 0: # Already cloned
        return visited[n]

        visited[n].val = n.val
        for neighbor in n.neighbors:
            visited[n].neighbors.append(dfs(neighbor))

            return visited[n]

            return dfs(node)

Tip 3: Avoid Repeated in Checks

# SLOW
if node not in visited:
    visited[node] = clone
    return visited[node]

    # FAST (use dict.get)
    clone = visited.get(node)
    if clone is None:
        clone = Node(node.val)
        visited[node] = clone
        return clone

Tip 4: Cache Locality - Use Arrays When Possible If node IDs are dense (1, 2, 3, …, N), use an array instead of a hash map for 2-3x speed improvement.

24. Production Debugging Checklist

When implementing graph cloning in production, watch for these issues:

Issue 1: Reference Leaks

# BAD: Keeps references to original graph
def cloneGraphBad(node):
    visited = {}
    # ... cloning logic
    return visited[node] # visited map keeps all original nodes!

    # GOOD: Only return the clone
def cloneGraphGood(node):
    visited = {}
    # ... cloning logic
    result = visited[node]
    visited.clear() # Free original references
    return result

Issue 2: Cycle Detection Failures Always check that your hash map lookup happens before creating the clone.

Issue 3: Memory Profiling Use tracemalloc to measure memory usage:

import tracemalloc

tracemalloc.start()
clone = cloneGraph(huge_graph)
current, peak = tracemalloc.get_traced_memory()
print(f"Current: {current / 1024 / 1024:.2f} MB")
print(f"Peak: {peak / 1024 / 1024:.2f} MB")
tracemalloc.stop()

25. Interview Pro Tips

Tip 1: Clarify the Problem

  • Is the graph directed or undirected?
  • Can there be self-loops?
  • Are node values unique?
  • Is the graph guaranteed to be connected?

Tip 2: Start with a Simple Example Draw a 3-4 node graph on paper. Walk through your algorithm step-by-step.

Tip 3: Mention the Hash Map First Immediately state: “We’ll need a hash map to track original → clone mappings to handle cycles.”

Tip 4: Discuss Trade-offs Mention that DFS is more concise but BFS is safer for very deep graphs.

Tip 5: Test Edge Cases

  • null graph
  • Single node with no neighbors
  • Two-node cycle
  • Complete graph (every node connected to every other node)

Key Takeaways

  1. Hash Map is Essential: Prevents infinite loops and duplicate clones.
  2. DFS vs BFS: Both work. DFS is more concise, BFS avoids stack overflow.
  3. Deep Copy: Must recursively clone all references, not just the top-level object.
  4. Graph Cycles: The hash map handles cycles naturally by returning existing clones.
  5. Real-World Use: Graph cloning is used in distributed systems, version control, and game AI.

Summary

Aspect Insight
Core Problem Deep copy a graph with cycles
Key Data Structure Hash map (original → clone)
Algorithm DFS or BFS with visited tracking
Time Complexity O(N + E)
Space Complexity O(N)

FAQ

Why can’t you clone a graph the same way you clone a linked list or tree?

Unlike trees or linked lists, graphs can contain cycles. If you naively recurse through neighbors without tracking which nodes have already been cloned, you will enter infinite recursion when you revisit a node through a cycle. The solution is a hash map that maps each original node to its clone, returning the existing clone immediately when a visited node is encountered.

What is the difference between shallow copy and deep copy for graphs?

A shallow copy creates a new top-level node but shares references to the original neighbor list and neighbor objects. Modifying a neighbor in the shallow copy affects the original. A deep copy recursively creates new node objects for the entire graph structure, ensuring complete independence between original and clone.

When should you prefer BFS over DFS for graph cloning?

Prefer BFS when the graph may be very deep, such as a long chain of nodes, because recursive DFS could cause a stack overflow. BFS uses an explicit queue with bounded memory proportional to the maximum width of the graph. For most interview problems with moderate graph sizes, either approach works well.

How do you verify that a graph clone is correct?

Verify three properties: (1) structural correctness by running BFS/DFS on both graphs and checking matching connectivity, (2) identity correctness by ensuring every cloned node is a different object from its original using clone is not original, and (3) value correctness by confirming all node values match between original and clone.

Originally published at: arunbaby.com/dsa/0033-clone-graph

Related across topics