Đọc và xử lý cây bằng duyệt theo lớp

Lan quản lý sáu trạm trong một khu vườn. Năm lối đi nối các trạm thành một mạng liên thông, không có vòng khép kín. Lan muốn tìm trạm xa cổng nhất và biết lối dài nhất giữa hai trạm. Chọn cổng làm mốc sẽ cho mỗi trạm một trạm cha và một độ sâu. Hai lần duyệt còn giúp tìm đường dài nhất mà không cần thử từng cặp trạm.

Cây nối mọi đỉnh bằng đúng một đường đi đơn

Một đồ thị vô hướng (undirected graph) gồm các đỉnh và các cạnh hai chiều. Một đường đi đơn (simple path) không đi qua cùng một đỉnh hai lần. Một cây (tree) là đồ thị vô hướng liên thông và không có chu trình. Liên thông nghĩa là từ mỗi đỉnh đều có đường đi đến mọi đỉnh khác. Không có chu trình nghĩa là không thể đi theo các cạnh rồi quay về điểm xuất phát mà không lặp cạnh.

Giữa hai đỉnh của cây có đúng một đường đi đơn. Liên thông bảo đảm có ít nhất một đường đi. Nếu có hai đường khác nhau, phần tách ra rồi gặp lại tạo thành chu trình. Tính duy nhất này cho phép ta nói đến đường đi giữa hai trạm mà không cần chọn tuyến.

Hình sau có sáu đỉnh và năm cạnh. Chẳng hạn, đường duy nhất từ 4 đến 6 là 4–2–1–3–6.

Với n đỉnh, cây có n - 1 cạnh. Có thể hình dung lần lượt gắn mỗi đỉnh mới vào một đỉnh đã có bằng một cạnh. Thêm một cạnh nối hai đỉnh đang có tạo chu trình, vì giữa chúng đã có một đường đi. Bỏ một cạnh làm cây tách thành hai phần, vì không còn đường đi khác giữa hai đầu cạnh đó.

Chỉ đếm n - 1 cạnh chưa đủ nếu đề không bảo đảm đầu vào hợp lệ. Một đồ thị có chu trình ở một nơi và một đỉnh cô lập ở nơi khác vẫn có thể có n - 1 cạnh. Với đồ thị vô hướng đơn, n - 1 cạnh cùng tính liên thông mới đủ kết luận là cây.

Đoạn sau xây danh sách kề và in số cạnh của ví dụ:

n = 6
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]
g = [[] for _ in range(n + 1)]
for u, v in edges:
    g[u].append(v)
    g[v].append(u)
print("kề 2:", g[2])
print("số cạnh:", sum(len(row) for row in g) // 2)

kề 2: [1, 4, 5]
số cạnh: 5

Mỗi cạnh xuất hiện hai lần trong tổng độ dài danh sách kề. Chia hai trả lại số cạnh thực. Tạo danh sách bằng biểu thức trong ví dụ giúp mỗi đỉnh có một danh sách riêng. Dùng [[]] * (n + 1) lại tạo nhiều tham chiếu đến cùng một danh sách.

Chọn gốc tạo quan hệ cha, con và độ sâu

Gốc (root) là đỉnh được chọn làm mốc. Với mỗi đỉnh khác gốc, cha (parent) là đỉnh ngay trước nó trên đường từ gốc. Những đỉnh có cùng cha là các con (children) của cha đó. Độ sâu (depth) là số cạnh trên đường từ gốc đến đỉnh. Gốc có độ sâu bằng 0.

Chọn gốc không đổi các cạnh, nhưng có thể đổi cha và độ sâu. Đỉnh 2 có cha là 1 nếu gốc là 1. Nếu chuyển gốc sang 4, cha của 2 lại là 4. Quy ước cha của gốc là 0 vì các đỉnh được đánh số từ 1.

Cây con (subtree) tại một đỉnh gồm chính đỉnh ấy và mọi hậu duệ của nó. Với gốc 1, cây con tại 2 gồm các đỉnh 2, 4 và 5. Bài 35 đã trình bày cách tính kích thước cây con; ở đây ta dùng quan hệ cha để xác định thành phần của nó.

Sau đây là cùng một mạng khi gốc chuyển sang 4. So sánh hai cách in giúp thấy quan hệ cha phụ thuộc gốc.

from collections import deque

g = [[], [2, 3], [1, 4, 5], [1, 6], [2], [2], [3]]
def root_tree(root):
    parent = [-1] * len(g)
    depth = [0] * len(g)
    parent[root] = 0
    q = deque([root])
    while q:
        u = q.popleft()
        for v in g[u]:
            if parent[v] == -1:
                parent[v] = u
                depth[v] = depth[u] + 1
                q.append(v)
    return parent[1:], depth[1:]

for root in (1, 4):
    print(root, root_tree(root))

1 ([0, 1, 1, 2, 2, 3], [0, 1, 1, 2, 2, 2])
4 ([2, 4, 1, 0, 2, 3], [2, 1, 3, 0, 2, 4])

Mỗi đỉnh chưa thăm có parent = -1. Đánh dấu ngay khi đưa vào hàng đợi giúp không đưa cùng đỉnh vào hai lần. Trong cây, mỗi đỉnh khác gốc có đúng một đường từ gốc, nên cha được gán là đúng.

Duyệt theo lớp tính cha và độ sâu trong một lượt

Duyệt theo chiều rộng (breadth-first search, BFS) xử lý các đỉnh theo thứ tự khoảng cách tăng dần từ điểm xuất phát. Hàng đợi chứa các đỉnh đã phát hiện nhưng chưa xét hết hàng xóm. Khi lấy u ra, mỗi hàng xóm chưa thăm v nhận parent[v] = u và depth[v] = depth[u] + 1.

Đề thường cho n rồi đến n - 1 dòng cạnh. Chương trình sau chọn gốc 1 và in cha, độ sâu theo thứ tự số đỉnh:

6
1 2
1 3
2 4
2 5
3 6

from collections import deque

n = int(input())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)
parent = [-1] * (n + 1)
depth = [0] * (n + 1)
parent[1] = 0
q = deque([1])
while q:
    u = q.popleft()
    for v in g[u]:
        if parent[v] == -1:
            parent[v] = u
            depth[v] = depth[u] + 1
            q.append(v)
for u in range(1, n + 1):
    print(u, parent[u], depth[u])

1 0 0
2 1 1
3 1 1
4 2 2
5 2 2
6 3 2

Vì mọi cạnh được lưu hai lần, tổng số lần xét hàng xóm là 2(n - 1). Mỗi đỉnh vào hàng đợi một lần. Thời gian và bộ nhớ đều là O(n). Với n = 100000, chương trình xét 199998 lượt kề, thay vì duyệt lại toàn bộ cây cho từng đỉnh.

deque.popleft() lấy đầu hàng đợi hiệu quả. Dùng list.pop(0) phải dồn các phần tử còn lại và có thể làm chậm đáng kể. Duyệt lặp cũng tránh giới hạn độ sâu đệ quy khi cây kéo dài thành một đường thẳng.

Nếu đề đảm bảo đầu vào là cây, có thể bỏ qua riêng cạnh về cha thay vì dùng dấu chưa thăm. Tuy nhiên, cách đó không đủ an toàn với một đồ thị có chu trình. Khi chưa biết đầu vào hợp lệ, dùng mảng đã thăm và kiểm tra số đỉnh đã đến được.

from collections import deque

g = [[], [2], [1, 3], [2], []]
seen = {1}
q = deque([1])
while q:
    u = q.popleft()
    for v in g[u]:
        if v not in seen:
            seen.add(v)
            q.append(v)
print("số đỉnh tới được:", len(seen))
print("liên thông:", len(seen) == 4)

số đỉnh tới được: 3
liên thông: False

Đỉnh 4 không được phát hiện. Vì vậy số nhãn đỉnh trong đầu vào không thay thế được phép kiểm tra liên thông.

Lá của cây có gốc là đỉnh không có con

Một lá (leaf) trong cây có gốc là đỉnh không có con. Với gốc 1 của mạng ban đầu, các lá là 4, 5 và 6. Gốc có thể là lá nếu cây chỉ có một đỉnh.

Bậc (degree) của một đỉnh là số cạnh kề với nó. Mọi đỉnh khác gốc có bậc một đều là lá: cạnh duy nhất dẫn về cha. Ngược lại, gốc bậc một vẫn có một con và không phải lá. Do đó không thể đếm lá có gốc bằng cách đếm bậc một mà bỏ qua gốc.

Đoạn dưới kiểm tra cùng một đường ba đỉnh với hai cách chọn gốc:

from collections import deque

g = [[], [2], [1, 3], [2]]
def leaves(root):
    parent = [-1] * len(g)
    parent[root] = 0
    q = deque([root])
    while q:
        u = q.popleft()
        for v in g[u]:
            if parent[v] == -1:
                parent[v] = u
                q.append(v)
    return [u for u in range(1, len(g))
            if not any(parent[v] == u for v in g[u])]

print("gốc 1:", leaves(1))
print("gốc 2:", leaves(2))

gốc 1: [3]
gốc 2: [1, 3]

Với gốc 1, đỉnh 1 chỉ có một cạnh nhưng có con 2. Với gốc 2, cả 1 và 3 đều là lá. Trên cây một đỉnh, danh sách kề rỗng nên điều kiện không có con vẫn đúng.

g = [[], []]
root = 1
print("số cạnh:", len(g[root]))
print("là lá:", len(g[root]) == 0)

số cạnh: 0
là lá: True

Hai lượt duyệt tìm đường kính cây không trọng số

Khoảng cách (distance) giữa hai đỉnh ở đây là số cạnh trên đường nối chúng. Đường kính (diameter) là khoảng cách lớn nhất giữa hai đỉnh bất kỳ. Cây một đỉnh có đường kính 0. Đường kính không phụ thuộc gốc được chọn.

Từ một đỉnh bất kỳ s, duyệt để tìm đỉnh xa nhất a. Từ a, duyệt lần nữa để tìm đỉnh xa nhất b. Khoảng cách a đến b là đường kính. Nếu có nhiều đỉnh xa nhất, chọn bất kỳ đỉnh nào trong số đó.

Từ 1, đỉnh 4, 5 và 6 đều cách hai cạnh. Chọn 4 làm a. Từ 4, đỉnh xa nhất là 6, cách bốn cạnh. Đường kính là bốn, không phải năm đỉnh nằm trên đường.

Vì sao đầu xa nhất có thể là đầu đường kính? Gọi x–y là một đường kính và xét điểm t nơi đường từ s gặp đường kính. Xét một nhánh xuất phát từ điểm p trên đường kính. Nhánh đó không thể dài hơn đoạn p–x hay đoạn p–y. Nếu dài hơn, ghép nhánh với đầu đối diện sẽ tạo đường dài hơn đường kính. Vì a xa s nhất, xét vị trí nhánh chứa a so với t cho thấy đường từ a đến ít nhất một trong x, y có độ dài không nhỏ hơn đường kính. Không đường nào dài hơn đường kính, nên đường đó cũng là đường kính. Lập luận dùng tính duy nhất của đường đi trong cây và độ dài cạnh không âm.

Ví dụ sau in cả hai đầu được chọn lẫn độ dài. Hàm nhận danh sách kề và trả về đỉnh xa nhất cùng bảng khoảng cách.

from collections import deque

g = [[], [2, 3], [1, 4, 5], [1, 6], [2], [2], [3]]
def farthest(start):
    dist = [-1] * len(g)
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    far = max(range(1, len(g)), key=lambda u: dist[u])
    return far, dist

a, _ = farthest(1)
b, dist = farthest(a)
print("hai đầu:", a, b)
print("độ dài:", dist[b])

hai đầu: 4 6
độ dài: 4

Hai lượt duyệt cùng tốn O(n) thời gian và O(n) bộ nhớ. Thử BFS từ mọi đỉnh cần O(n²) trên cây, quá nhiều với 100000 đỉnh. Các đoạn mã dùng số cạnh làm khoảng cách; cạnh có trọng số cần cộng trọng số thay vì cộng 1. Với trọng số âm, không áp dụng kết luận hai lượt trên một cách tùy tiện.

Bán kính cho biết vị trí đặt trạm trực tốt nhất

Giả sử cần đặt một trạm trực tại một đỉnh sao cho trạm xa nhất cách nó ít nhất có thể. Khoảng cách lớn nhất từ một đỉnh đến các đỉnh khác là độ lệch tâm (eccentricity) của đỉnh đó. Giá trị nhỏ nhất trong các độ lệch tâm là bán kính (radius).

Với đường kính dài D cạnh của cây không trọng số, bán kính bằng (D + 1) // 2. Đỉnh giữa của đường kính đạt được giá trị này. Nếu D chẵn có một đỉnh giữa; nếu D lẻ có hai đỉnh giữa. Không thể làm tốt hơn vì mọi vị trí đều cách ít nhất một đầu đường kính ít nhất một nửa D làm tròn lên.

Để thấy các vị trí giữa, lưu cha trong lượt duyệt thứ hai rồi lần ngược từ b đến a:

from collections import deque

g = [[], [2, 3], [1, 4, 5], [1, 6], [2], [2], [3]]
def bfs(start):
    dist = [-1] * len(g)
    parent = [0] * len(g)
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    far = max(range(1, len(g)), key=lambda u: dist[u])
    return far, dist, parent

a, _, _ = bfs(1)
b, dist, parent = bfs(a)
path = []
u = b
while u:
    path.append(u)
    u = parent[u]
d = dist[b]
print("đường kính:", path)
print("bán kính:", (d + 1) // 2)
print("trung tâm:", path[d // 2:d // 2 + 1 + d % 2])

đường kính: [6, 3, 1, 2, 4]
bán kính: 2
trung tâm: [1]

Mảng path đi từ b về a, nên đảo chiều không làm đổi các đỉnh giữa. Khi D = 0, lát cắt vẫn chọn đúng đỉnh duy nhất. Khi D = 3, hai vị trí giữa nằm ở chỉ số 1 và 2.

Nhiều điểm xuất phát giúp tìm trạm gần nhất

Giả sử một số trạm đã có nhân viên. Với mỗi địa điểm, ta muốn biết nó cách trạm có nhân viên gần nhất bao nhiêu cạnh. Chạy một lượt BFS từ từng trạm rồi lấy nhỏ nhất cho kết quả đúng, nhưng lặp lại việc duyệt. Với k trạm và n đỉnh, cách này tốn O(kn) thời gian.

Thay vào đó, dùng BFS nhiều nguồn (multi-source BFS). Đặt khoảng cách của tất cả trạm bằng 0 và đưa tất cả vào hàng đợi trước khi duyệt. Các lớp khoảng cách lan ra đồng thời. Khi một đỉnh được phát hiện lần đầu, không nguồn nào có thể đến nó bằng ít cạnh hơn, vì hàng đợi xử lý lớp gần trước lớp xa.

Trên đường 1–2–3–4–5, đặt trạm ở 1 và 5. Hai trạm cùng tạo lớp 0; các đỉnh 2 và 4 thuộc lớp 1; đỉnh 3 thuộc lớp 2. Đỉnh 3 có thể được phát hiện từ phía 2 hoặc phía 4, nhưng khoảng cách gần nhất không đổi.

Chương trình sau in khoảng cách theo thứ tự nhãn đỉnh. Ban đầu -1 chỉ đỉnh chưa được phát hiện.

from collections import deque

g = [[], [2], [1, 3], [2, 4], [3, 5], [4]]
stations = [1, 5]
dist = [-1] * len(g)
q = deque(stations)
for s in stations:
    dist[s] = 0
while q:
    u = q.popleft()
    for v in g[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)
print(dist[1:])
print("khoảng cách lớn nhất:", max(dist[1:]))

[0, 1, 2, 1, 0]
khoảng cách lớn nhất: 2

Mỗi đỉnh chỉ vào hàng đợi một lần, kể cả khi nhiều nguồn có thể đến cùng lúc. Các cạnh vẫn được xét hai lượt, nên thời gian là O(n) và bộ nhớ là O(n). Nếu mọi đỉnh đều có trạm, tất cả khoảng cách là 0. Đề cần có ít nhất một trạm để khái niệm gần nhất có nghĩa.

Lỗi thường gặp

Tóm tắt

Cây liên thông, không có chu trình và có đúng một đường đi đơn giữa mỗi cặp đỉnh. Chọn gốc tạo cha, con và độ sâu. BFS với danh sách kề tính các giá trị này trong O(n). Lá là đỉnh không có con. Hai lượt BFS tìm đường kính của cây không trọng số; bán kính là nửa đường kính làm tròn lên.

Kiểm tra nhanh

Đọc thêm

• Breadth-first search — CP-Algorithms
• Hàng đợi với deque — tài liệu Python