Clone Graph Python Solution with Tests

Tested Python solution for LeetCode 133 with 63 pytest cases. Generate a practice environment with lcpy.

LeetCode 133, Medium. Topics: Hash Table, Depth-First Search, Breadth-First Search, Graph. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 63 parametrized pytest cases, and a playground notebook:

lcpy gen -n 133   # by problem number
lcpy gen -s clone_graph   # by problem name

​

Problem

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 (int) and a list (List[Node]) of its neighbors.

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

Test case format:

For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

​

Examples

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. 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).

Input: adjList = [[]]
Output: [[]]

Explanation: 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.

Input: adjList = []
Output: []

Explanation: This an empty graph, it does not have any nodes.

​

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

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import deque

from leetcode_py import GraphNode


class Solution:
    # Time: O(V + E)
    # Space: O(V)
    def clone_graph(self, node: GraphNode | None) -> GraphNode | None:
        if node is None:
            return None

        def dfs(node: GraphNode, visited: dict[int, GraphNode]):
            if node.val in visited:
                return visited[node.val]

            clone = GraphNode(node.val)
            visited[node.val] = clone

            for neighbor in node.neighbors:
                clone.neighbors.append(dfs(neighbor, visited))

            return clone

        return dfs(node, visited={})


class SolutionDFS:
    # DFS Iterative
    # Time: O(V + E)
    # Space: O(V)
    def clone_graph(self, node: GraphNode | None) -> GraphNode | None:
        if node is None:
            return None

        stack = [node]
        visited = {node.val: GraphNode(node.val)}

        while stack:
            current = stack.pop()
            clone = visited[current.val]

            for neighbor in current.neighbors:
                if neighbor.val not in visited:
                    visited[neighbor.val] = GraphNode(neighbor.val)
                    stack.append(neighbor)
                clone.neighbors.append(visited[neighbor.val])

        return visited[node.val]


class SolutionBFS:
    # BFS
    # Time: O(V + E)
    # Space: O(V)
    def clone_graph(self, node: GraphNode | None) -> GraphNode | None:
        if node is None:
            return None

        queue = deque([node])
        visited = {node.val: GraphNode(node.val)}

        while queue:
            current = queue.popleft()
            clone = visited[current.val]

            for neighbor in current.neighbors:
                if neighbor.val not in visited:
                    visited[neighbor.val] = GraphNode(neighbor.val)
                    queue.append(neighbor)
                clone.neighbors.append(visited[neighbor.val])

        return visited[node.val]

​

Complexity

Time	Space
O(V + E)	O(V)

​

Tags

Grind 75, Grind, Blind 75, NeetCode 150, NeetCode 250, NeetCode All, AlgoMaster 75.