#133

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Clone Graph

Clone Graph involves cloning a graph using DFS, focusing on graph traversal and neighbor management using hash tables.

hash table depth first search breadth first search graph

Problem Statement

Given a reference to a node in a connected, undirected graph, your task is to return a deep copy (clone) of the graph. Each node in the graph contains an integer value and a list of neighbors. The graph is connected, and there are no self-loops or repeated edges.

You must ensure that the cloned graph is an exact duplicate, maintaining the same structure and values, with no references to the original nodes. This problem requires careful management of visited nodes to handle cycles and multiple neighbors.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

class Node { public int val; public List neighbors; }

Example 2

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]

Output: [[2,4],[1,3],[2,4],[1,3]]

There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 3

Input: adjList = [[]]

Output: [[]]

Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

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.

Solution Approach

Depth-First Search (DFS) Traversal

Using DFS, start from the given node and recursively visit its neighbors. For each node, check if it has already been cloned by storing nodes in a hash table to avoid duplication. If a node hasn’t been cloned, create a new node with the same value, and recursively clone its neighbors. This ensures the graph structure is preserved.

Hash Table for Storing Cloned Nodes

A hash table is used to map each original node to its clone. This allows the DFS traversal to check whether a node has already been cloned, preventing cycles and redundant cloning. The hash table ensures that the algorithm handles graphs with cycles correctly by not revisiting nodes.

Breadth-First Search (BFS) Alternative

An alternative to DFS is BFS, where you use a queue to explore nodes level by level. Similar to DFS, a hash table keeps track of visited nodes, and neighbors are added to the queue for cloning. This approach ensures all nodes are cloned without revisiting nodes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depends on the number of nodes and edges in the graph. DFS and BFS both operate in O(N + E), where N is the number of nodes and E is the number of edges. Space complexity is also O(N) due to the storage required for the hash table to track visited nodes and clones.

What Interviewers Usually Probe

Do you understand the importance of using a hash table to store visited nodes during graph traversal?
Can you describe how to handle cycles when cloning a graph using DFS?
Will you explain how the BFS approach can be an alternative to DFS for this problem?

Common Pitfalls or Variants

Common pitfalls

Not using a hash table to track cloned nodes, leading to cycles and duplicate clones.
Forgetting to handle empty graphs (edge cases with no nodes).
Mismanaging neighbor lists, potentially losing node connections during cloning.

Follow-up variants

How would you handle cloning a graph with multiple disconnected components?
Can you modify the algorithm to clone a directed graph?
What changes would be necessary to clone the graph while maintaining node reference identities (not deep copying)?

FAQ

What is the primary pattern used to solve the Clone Graph problem?

The primary pattern for solving the Clone Graph problem is graph traversal using Depth-First Search (DFS) or Breadth-First Search (BFS) with the aid of a hash table.

How does the hash table help in the Clone Graph problem?

The hash table maps original nodes to their clones, ensuring that each node is only cloned once and preventing infinite loops in the presence of cycles.

How do you handle cycles in the Clone Graph problem?

Cycles are handled by checking the hash table to ensure that nodes are not cloned more than once. If a node has already been cloned, the algorithm skips it to avoid infinite loops.

What happens if the graph is empty in the Clone Graph problem?

If the graph is empty (i.e., the input node is null), the solution should return null or an empty graph as the clone.

Can Clone Graph be solved using a different traversal method?

Yes, Clone Graph can be solved using either Depth-First Search (DFS) or Breadth-First Search (BFS). Both approaches rely on a hash table to manage visited nodes.

terminal

Solution

Solution 1: Hash Table + DFS

We use a hash table $\textit{g}$ to record the correspondence between each node in the original graph and its copy, and then perform depth-first search.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional


class Solution:
    def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
        def dfs(node):
            if node is None:
                return None
            if node in g:
                return g[node]
            cloned = Node(node.val)
            g[node] = cloned
            for nxt in node.neighbors:
                cloned.neighbors.append(dfs(nxt))
            return cloned

        g = defaultdict()
        return dfs(node)

Continue Practicing

#924 minimize malware spread #928 minimize malware spread ii #207 course schedule