Taro Logo

Clone Graph

Medium
Meta logo
Meta
3 views
Topics:
Graphs

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;
}

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.

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

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

Another example:

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.

How would you implement a deep copy of a graph given a starting node? Consider edge cases such as empty graphs or graphs with a single node. Discuss the time and space complexity of your solution.

Solution


Deep Copy (Clone) of a Graph

Problem Description

Given a reference to a node in a connected undirected graph, the goal is to create a deep copy (clone) of the graph. Each node in the graph contains a value (integer) and a list of its neighbors. The graph is represented using an adjacency list where each list describes the set of neighbors of a node in the graph. The value of each node is the same as its index (1-indexed). The given node will always be the first node with val = 1. The function should return the copy of the given node as a reference to the cloned graph.

Naive Solution (Brute Force)

The brute force approach would involve traversing the original graph and creating new nodes with the same values. A simple way to accomplish this is using Depth-First Search (DFS) or Breadth-First Search (BFS). As we visit each node in the original graph, we create a corresponding node in the cloned graph.

Optimal Solution

The optimal solution also involves using DFS or BFS, but with a mechanism to avoid infinite loops and to efficiently create the cloned graph. A hash map (or dictionary) is typically used to store the mapping between the nodes in the original graph and their corresponding nodes in the cloned graph. This ensures that each node is cloned only once, and that neighbors are correctly linked.

Algorithm:

  1. Initialization: Create a hash map to store the mapping between original nodes and cloned nodes.
  2. Base Case: If the input node is null, return null.
  3. Check if Cloned: Check if the node has already been cloned (i.e., exists in the hash map). If yes, return the cloned node from the hash map.
  4. Clone Node: If the node has not been cloned, create a new node with the same value as the original node.
  5. Store Mapping: Store the mapping between the original node and the cloned node in the hash map.
  6. Clone Neighbors: Iterate through the neighbors of the original node. For each neighbor, recursively call the clone function to get the cloned neighbor.
  7. Add Neighbors: Add the cloned neighbor to the list of neighbors of the cloned node.
  8. Return Cloned Node: Return the cloned node.

Code (Python):

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


def cloneGraph(node: 'Node') -> 'Node':
    if not node:
        return None

    old_to_new = {}

    def clone(node):
        if node in old_to_new:
            return old_to_new[node]

        copy = Node(node.val)
        old_to_new[node] = copy

        for neighbor in node.neighbors:
            copy.neighbors.append(clone(neighbor))

        return copy

    return clone(node)

Big(O) Run-time

The run-time complexity is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because we visit each node and each edge once.

Big(O) Space usage

The space complexity is O(V), where V is the number of vertices (nodes) in the graph. This is because, in the worst case, we may need to store all nodes in the hash map.

Edge Cases

  • Empty Graph: If the input graph is empty (i.e., the input node is null), the function should return null.
  • Single Node Graph: If the graph consists of only one node, the function should create a new node with the same value and return it.
  • Disconnected Graph: The problem statement specifies that the graph is connected, so this case does not need to be handled explicitly. However, if the graph were disconnected, the algorithm would only clone the connected component containing the starting node.
  • Cyclic Graph: The algorithm correctly handles cyclic graphs due to the use of the hash map to keep track of cloned nodes, preventing infinite recursion.