Clone Graph

Question

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Tests graph traversal and hash map usage, a recurring Meta interview question.

Codemia · Accepted Answer

The problem requires us to create a deep copy of an undirected graph, which means we need to replicate both nodes and their connections (edges). This is a classic case for the **graph traversal** pattern, specifically using **BFS (Breadth-First Search)** or **DFS (Depth-First Search)**. Both methods can effectively explore all nodes and edges of the graph. In this case, we will use a **DFS approach** for its straightforward recursive implementation, which allows us to copy nodes and their connections as we traverse through the graph.

1. **Initialization**: Start by creating a hash map (dictionary in Python) to keep track of already copied nodes. This will help in avoiding cycles and redundant copies.
2. **Recursive Function**: Define a recursive function that takes a node as input. If the node has already been copied (exists in the hash map), return the copied node from the map.
3. **Copy the Node**: If the node is not in the map, create a new node with the same value, and add it to the map.
4. **Copy Neighbors**: Recursively call the function for each neighbor of the current node, adding the results to the neighbors list of the newly created node.
5. **Return the Copied Node**: Finally, return the newly created node.

### Example Walkthrough:
For a graph represented as follows:
```
1 -- 2
|    |
4 -- 3
```
Starting from node 1:
- Create a copy of node 1, add it to the map.
- Call the function for neighbor 2, create a copy of node 2, and add it to the map. Continue this for neighbors 3 and 4 recursively.

Here is the Python solution using DFS:
```python
class Node:
    def __init__(self, val=None, 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

# HashMap to keep track of copied nodes
        copied_nodes = {}

def dfs(current_node):
            if current_node in copied_nodes:
                return copied_nodes[current_node]

# Create a copy of the current node
            copy = Node(current_node.val)
            copied_nodes[current_node] = copy

# Recursively copy the neighbors
            for neighbor in current_node.neighbors:
                copy.neighbors.append(dfs(neighbor))

return copy

return dfs(node)
```
This code defines a Node class for the graph nodes and a Solution class with a method that implements the cloning logic.

The time complexity of this solution is **O(V + E)**, where **V** is the number of vertices (nodes) and **E** is the number of edges. This complexity arises because we visit each node exactly once and traverse each edge exactly once during the DFS. The space complexity is also **O(V)** due to the hash map used to store the copied nodes and the call stack of the recursive function, which can go as deep as the number of nodes in the worst case (especially in the case of a skewed graph).

1. **Empty Graph**: If the input node is `None`, the output should also be `None`.
2. **Single Node Graph**: If the graph consists of a single node with no edges, the output should be a new node with the same value and no neighbors.
3. **Cyclic Graph**: The implementation must handle cycles (e.g., a node points back to one of its neighbors), which is managed by using the hash map to track already copied nodes to avoid infinite loops.

Clone Graph

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string