Solving LeetCode Problem #133: Clone Graph Using Depth-First Search

Introduction

In this post, we’ll take a closer look at a classic graph problem — Clone Graph. This is LeetCode Problem #133 and it is a great problem to enhance your understanding of graph traversal techniques, particularly Depth-First Search (DFS).

Problem Statement

Given a reference of a node in a connected undirected graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Return a deep copy (clone) of the graph. The graph is represented as follows:

• The Node.val is unique for each node.
• All Node are connected by edges.

Understanding the Problem and Approach

This problem falls under the category of graph traversal. The task is to perform a deep copy of the graph which means creating a new graph that has the same structure as the original but shares no nodes with it.

A Depth-First Search (DFS) can be used to traverse the graph and make a copy of each node while preserving the connections. A dictionary can be used to store the mapping between the original nodes and their copies. This dictionary serves two purposes:

1. It helps to avoid making multiple copies of the same node.
2. It can be used to reconnect the copied nodes.

Now that we’ve outlined the approach, let’s take a look at the Python solution.

Python Solution

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

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

        visited = {}

        def dfs(node):
            # Return the clone from the visited dictionary
            if node in visited:
                return visited[node]
            
            # Copy the node and store it in the visited dictionary
            clone_node = Node(node.val, [])
            visited[node] = clone_node

            # Iterate through neighbors
            for neighbor in node.neighbors:
                clone_node.neighbors.append(dfs(neighbor))
            
            return clone_node

        return dfs(node)

Time and Space Complexity Analysis

The time complexity of this solution is O(n), where n is the number of nodes in the graph. This is because each node in the graph is visited and copied exactly once.

The space complexity is also O(n) because the ‘visited’ dictionary will end up storing all nodes in the graph. Additionally, there is space required for the recursive stack in the DFS traversal. In the worst case, this could be O(n) for a skewed graph.

Conclusion

In this post, we have solved the Clone Graph problem using Depth-First Search. This problem is a wonderful way to understand how graph traversal can be used to create a deep copy of a data structure. Keep practicing, and happy coding!