133. Clone Graph

Problem Statement

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

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: Node 1's value is 1, and it has two neighbors: Node 2 and 4. Node 2's value is 2, and it has two neighbors: Node 1 and 3. Node 3's value is 3, and it has two neighbors: Node 2 and 4. Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Example 2:

Input: adjList = [[]] Output: [[]] Explanation: Note that the input contains one empty list. The graph contains only one node with val = 1 and it does not have any neighbors.

---

Difficulty

Medium

Solution 1: Breadth-First Search (BFS)

Approach:

In the BFS approach, we use a queue to traverse the graph layer by layer. We also maintain a hash map to map original nodes to their corresponding cloned nodes. When we visit a node, we check if it has already been cloned. If not, we create a clone and store it in the map. Then, for each neighbor of the current node, we either retrieve its clone from the map or create a new one, adding it to the neighbor list of the current node's clone. This ensures that every node and edge is copied exactly once without falling into infinite loops in a cyclic graph.

Java

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> visited = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        
        visited.put(node, new Node(node.val, new ArrayList<>()));
        queue.offer(node);
        
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            for (Node neighbor : curr.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    visited.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
                    queue.offer(neighbor);
                }
                visited.get(curr).neighbors.add(visited.get(neighbor));
            }
        }
        return visited.get(node);
    }
}

C++

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        unordered_map<Node*, Node*> visited;
        queue<Node*> q;
        
        visited[node] = new Node(node->val);
        q.push(node);
        
        while (!q.empty()) {
            Node* curr = q.front();
            q.pop();
            
            for (auto neighbor : curr->neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    visited[neighbor] = new Node(neighbor->val);
                    q.push(neighbor);
                }
                visited[curr]->neighbors.push_back(visited[neighbor]);
            }
        }
        return visited[node];
    }
};

Python

from collections import deque
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        
        visited = {node: Node(node.val)}
        queue = deque([node])
        
        while queue:
            curr = queue.popleft()
            for neighbor in curr.neighbors:
                if neighbor not in visited:
                    visited[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)
                visited[curr].neighbors.append(visited[neighbor])
        
        return visited[node]

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
Space Complexity: O(V) to store the hash map and the queue.

---

Solution 2: Depth-First Search (DFS)

Approach:

DFS utilizes recursion to traverse the graph depth-first. We use a hash map to keep track of already cloned nodes. For each node, if it's already in our map, we return its clone. If not, we create a clone, add it to the map, and then recursively clone all of its neighbors. This naturally handles the graph structure and avoids cycles by checking the map before proceeding with a recursive call.

Java

class Solution {
    private Map<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);

        Node cloneNode = new Node(node.val, new ArrayList<>());
        visited.put(node, cloneNode);

        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

C++

class Solution {
public:
    unordered_map<Node*, Node*> visited;

    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        if (visited.count(node)) return visited[node];

        Node* cloneNode = new Node(node->val);
        visited[node] = cloneNode;

        for (auto neighbor : node->neighbors) {
            cloneNode->neighbors.push_back(cloneGraph(neighbor));
        }
        return cloneNode;
    }
};

Python

class Solution:
    def __init__(self):
        self.visited = {}

    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        if node in self.visited:
            return self.visited[node]

        clone_node = Node(node.val, [])
        self.visited[node] = clone_node

        for neighbor in node.neighbors:
            clone_node.neighbors.append(self.cloneGraph(neighbor))
        
        return clone_node

Time Complexity: O(V + E)
Space Complexity: O(V) for the recursion stack and the hash map.

← All Problems