{x}
blog image

Clone Graph

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.

 

Example 1:

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

Example 2:

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.

Example 3:

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 Explanation for Clone Graph

This problem requires creating a deep copy of a graph, ensuring that all nodes and edges are duplicated. The graph is represented using a Node class with a value and a list of neighboring nodes. We'll explore Depth-First Search (DFS) and Breadth-First Search (BFS) approaches.

Approach 1: Depth-First Search (DFS) using Recursion

This approach uses recursion and a hash map (dictionary in Python) to track visited nodes. The clone function recursively explores the graph:

  1. Base Case: If the current node is null, it returns null.
  2. Visited Check: If the node is already in the visited map, it returns the cloned version from the map, avoiding cycles.
  3. Clone Creation: A new node with the same value is created.
  4. Neighbor Cloning: The function recursively calls itself on each neighbor and adds the cloned neighbor to the new node's neighbor list.
  5. Map Update: The newly created node is added to the visited map.
  6. Return: The cloned node is returned.

Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. Each node and edge is visited once.

Space Complexity: O(V) for the visited map, storing at most all the nodes in the worst-case scenario (a fully connected graph). The recursive call stack also adds space complexity, but this is at most proportional to the height of the graph, which in the worst case is equal to V.

Approach 2: Breadth-First Search (BFS) using a Queue

This approach uses a queue for iterative traversal, also utilizing a hash map to track visited nodes.

  1. Initialization: The visited map is created and the root node is cloned and added to both the visited map and a queue.
  2. Iteration: While the queue is not empty:
    • Dequeue a node.
    • Iterate through its neighbors:
      • If a neighbor is not in visited, clone it, add it to visited and the queue.
      • Add the cloned neighbor to the cloned node's neighbor list.

Time Complexity: O(V + E), same as DFS. Each node and edge is visited once.

Space Complexity: O(V), for both the visited map and the queue, which may store all the nodes in the worst case.

Code Examples (Python, Java, C++, Go, TypeScript, C#)

The code examples provided in the prompt demonstrate both DFS and BFS implementations in multiple languages. The DFS solution is generally more concise, while the BFS solution might be slightly easier to understand for those less familiar with recursion. Choose the implementation that best suits your understanding and preferred language. Both have the same time and space complexity.

Remember that the Node class definition needs to be included in each language's implementation. The specific details might vary depending on the language's syntax, but the core logic remains the same.