Bài học

Biểu diễn cây và duyệt DFS/BFS

Mục tiêu bài học

Sau bài này, em biểu diễn được một cây bằng danh sách kề hoặc mảng $parent[]$ , và cài đúng hai chiến lược duyệt cây — DFS đệ quy (đi sâu trước) và BFS bằng hàng đợi (đi theo từng mức) — cùng biết chọn chiến lược nào cho từng loại bài toán.

Sau bài này, em biểu diễn được một cây bằng danh sách kề hoặc mảng $parent[]$, và cài đúng hai chiến lược duyệt cây — DFS đệ quy (đi sâu trước) và BFS bằng hàng đợi (đi theo từng mức) — cùng biết chọn chiến lược nào cho từng loại bài toán.

Cần nhớ trước

Em cần nhớ lại: đệ quy và cách một hàm tự gọi chính nó với bài toán nhỏ hơn (Course 4), hàng đợi FIFO và cách dùng collections.deque (Course 3), và ký hiệu độ phức tạp $O(n)$ , $O(n+m)$ .

Em cần nhớ lại: đệ quy và cách một hàm tự gọi chính nó với bài toán nhỏ hơn (Course 4), hàng đợi FIFO và cách dùng `collections.deque` (Course 3), và ký hiệu độ phức tạp $O(n)$, $O(n+m)$.

So với mức chuẩn: Tin học 11 CT GDPT 2018 giới thiệu cây như một cấu trúc dữ liệu mới, thường dừng ở việc nhận biết khái niệm gốc, đỉnh, con, lá và cách vẽ một cây nhỏ. Đề HSG đòi hỏi nhiều hơn thế: chọn đúng cách biểu diễn cho một cây có thể lên tới hàng chục nghìn đỉnh, cài đặt DFS/BFS chạy đúng độ phức tạp $O(n)$ , và — khi cây quá sâu — biết vì sao bản đệ quy thô (không phòng bị) có thể sập giữa chừng.

**So với mức chuẩn:** Tin học 11 CT GDPT 2018 giới thiệu cây như một cấu trúc dữ liệu mới, thường dừng ở việc nhận biết khái niệm gốc, đỉnh, con, lá và cách vẽ một cây nhỏ. Đề HSG đòi hỏi nhiều hơn thế: chọn đúng cách biểu diễn cho một cây có thể lên tới hàng chục nghìn đỉnh, cài đặt DFS/BFS chạy đúng độ phức tạp $O(n)$, và — khi cây quá sâu — biết vì sao bản đệ quy thô (không phòng bị) có thể sập giữa chừng.

Bài toán mở đầu — vì sao mảng và danh sách liền kề không đủ

Ở Course 2 và Course 3, mỗi phần tử của một dãy chỉ có nhiều nhất một phần tử "tiếp theo". Giờ hãy thử biểu diễn một cây thư mục: thư mục gốc chứa ba thư mục con, một trong ba thư mục đó lại chứa hai thư mục con khác. Không có một mảng một chiều nào diễn tả được quan hệ "một đỉnh có nhiều con" này một cách tự nhiên — cần một cấu trúc dữ liệu mới cho quan hệ phân nhánh.

Ý tưởng cốt lõi — biểu diễn và hai chiến lược duyệt

Cách biểu diễn gọn nhất là danh sách kề (adjacency list): một dict ánh xạ mỗi đỉnh sang danh sách các con trực tiếp của nó, ví dụ adj = {1: [2, 3, 4], 2: [5, 6]} nghĩa là đỉnh 1 có ba con 2, 3, 4, và đỉnh 2 có hai con 5, 6 (các đỉnh không xuất hiện làm khoá coi như không có con — là lá). Cách thứ hai là mảng parent[], mỗi đỉnh chỉ giữ cha của chính nó — gọn hơn khi chỉ cần leo lên gốc, nhưng phải xây lại danh sách kề nếu muốn duyệt xuống (Course sau sẽ cần cả hai chiều). Có cây rồi, hai câu hỏi tự nhiên là: đi hết mọi đỉnh theo thứ tự nào? DFS chọn "đi sâu trước" — thăm một con, đi hết nhánh dưới con đó rồi mới quay lại xét con kế tiếp; BFS chọn "đi rộng trước" — thăm hết mọi đỉnh ở mức hiện tại rồi mới sang mức kế tiếp.

Cách biểu diễn gọn nhất là **danh sách kề** (adjacency list): một `dict` ánh xạ mỗi đỉnh sang danh sách các con trực tiếp của nó, ví dụ `adj = {1: [2, 3, 4], 2: [5, 6]}` nghĩa là đỉnh 1 có ba con 2, 3, 4, và đỉnh 2 có hai con 5, 6 (các đỉnh không xuất hiện làm khoá coi như không có con — là lá). Cách thứ hai là mảng `parent[]`, mỗi đỉnh chỉ giữ cha của chính nó — gọn hơn khi chỉ cần leo lên gốc, nhưng phải xây lại danh sách kề nếu muốn duyệt xuống (Course sau sẽ cần cả hai chiều). Có cây rồi, hai câu hỏi tự nhiên là: đi hết mọi đỉnh theo thứ tự nào? DFS chọn "đi sâu trước" — thăm một con, đi hết nhánh dưới con đó rồi mới quay lại xét con kế tiếp; BFS chọn "đi rộng trước" — thăm hết mọi đỉnh ở mức hiện tại rồi mới sang mức kế tiếp.

Ví dụ

Ví dụ 1 — DFS đệ quy trên một cây 6 đỉnh

1
Đệ quy trên mảng một chiều (Course 4) chỉ có một hướng đi — từ phần tử $i$ sang $i+1$ . Trên cây, một đỉnh có thể có nhiều con, nên hàm đệ quy phải tự quyết định thứ tự xử lý các con — đây là bước chuyển từ đệ quy tuyến tính sang đệ quy phân nhánh.
Đệ quy trên mảng một chiều (Course 4) chỉ có một hướng đi — từ phần tử $i$ sang $i+1$. Trên cây, một đỉnh có thể có nhiều con, nên hàm đệ quy phải tự quyết định thứ tự xử lý các con — đây là bước chuyển từ đệ quy tuyến tính sang đệ quy phân nhánh.
2
DFS preorder: in đỉnh hiện tại trước, rồi đệ quy lần lượt vào từng con theo đúng thứ tự chúng xuất hiện trong danh sách kề. Khi một lời gọi con kết thúc (đã đi hết nhánh dưới nó), hàm quay lui về xét con tiếp theo.

def dfs_preorder(adj, root):
    order = []
    def go(u):
        order.append(u)
        for v in adj[u]:
            go(v)
    go(root)
    return order

adj = {1: [2, 3, 4], 2: [5, 6], 3: [], 4: [], 5: [], 6: []}
print(dfs_preorder(adj, 1))

4
Chạy đoạn mã trên in ra [1, 2, 5, 6, 3, 4]. Đỉnh 2 đứng trước 3 trong adj[1] nên go(2) được gọi trước — và vì go(2) phải đi hết nhánh dưới nó (gồm 5, 6) trước khi trả về, cả ba đỉnh 2, 5, 6 xuất hiện liền nhau, trước khi 3 và 4 được xét.
Chạy đoạn mã trên in ra `[1, 2, 5, 6, 3, 4]`. Đỉnh 2 đứng trước 3 trong `adj[1]` nên `go(2)` được gọi trước — và vì `go(2)` phải đi hết nhánh dưới nó (gồm 5, 6) trước khi trả về, cả ba đỉnh 2, 5, 6 xuất hiện liền nhau, trước khi 3 và 4 được xét.
5
DFS preorder thăm cha trước con — dùng khi cần xử lý một đỉnh trước khi biết thông tin từ con của nó (in tên thư mục cha trước khi liệt kê file bên trong). Đối lập là DFS postorder (thăm con trước cha) — sẽ dùng ở Bài 4 để tính kích thước từng cây con.
6
Ta có cây gồm 6 đỉnh với danh sách kề đã cho. Xét lời gọi $go(1)$ : hàm in ra $1$ , rồi lần lượt gọi $go(2)$ , $go(3)$ , $go(4)$ theo đúng thứ tự trong $adj[1]$ . Vì $go(2)$ được gọi trước nên toàn bộ nhánh gốc tại $2$ (gồm $2, 5, 6$ ) được duyệt xong trước khi quay lại xét $3$ . $(1)$ Suy ra thứ tự thăm là $1, 2, 5, 6, 3, 4$ . Mỗi đỉnh được thăm đúng một lần, và mỗi cạnh được xét đúng một lần khi duyệt danh sách kề của đỉnh cha nó, nên tổng công việc là $O(n + m)$ — với cây thì $m = n - 1$ nên độ phức tạp gọn thành $O(n)$ . $(2)$ Kết hợp $(1)$ và $(2)$ : DFS preorder trên cây này cho thứ tự thăm $1, 2, 5, 6, 3, 4$ với độ phức tạp $O(n)$ . Vậy $order = [1, 2, 5, 6, 3, 4]$ .
Ta có cây gồm 6 đỉnh với danh sách kề đã cho. Xét lời gọi $go(1)$: hàm in ra $1$, rồi lần lượt gọi $go(2)$, $go(3)$, $go(4)$ theo đúng thứ tự trong $adj[1]$. Vì $go(2)$ được gọi trước nên toàn bộ nhánh gốc tại $2$ (gồm $2, 5, 6$) được duyệt xong trước khi quay lại xét $3$. $(1)$ Suy ra thứ tự thăm là $1, 2, 5, 6, 3, 4$. Mỗi đỉnh được thăm đúng một lần, và mỗi cạnh được xét đúng một lần khi duyệt danh sách kề của đỉnh cha nó, nên tổng công việc là $O(n + m)$ — với cây thì $m = n - 1$ nên độ phức tạp gọn thành $O(n)$. $(2)$ Kết hợp $(1)$ và $(2)$: DFS preorder trên cây này cho thứ tự thăm $1, 2, 5, 6, 3, 4$ với độ phức tạp $O(n)$. Vậy $order = [1, 2, 5, 6, 3, 4]$.

Ví dụ

Ví dụ 2 — BFS theo từng mức, tính độ sâu mọi đỉnh

1
BFS trên cây phải xử lý đúng số con thay đổi của từng đỉnh (không cố định như 4 hướng trên lưới ô vuông), và có thể dùng để tính luôn độ sâu (khoảng cách tới gốc) của mọi đỉnh trong một lượt duyệt duy nhất.
2
Dùng hàng đợi FIFO (Course 3): đưa gốc vào hàng đợi với độ sâu 0, rồi lặp lại — lấy một đỉnh ra, xử lý nó, đưa các con của nó vào hàng đợi với độ sâu tăng thêm 1. Vì hàng đợi giữ đúng thứ tự vào trước ra trước, mọi đỉnh ở mức $k$ được xử lý xong trước khi đỉnh đầu tiên ở mức $k+1$ được lấy ra.
Dùng hàng đợi FIFO (Course 3): đưa gốc vào hàng đợi với độ sâu 0, rồi lặp lại — lấy một đỉnh ra, xử lý nó, đưa các con của nó vào hàng đợi với độ sâu tăng thêm 1. Vì hàng đợi giữ đúng thứ tự vào trước ra trước, mọi đỉnh ở mức $k$ được xử lý xong trước khi đỉnh đầu tiên ở mức $k+1$ được lấy ra.

from collections import deque

def bfs_depth(adj, root):
    order = []
    depth = {root: 0}
    q = deque([root])
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            depth[v] = depth[u] + 1
            q.append(v)
    return order, depth

adj = {1: [2, 3, 4], 2: [5, 6], 3: [], 4: [], 5: [], 6: []}
order, depth = bfs_depth(adj, 1)
print(order)
print(depth)

4
Kết quả: order = [1, 2, 3, 4, 5, 6] và depth = {1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2}. Khác hẳn thứ tự DFS ở Ví dụ 1 — ba đỉnh 2, 3, 4 (cùng mức 1) đứng liền nhau ngay sau gốc, thay vì bị chen bởi nhánh con của 2.
5
BFS luôn thăm hết mức $k$ trước khi sang mức $k+1$ , nên depth[] tính được ngay trong lúc duyệt mà không cần một hàm đệ quy riêng — một lợi thế khi cây quá sâu để đệ quy an toàn (xem Mở rộng dành cho HSG bên dưới).
BFS luôn thăm hết mức $k$ trước khi sang mức $k+1$, nên `depth[]` tính được ngay trong lúc duyệt mà không cần một hàm đệ quy riêng — một lợi thế khi cây quá sâu để đệ quy an toàn (xem Mở rộng dành cho HSG bên dưới).
6
Ta có hàng đợi FIFO đảm bảo đỉnh nào được đưa vào trước thì được lấy ra và xử lý trước. $(1)$ Vì mọi đỉnh ở mức $k$ đều được đưa vào hàng đợi trong lúc xử lý các đỉnh ở mức $k-1$ , nên chúng đứng liền nhau trong hàng đợi và được lấy ra theo đúng thứ tự mức. $(2)$ Kết hợp $(1)$ và $(2)$ : thứ tự lấy ra khỏi hàng đợi chính là thứ tự duyệt theo từng mức $1, 2, 3, 4, 5, 6$ , với độ sâu tương ứng $0, 1, 1, 1, 2, 2$ . Mỗi đỉnh được đưa vào và lấy ra khỏi hàng đợi đúng một lần nên độ phức tạp là $O(n)$ . Vậy BFS cho thứ tự thăm $1, 2, 3, 4, 5, 6$ với $depth = \{0, 1, 1, 1, 2, 2\}$ .
Ta có hàng đợi FIFO đảm bảo đỉnh nào được đưa vào trước thì được lấy ra và xử lý trước. $(1)$ Vì mọi đỉnh ở mức $k$ đều được đưa vào hàng đợi trong lúc xử lý các đỉnh ở mức $k-1$, nên chúng đứng liền nhau trong hàng đợi và được lấy ra theo đúng thứ tự mức. $(2)$ Kết hợp $(1)$ và $(2)$: thứ tự lấy ra khỏi hàng đợi chính là thứ tự duyệt theo từng mức $1, 2, 3, 4, 5, 6$, với độ sâu tương ứng $0, 1, 1, 1, 2, 2$. Mỗi đỉnh được đưa vào và lấy ra khỏi hàng đợi đúng một lần nên độ phức tạp là $O(n)$. Vậy BFS cho thứ tự thăm $1, 2, 3, 4, 5, 6$ với $depth = \{0, 1, 1, 1, 2, 2\}$.

Bẫy thường gặp

Ba lỗi hay gặp: nghĩ rằng DFS luôn "nhanh hơn" hoặc "chậm hơn" BFS — cả hai đều $O(n)$ trên cây, chúng khác nhau ở THỨ TỰ thăm, không phải tốc độ; quên rằng DFS đệ quy trên cây rất sâu (n tới $10^5$ ) có thể vượt giới hạn đệ quy mặc định của Python và dừng bằng lỗi; và mang thói quen dùng mảng $visited[]$ từ đồ thị tổng quát sang cây rồi thắc mắc vì sao "thừa" — trên cây, từ gốc chỉ có đúng một đường tới mỗi đỉnh nên DFS/BFS không bao giờ quay lại một đỉnh đã thăm.

Ba lỗi hay gặp: nghĩ rằng DFS luôn "nhanh hơn" hoặc "chậm hơn" BFS — cả hai đều $O(n)$ trên cây, chúng khác nhau ở THỨ TỰ thăm, không phải tốc độ; quên rằng DFS đệ quy trên cây rất sâu (n tới $10^5$) có thể vượt giới hạn đệ quy mặc định của Python và dừng bằng lỗi; và mang thói quen dùng mảng $visited[]$ từ đồ thị tổng quát sang cây rồi thắc mắc vì sao "thừa" — trên cây, từ gốc chỉ có đúng một đường tới mỗi đỉnh nên DFS/BFS không bao giờ quay lại một đỉnh đã thăm.

Ví dụ

Ví dụ 3 — Mở rộng dành cho HSG: DFS bằng ngăn xếp tường minh

1
Mở rộng dành cho HSG: kỹ thuật này không nằm trong YCCĐ Lớp 11 — nó đòi hỏi hiểu vì sao đệ quy có giới hạn ở tầng hệ thống, không chỉ đúng thuật toán. Tiên quyết: cấu trúc ngăn xếp (Course 3).
2
Thay ngăn xếp lời gọi hàm (ẩn, do Python quản lý) bằng một ngăn xếp tường minh — một list Python. Mỗi bước: lấy đỉnh ở đỉnh ngăn xếp ra, xử lý nó, rồi đẩy các con vào. Vì ngăn xếp là LIFO (vào sau ra trước), muốn con đầu tiên được xử lý trước, ta phải đẩy nó vào SAU CÙNG — tức đẩy danh sách con theo thứ tự đảo ngược.
Thay ngăn xếp lời gọi hàm (ẩn, do Python quản lý) bằng một ngăn xếp tường minh — một `list` Python. Mỗi bước: lấy đỉnh ở đỉnh ngăn xếp ra, xử lý nó, rồi đẩy các con vào. Vì ngăn xếp là LIFO (vào sau ra trước), muốn con đầu tiên được xử lý trước, ta phải đẩy nó vào SAU CÙNG — tức đẩy danh sách con theo thứ tự đảo ngược.

def dfs_iterative(adj, root):
    order = []
    stack = [root]
    while stack:
        u = stack.pop()
        order.append(u)
        for v in reversed(adj[u]):
            stack.append(v)
    return order

adj = {1: [2, 3, 4], 2: [5, 6], 3: [], 4: [], 5: [], 6: []}
print(dfs_iterative(adj, 1))

4
Kết quả: [1, 2, 5, 6, 3, 4] — trùng khớp tuyệt đối với DFS đệ quy ở Ví dụ 1. Thử nghiệm trên một cây thẳng 5000 đỉnh (mỗi đỉnh chỉ có một con) với giới hạn đệ quy của Python đặt gần mức mặc định: bản đệ quy báo lỗi RecursionError giữa chừng, còn bản ngăn xếp tường minh duyệt trọn vẹn cả 5000 đỉnh.
Kết quả: `[1, 2, 5, 6, 3, 4]` — trùng khớp tuyệt đối với DFS đệ quy ở Ví dụ 1. Thử nghiệm trên một cây thẳng 5000 đỉnh (mỗi đỉnh chỉ có một con) với giới hạn đệ quy của Python đặt gần mức mặc định: bản đệ quy báo lỗi `RecursionError` giữa chừng, còn bản ngăn xếp tường minh duyệt trọn vẹn cả 5000 đỉnh.
5
sys.getrecursionlimit() của Python thường trả về $1000$ — một cây thẳng sâu hơn con số đó là đủ để DFS đệ quy sập. Với dữ liệu HSG có thể lên tới $n = 10^5$ , luôn cân nhắc bản ngăn xếp tường minh cho DFS trên cây có thể suy biến gần-thành-dãy.
`sys.getrecursionlimit()` của Python thường trả về $1000$ — một cây thẳng sâu hơn con số đó là đủ để DFS đệ quy sập. Với dữ liệu HSG có thể lên tới $n = 10^5$, luôn cân nhắc bản ngăn xếp tường minh cho DFS trên cây có thể suy biến gần-thành-dãy.
6
Ta có ngăn xếp hoạt động theo nguyên tắc vào sau ra trước. $(1)$ Muốn con đầu tiên trong $adj[u]$ được xử lý trước — đúng thứ tự DFS đệ quy — ta phải đẩy nó vào ngăn xếp sau cùng, tức đẩy các con theo thứ tự ngược lại. $(2)$ Kết hợp $(1)$ và $(2)$ : vòng lặp "lấy ra rồi đẩy con theo thứ tự đảo ngược" tái tạo đúng thứ tự thăm của DFS đệ quy, $1, 2, 5, 6, 3, 4$ . Vì cách này không dùng ngăn xếp lời gọi hàm của Python, số lời gọi lồng nhau không còn bị giới hạn bởi $sys.getrecursionlimit()$ . Vậy khi đề cho cây sâu tới $10^5$ đỉnh, DFS bằng ngăn xếp tường minh là lựa chọn an toàn, độ phức tạp vẫn $O(n)$ .
Ta có ngăn xếp hoạt động theo nguyên tắc vào sau ra trước. $(1)$ Muốn con đầu tiên trong $adj[u]$ được xử lý trước — đúng thứ tự DFS đệ quy — ta phải đẩy nó vào ngăn xếp sau cùng, tức đẩy các con theo thứ tự ngược lại. $(2)$ Kết hợp $(1)$ và $(2)$: vòng lặp "lấy ra rồi đẩy con theo thứ tự đảo ngược" tái tạo đúng thứ tự thăm của DFS đệ quy, $1, 2, 5, 6, 3, 4$. Vì cách này không dùng ngăn xếp lời gọi hàm của Python, số lời gọi lồng nhau không còn bị giới hạn bởi $sys.getrecursionlimit()$. Vậy khi đề cho cây sâu tới $10^5$ đỉnh, DFS bằng ngăn xếp tường minh là lựa chọn an toàn, độ phức tạp vẫn $O(n)$.

So khớp từng bước với đoạn mã đệ quy ở Ví dụ 1 — mỗi lần go(v) được gọi là một bước trong sơ đồ.

Đối chiếu với Ví dụ 2: ba đỉnh cùng mức 1 (2, 3, 4) đứng liền nhau, khác hẳn thứ tự DFS ở sơ đồ trên.

Luyện tập có hướng dẫn

Luyện tập độc lập

Thử thách

Tóm tắt

Cây biểu diễn tự nhiên bằng danh sách kề (mỗi đỉnh giữ danh sách con) hoặc mảng $parent[]$ (mỗi đỉnh giữ cha). DFS đệ quy đi sâu vào một nhánh trước khi quay lại xét nhánh khác; BFS bằng hàng đợi đi hết một mức trước khi sang mức kế tiếp — cả hai đều $O(n)$ , khác nhau ở thứ tự chứ không phải tốc độ. Khi cây quá sâu cho đệ quy an toàn, thay hàm đệ quy bằng một ngăn xếp tường minh vẫn giữ nguyên thứ tự thăm mà không bị giới hạn đệ quy của Python.

Cây biểu diễn tự nhiên bằng danh sách kề (mỗi đỉnh giữ danh sách con) hoặc mảng $parent[]$ (mỗi đỉnh giữ cha). DFS đệ quy đi sâu vào một nhánh trước khi quay lại xét nhánh khác; BFS bằng hàng đợi đi hết một mức trước khi sang mức kế tiếp — cả hai đều $O(n)$, khác nhau ở thứ tự chứ không phải tốc độ. Khi cây quá sâu cho đệ quy an toàn, thay hàm đệ quy bằng một ngăn xếp tường minh vẫn giữ nguyên thứ tự thăm mà không bị giới hạn đệ quy của Python.

Bài sau thu hẹp phạm vi vào một dạng cây có tính chất thứ tự đặc biệt — cây nhị phân tìm kiếm — nơi DFS theo một thứ tự cụ thể (duyệt trung tố) cho ra chính dãy số đã sắp xếp.