13. Clone an Undirected Graph

The problem can be found at the following link: Question Link

Problem Description

Given a connected undirected graph represented by an adjacency list, adjList[][], with n nodes (each node having a distinct label from 0 to n-1), your task is to create a clone (deep copy) of this graph. Each node in the graph has:

• An integer val

• A list neighbors containing references to its adjacent nodes

Structure

class Node {
    int val;
    List<Node> neighbors;
}

Return a reference to the cloned graph such that the cloned graph is identical to the original graph. The driver code will then print true if the clone is correct; otherwise it prints false.

Note: Sorry for uploading late, my Final Sem exam is going on.

Examples

Example 1

Input:

n = 4 adjList = [[1, 2], [0, 2], [0, 1, 3], [2]]

Output:

true

Explanation:

The cloned graph is structurally identical to the original. Driver code checks memory and structure integrity.

Example 2

Input:

n = 3 adjList = [[1, 2], [0], [0]]

Output:

true

Explanation:

The cloned graph is identical to the original one, hence driver code outputs true.

Constraints

• $( 1 \leq n \leq 10^4 )$

• $( 0 \leq \text{number of edges} \leq 10^5 )$

• $( 0 \leq \text{adjList[i][j]} < n )$

My Approach

BFS-Based Graph Clone using Queue

Algorithm Steps:

1. Initialization:

   • If the starting node is null, return null.

   • Create a hash map (or dictionary) to store mappings from each original node to its clone.

   • Initialize a queue and enqueue the starting node.

2. BFS Traversal:

   • While the queue is not empty:

     • Dequeue the front node.

     • For each neighbor of the dequeued node:

       • If the neighbor hasn't been cloned (i.e., not present in the map), create its clone, store it in the map, and enqueue the neighbor.

       • Append the clone of the neighbor to the neighbors list of the clone corresponding to the current node.

3. Return:

   • After processing all nodes, return the clone corresponding to the starting node.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(N + M), where N is the number of nodes and M is the number of edges. We visit each node and edge exactly once during the clone.

• Expected Auxiliary Space Complexity: O(N), used by the hash map and the queue.

Code (C++)

// ✅ BFS-Based Graph Clone using Queue
class Solution {
  public:
    Node* cloneGraph(Node* node) {
        if (!node) return 0;
        unordered_map<Node*, Node*> m;
        m[node] = new Node(node->val);
        queue<Node*> q{{node}};
        while (!q.empty()) {
            for (auto n : q.front()->neighbors) {
                if (!m[n]) q.push(n), m[n] = new Node(n->val);
                m[q.front()]->neighbors.push_back(m[n]);
            }
            q.pop();
        }
        return m[node];
    }
};

⚡ Alternative Approaches

📊 2️⃣ DFS-Based Clone (Recursive)

Algorithm Steps:

1. Use a map<Node*, Node*> to keep track of original → clone mappings.

2. Recursively visit each neighbor and clone them.

3. Return the cloned node after recursively linking its neighbors.

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        unordered_map<Node*, Node*> m;
        return dfs(node, m);
    }

    Node* dfs(Node* node, unordered_map<Node*, Node*>& m) {
        if (m.count(node)) return m[node];
        Node* clone = new Node(node->val);
        m[node] = clone;
        for (Node* neighbor : node->neighbors)
            clone->neighbors.push_back(dfs(neighbor, m));
        return clone;
    }
};

📝 Complexity Analysis:

• Time Complexity: O(N + M) — Each node and edge visited once.

• Space Complexity: O(N) — For hashmap and recursion stack.

✅ Why This Approach?

Very elegant and simple implementation that leverages recursion, suitable for medium-size graphs.

📊 3️⃣ DFS-Based Clone (Iterative using Stack)

Algorithm Steps:

1. Use a stack to simulate DFS traversal.

2. Maintain a map<Node*, Node*> for cloning references.

3. Clone each unvisited neighbor during traversal.

4. Append the neighbors to the corresponding clone.

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        unordered_map<Node*, Node*> m;
        stack<Node*> st;
        st.push(node);
        m[node] = new Node(node->val);

        while (!st.empty()) {
            Node* curr = st.top(); st.pop();
            for (auto neighbor : curr->neighbors) {
                if (!m.count(neighbor)) {
                    m[neighbor] = new Node(neighbor->val);
                    st.push(neighbor);
                }
                m[curr]->neighbors.push_back(m[neighbor]);
            }
        }
        return m[node];
    }
};

📝 Complexity Analysis:

• Time Complexity: O(N + M) — Visit every node and edge once.

• Space Complexity: O(N) — Hashmap and stack.

✅ Why This Approach?

Avoids recursion and risk of stack overflow. Ideal when recursion depth is a limitation.

🆚 Comparison of Approaches

Approach	⏱️ Time Complexity	🗂️ Space Complexity	✅ Pros	⚠️ Cons
BFS (Queue + Map)	🟡 O(N + M)	🟢 O(N)	Iterative, clean traversal	Slightly more space for queue
DFS (Recursive)	🟡 O(N + M)	🟢 O(N)	Concise and elegant	Risk of stack overflow on deep graphs
DFS (Iterative using Stack)	🟡 O(N + M)	🟢 O(N)	Avoids recursion limit	More verbose and a bit complex

✅ Best Choice?

• Use BFS for queue-based iterative style and easier debugging.

• Prefer Recursive DFS for elegance, unless you're dealing with very deep or cyclic graphs.

• Choose Iterative DFS if recursion depth is a concern or restricted.

Code (Java)

class Solution {
    Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> m = new HashMap<>();
        Queue<Node> q = new LinkedList<>();
        m.put(node, new Node(node.val));
        q.add(node);
        while (!q.isEmpty()) {
            for (Node n : q.peek().neighbors) {
                if (!m.containsKey(n)) {
                    m.put(n, new Node(n.val));
                    q.add(n);
                }
                m.get(q.peek()).neighbors.add(m.get(n));
            }
            q.poll();
        }
        return m.get(node);
    }
}

Code (Python)

class Solution:
    def cloneGraph(self, node):
        if not node: return None
        m, q = {node: Node(node.val)}, [node]
        while q:
            for n in q[0].neighbors:
                if n not in m:
                    m[n] = Node(n.val)
                    q.append(n)
                m[q[0]].neighbors.append(m[n])
            q.pop(0)
        return m[node]

Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count