133. Clone Graph#

Difficulty: Medium

Link to Problem: To see the Clone Graph problem on LeetCode, click here!

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.

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.

Probelm Explanation:#

The problem at hand is to clone a connected undirected graph, which means we need to create a deep copy of the original graph while preserving its structure and relationships between nodes. The graph is represented using adjacency lists, where each node has a value (an integer) and a list of its neighbors.

Here are the key aspects of the problem:

  1. Input: You are given a reference to one of the nodes in the original graph. This reference node serves as the entry point to the graph. The entire graph can be explored starting from this node.

  2. Output: The goal is to create a deep copy of the graph and return a reference to the cloned graph. The cloned graph should have the same structure and relationships as the original one but should be a separate instance in memory.

  3. Graph Structure: The graph is composed of nodes (vertices) and edges. Nodes have values (integers) and are connected to other nodes through edges (undirected connections). Each node has a list of neighbors, which are other nodes it is connected to.

  4. Connected Graph: The problem assumes that the graph is connected, meaning that you can start from the reference node provided and traverse the entire graph by following the edges. This ensures that there are no isolated components in the graph.

To solve this problem, you typically need to perform a graph traversal (e.g., depth-first search or breadth-first search) to visit all the nodes in the original graph, create corresponding nodes in the clone, and establish the same connections between nodes in the cloned graph as in the original one. To avoid duplication of nodes, you also need to keep track of visited nodes to ensure that the cloning process is efficient and that nodes are not duplicated in the clone.

The problem can be challenging because you need to create a deep copy of the graph while handling cyclic dependencies between nodes and ensuring that the structure and relationships of the original graph are preserved in the clone. The solution requires recursion or a data structure to maintain the mapping between original nodes and their clones to achieve an efficient and accurate cloning process.

Solution:#

Here’s a Python function to implement this algorithm:

# 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 []

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

        visited = {}  # Dictionary to keep track of visited nodes

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

            # Create a copy of the original node
            copy_node = Node(original_node.val)
            visited[original_node] = copy_node

            # Recursively clone the neighbors of the original node
            for neighbor in original_node.neighbors:
                copy_node.neighbors.append(dfs(neighbor))

            return copy_node

        return dfs(node)

Explanation:#

The given code defines a Python class, Node, and a solution class, Solution, to clone a connected undirected graph represented by nodes and their neighbors. Here’s an explanation of the code:

  1. The Node class defines a node in the graph. Each node has a value (val) which is an integer and a list of neighbors (neighbors) that are other nodes in the graph.

  2. The Solution class contains the method cloneGraph, which takes a reference to the first node of the graph (node) as input and returns a deep copy of the entire graph, preserving the structure and relationships between nodes.

  3. Inside the cloneGraph method:

    • It first checks if the input node is None. If it’s None, it means there is no graph to clone, and the method returns None.

    • It initializes a visited dictionary to keep track of visited nodes. This dictionary is used to ensure that each node is cloned only once to avoid duplication.

    • The dfs (depth-first search) function is defined within the cloneGraph method. It takes an original node as input and returns its corresponding clone. This function performs the actual cloning of the graph.

    • Inside the dfs function:

      • It checks if the original node has been visited before by looking it up in the visited dictionary. If it has been visited, it returns the corresponding clone from the visited dictionary.

      • If the original node is not visited, it creates a new node, copy_node, with the same value as the original node. This is the first step in creating the clone of the original node.

      • It then recursively clones the neighbors of the original node by iterating through the neighbors list of the original node and appending the corresponding cloned neighbors to the neighbors list of the copy_node. This step ensures that the relationships between nodes are preserved in the clone.

      • The copy_node is added to the visited dictionary with the original node as the key and the clone as the value.

      • Finally, the copy_node is returned as the result of the DFS for the original node.

  4. The cloneGraph method returns the result of the DFS on the input node, which is the clone of the entire graph with its structure and relationships intact.

In summary, the code uses depth-first search (DFS) to traverse the original graph, creating a clone for each node and its neighbors. It ensures that each node is cloned only once to avoid duplication and returns a reference to the cloned graph.

Test cases:#

Here’s how you can use this solution:

def get_adjacency_list(node):
    visited = {}  # Dictionary to keep track of visited nodes

    def dfs(node):
        if not node:
            return []

        if node in visited:
            return visited[node]

        neighbors = [n.val for n in node.neighbors]
        visited[node] = neighbors

        for neighbor in node.neighbors:
            dfs(neighbor)

    dfs(node)
    result = []

    def get_node_and_neighbors(node):
        result.append([node.val] + visited[node])

    get_node_and_neighbors(node)
    return result


# Testing the code with the provided examples
adjList1 = [[2, 4], [1, 3], [2, 4], [1, 3]]
solution = Solution()

# Create the graph from adjList
nodes = [Node(i) for i in range(1, len(adjList1) + 1)]
for i, adj in enumerate(adjList1):
    nodes[i].neighbors = [nodes[j - 1] for j in adj]

# Clone the graph and get its adjacency list
cloned_node1 = solution.cloneGraph(nodes[0])
cloned_adjList1 = get_adjacency_list(cloned_node1)

# Print the cloned graph as an adjacency list
print(cloned_adjList1)

# Output should match adjList1

[[1, 2, 4]]

# Example 2
# Input: adjList = [[]]

adjList2 = [[]]
solution = Solution()

# Create the graph from adjList
node1 = Node(1)

# Clone the graph and get its adjacency list
cloned_node1 = solution.cloneGraph(node1)
cloned_adjList2 = get_adjacency_list(cloned_node1)

# Print the cloned graph as an adjacency list
print(cloned_adjList2)

# Output should be [[]], which represents an empty graph

[[1]]

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided code for cloning a graph using depth-first search (DFS).

Time Complexity:

  1. Creating the graph: The time complexity to create the original graph from adjList is O(V + E), where V is the number of vertices (nodes) and E is the number of edges. We iterate through each node and its neighbors in adjList.

  2. Cloning the graph (DFS): The depth-first search (DFS) is used to traverse the original graph and create a clone. The time complexity of DFS is O(V + E), as we visit each node and each edge once.

Overall, the time complexity is O(V + E) for both creating the original graph and cloning it.

Space Complexity:

  1. Storage for the original graph: We need to store the original graph, which includes all nodes and their adjacency lists. In the worst case, this requires O(V + E) space, where V is the number of nodes, and E is the number of edges.

  2. Storage for the visited dictionary: The visited dictionary stores mappings from original nodes to their corresponding clones. In the worst case, this requires O(V) space because each node is visited once.

  3. Recursive stack for DFS: The space used for the recursive call stack during DFS can be up to O(V) in the worst case, where V is the number of nodes.

Overall, the space complexity is O(V + E) for storing the original graph, and O(V) for auxiliary data structures, including the visited dictionary and the DFS call stack. Therefore, the overall space complexity is O(V + E).

In summary, the time and space complexities of the provided code for cloning a graph are both O(V + E), where V is the number of nodes, and E is the number of edges in the graph.

Challenging Exercises:#

  1. Cyclic Graph: Design a graph with cycles (nodes connected in a cycle). Test if the code can correctly clone graphs with cycles and doesn’t fall into an infinite loop during traversal.

  2. Partial Graph Cloning: Modify the code to clone only a subset of the graph starting from a given reference node, rather than the entire graph. Implement this as an extension to the problem.