Clone Graph: sao chép sâu một cấu trúc đồ thị có chu trình

Bài toán trông đơn giản cho đến khi bạn nghĩ đến chu trình. Bạn có một đồ thị vô hướng liên thông — bất kỳ số lượng node nào, mỗi node có một danh sách neighbors — và bạn cần trả về một bản sao hoàn toàn độc lập. Cùng cấu trúc, cùng giá trị, nhưng không chia sẻ object reference nào. Cái khiến bài này thực sự khó: các node trỏ đến nhau, nên nếu đệ quy clone node 1 mà không kiểm soát, sẽ lại đệ quy ngược về node 1 và chạy mãi mãi. Đó là vấn đề cốt lõi. Mọi thứ còn lại chỉ là bookkeeping.

Bài toán là LeetCode 133. Đồ thị có nhiều nhất 100 node, không có self-loop và không có cạnh trùng lặp.

Constraints nói gì

0 <= số node <= 100. Rất nhỏ. Mọi thuật toán nào duyệt mỗi node và cạnh đúng một lần — O(N + M) — là đủ nhanh. Không có áp lực phải nghĩ đến O(log N). Điều thú vị ở đây là cấu trúc của đồ thị, không phải kích thước.

Node.val là duy nhất và thuộc [1, 100]. Điều này có nghĩa là bạn có thể dùng object node gốc làm key trong hash map (theo identity, không phải giá trị). Trên thực tế đó chính xác là những gì bạn làm: original_node -> cloned_node. Vì giá trị là unique, bạn cũng có thể dùng một mảng kích thước 101 thay cho hash map — nhưng hash map rõ ràng hơn và tôi không thấy có lý do gì để tối ưu ở đây.

Đồ thị liên thông. Mọi node đều có thể tiếp cận từ node đầu tiên. Bạn không cần xử lý các thành phần không liên thông — một lần duyệt từ node 1 là đủ để thăm tất cả.

Không có self-loop, không có cạnh trùng lặp. Điều này không thay đổi thuật toán nhưng có nghĩa là bạn không cần xử lý trường hợp một node là neighbor của chính nó.

Đồ thị có chu trình. Đây là constraint buộc toàn bộ thiết kế. Bạn không thể clone một đồ thị có chu trình bằng đệ quy đơn giản mà không theo dõi node nào đã clone rồi.

DFS với hash map

Ý tưởng cốt lõi: dùng hash map để theo dõi những node gốc nào đã được clone. Trước khi đệ quy vào neighbors của một node, tạo và đăng ký clone của nó. Bước đăng ký đó chính là thứ phá vỡ chu trình.

Đây là điều xảy ra nếu bạn không làm theo đúng thứ tự:

clone(1) -> create clone_1 -> clone(2) -> create clone_2
         -> clone(1)                    # 1 là neighbor của 2
         -> create ANOTHER clone_1      # lặp vô hạn

Giải pháp: tạo clone và đưa vào map trước khi xử lý neighbors. Mọi lần đệ quy sau đó đến cùng node sẽ tìm thấy clone sẵn có và trả về ngay, không đệ quy thêm.

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
 
        cloned = {}
 
        def dfs(n):
            if n in cloned:
                return cloned[n]
 
            clone = Node(n.val)
            cloned[n] = clone           # đăng ký trước khi đệ quy
 
            for neighbor in n.neighbors:
                clone.neighbors.append(dfs(neighbor))
 
            return clone
 
        return dfs(node)

public class Solution {
    public Node CloneGraph(Node node) {
        if (node == null) return null;
 
        var cloned = new Dictionary<Node, Node>();
        return Dfs(node, cloned);
    }
 
    private Node Dfs(Node node, Dictionary<Node, Node> cloned) {
        if (cloned.ContainsKey(node))
            return cloned[node];
 
        var clone = new Node(node.val);
        cloned[node] = clone;           // đăng ký trước khi đệ quy
 
        foreach (var neighbor in node.neighbors)
            clone.neighbors.Add(Dfs(neighbor, cloned));
 
        return clone;
    }
}

Phiên bản Python dùng closure để truy cập cloned từ nested function. Phiên bản C# truyền nó như một parameter — cùng logic, khác convention về scope.

Trace qua ví dụ mẫu

Ví dụ chuẩn: bốn node theo hình vuông. Adjacency: 1-2, 1-4, 2-3, 3-4. Bắt đầu từ node 1:

Từng bước theo neighbor list:

dfs(1)         -> tạo clone_1, đăng ký 1->clone_1
  dfs(2)       -> tạo clone_2, đăng ký 2->clone_2
    dfs(1)     -> có trong map, return clone_1
    dfs(3)     -> tạo clone_3, đăng ký 3->clone_3
      dfs(2)   -> có trong map, return clone_2
      dfs(4)   -> tạo clone_4, đăng ký 4->clone_4
        dfs(1) -> có trong map, return clone_1
        dfs(3) -> có trong map, return clone_3
      clone_3.neighbors = [clone_2, clone_4]
    clone_2.neighbors = [clone_1, clone_3]
  dfs(4)       -> có trong map, return clone_4
clone_1.neighbors = [clone_2, clone_4]

Mỗi node được tạo đúng một lần. Mỗi back-edge đều resolve về một clone đã tồn tại. Cấu trúc kết quả đẳng cấu với đồ thị gốc.

BFS với queue

BFS là một lựa chọn thay thế trực tiếp. Thay vì đệ quy, bạn duy trì một queue tường minh chứa các node gốc cần xử lý. Hash map đóng vai trò giống hệt — nó cho biết một neighbor đã được clone chưa.

Điểm khác biệt chính trong cấu trúc code: với DFS, bạn append vào clone.neighbors sau khi lời gọi đệ quy trả về. Với BFS, bạn append trong vòng lặp, dựa vào thực tế là clone đã được tạo (dù chưa được populate đầy đủ) khi bạn lần đầu gặp nó.

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

public class Solution {
    public Node CloneGraph(Node node) {
        if (node == null) return null;
 
        var cloned = new Dictionary<Node, Node>();
        cloned[node] = new Node(node.val);
        var queue = new Queue<Node>();
        queue.Enqueue(node);
 
        while (queue.Count > 0) {
            var current = queue.Dequeue();
            foreach (var neighbor in current.neighbors) {
                if (!cloned.ContainsKey(neighbor)) {
                    cloned[neighbor] = new Node(neighbor.val);
                    queue.Enqueue(neighbor);
                }
                cloned[current].neighbors.Add(cloned[neighbor]);
            }
        }
 
        return cloned[node];
    }
}

Lưu ý: clone của neighbor được tạo khi lần đầu gặp nó (khi là neighbor của bất kỳ node nào đã xử lý), trước khi bản thân neighbor được dequeue. Điều đó ổn — chúng ta chỉ set val lúc tạo. Danh sách neighbors sẽ được populate khi neighbor cuối cùng được dequeue. Nhưng chúng ta đã có thể append cloned[neighbor] vào neighbor list của node hiện tại vì object clone đã tồn tại.

So sánh hai cách tiếp cận

Thời gian giống nhau — mỗi node và cạnh được xử lý đúng một lần trong cả hai trường hợp. Bộ nhớ cũng gần tương đương: DFS dùng O(N) cho hash map cộng O(H) cho call stack với H là độ dài đường đi dài nhất trong đồ thị, còn BFS dùng O(N) cho hash map cộng O(N) cho queue ở kích thước lớn nhất. Với N=100 cả hai đều không quan trọng.

Sự khác biệt thực tế là rủi ro stack overflow. Với N=100 và độ sâu đệ quy tối đa 100 frame, DFS hoàn toàn an toàn ở đây. Nếu bạn đang clone một đồ thị với hàng triệu node xếp theo một chuỗi dài, DFS đệ quy sẽ overflow còn BFS thì không. Với constraints này, tôi sẽ dùng DFS — code ngắn hơn và ý định rõ ràng hơn.

Edge cases

Input null. node là null (Python: None). Cả hai implementation đều kiểm tra điều này đầu tiên và trả về null ngay lập tức. Hash map không cần tạo.

Node đơn, không có neighbors. adjList = [[]]. DFS tạo một clone, không tìm thấy neighbor nào để đệ quy, và trả về clone. Đúng.

Đồ thị tự tham chiếu. Constraints nói không có self-loop, nhưng thử xem điều gì xảy ra nếu một node có trong danh sách neighbor của chính nó: DFS sẽ gọi dfs(node) trong khi đang xử lý neighbors của node, tìm thấy node đã có trong map, và trả về clone hiện có. Không có đệ quy vô hạn. Bất biến đăng ký-trước-đệ quy xử lý được cả trường hợp này.

Chuỗi tuyến tính. Các node tạo thành một đường đi: 1-2-3-...-100. DFS đệ quy sâu 100 cấp. Ổn với kích thước này. Chuỗi không có chu trình nên mỗi node chỉ gặp đúng một lần từ một hướng.

Đồ thị đầy đủ (K_n). Mỗi node kết nối với mọi node còn lại. N=100 có nghĩa là mỗi node có 99 neighbors. Tổng cạnh: N*(N-1)/2 ≈ 5,000. Vẫn là O(N + M), vẫn ổn. Lần kiểm tra hash map ở đầu mỗi lời gọi DFS ngăn mọi công việc thừa.

Mental model và khả năng tổng quát hóa

Bài toán này là một trường hợp của một pattern chung: duyệt với memo table. Bạn đang thực hiện graph traversal (DFS hoặc BFS), và bạn đang xây dựng thứ gì đó trong quá trình đó. Memo table (hash map từ node gốc đến clone) phục vụ hai mục đích đồng thời: nó ngăn việc thăm lại node (vai trò visited set thông thường), và nó ánh xạ node cũ sang node mới để bạn có thể nối cạnh trong bản clone.

Pattern tương tự xuất hiện trong:

• Copy List with Random Pointer (LeetCode 138) — linked list mà mỗi node có con trỏ next và con trỏ random có thể trỏ đến bất kỳ đâu. Con trỏ random tạo ra rủi ro chu trình theo nghĩa cấu trúc tương tự. Cùng giải pháp: hash map từ node gốc đến clone, một hoặc hai lần duyệt tùy phiên bản.
• Copy Binary Tree with Random Pointer (LeetCode 1485) — ý tưởng tương tự trên tree, với twist là random pointers tạo ra rủi ro chu trình.
• Number of Islands (200) — không có cloning, nhưng DFS traversal với visited marker có cấu trúc giống hệt. Marker ngăn việc vào lại cells theo cùng cách hash map ngăn vào lại nodes.
• Pacific Atlantic Water Flow (417) — multi-source BFS từ hai biên, xây dựng visited set cho mỗi biên. Cách quản lý queue phản ánh cách tiếp cận BFS clone.

Series tiếp tục với Number of Islands và sau đó là Course Schedule — bài sau thêm cạnh có hướng và yêu cầu bạn phát hiện chu trình một cách tường minh thay vì chỉ tránh duyệt vô hạn. Clone Graph là bài đồ thị đầu tiên tốt vì vấn đề chu trình mang tính cơ học: một hash map, một quy tắc về thứ tự. Các bài khó hơn đòi hỏi bạn phải suy nghĩ về ý nghĩa của chu trình.