Nối mạng tiết kiệm với cây khung nhỏ nhất

Lan cần nối bốn phòng máy bằng dây mạng. Các đoạn dây có giá lần lượt là 1, 2, 3, 4 và 6 đơn vị. Lan muốn mọi phòng liên lạc được, nhưng không muốn mua dây thừa.

Cây khung nối tất cả các đỉnh mà không có chu trình

Mỗi phòng là một đỉnh (vertex), mỗi đoạn dây là một cạnh (edge). Số ghi trên cạnh là trọng số (weight), ở đây biểu thị chi phí. Đồ thị là vô hướng vì dây dùng được theo cả hai chiều.

Một cây khung (spanning tree) gồm tất cả các đỉnh, liên thông và không có chu trình. Với n đỉnh, cây khung có đúng n - 1 cạnh. Nếu đồ thị ban đầu không liên thông, không có cây khung bao phủ mọi đỉnh.

Cây khung nhỏ nhất (minimum spanning tree, viết tắt MST) là cây khung có tổng trọng số nhỏ nhất. Có thể có nhiều MST với cùng tổng, chẳng hạn khi các cạnh bằng trọng số. Một đồ thị chỉ có một đỉnh vẫn có cây khung với tổng bằng 0.

Xét các cạnh của mạng bốn phòng. Chương trình dưới đây tính tổng chi phí của một cách nối đã chọn.

edges = [(1, 2, 1), (2, 3, 2), (3, 4, 4)]
print(sum(w for _, _, w in edges))
print(len(edges))

7
3

Ba cạnh nối bốn phòng thành một đường liên tục. Tổng là 7 và không có chu trình. Để biết tổng 7 có nhỏ nhất không, ta cần so sánh có hệ thống với các cách nối khác.

Tổng chi phí toàn mạng khác độ dài một đường đi

Đường đi ngắn nhất tối ưu chi phí giữa hai đỉnh được chỉ định. MST tối ưu tổng chi phí các cạnh của cả mạng. Hai mục tiêu đó có thể dẫn đến các cạnh khác nhau.

Với tam giác sau, đường đi trực tiếp từ 1 đến 3 có giá 3. Hai cạnh còn lại đều có giá 2.

direct = 3
via_two = 2 + 2
tree_total = 2 + 2
print("đường trực tiếp:", direct)
print("đường qua 2:", via_two)
print("tổng cây:", tree_total)

đường trực tiếp: 3
đường qua 2: 4
tổng cây: 4

Đường trực tiếp rẻ hơn đường qua 2. Tuy nhiên, cây gồm hai cạnh giá 2 có tổng 4, nhỏ hơn cây gồm cạnh giá 3 và một cạnh giá 2. Vì vậy đường 1 đến 3 trong MST không nhất thiết là đường ngắn nhất ban đầu.

Kruskal lần lượt chọn cạnh rẻ không tạo chu trình

Thuật toán Kruskal (Kruskal's algorithm) sắp xếp các cạnh theo trọng số tăng dần. Ta giữ một rừng (forest), tức tập các cây chưa nối với nhau. Ban đầu mỗi đỉnh là một cây riêng.

Khi xét cạnh nối hai cây khác nhau, ta chọn cạnh rồi gộp hai cây. Nếu hai đầu đã thuộc cùng một cây, ta bỏ cạnh vì nó tạo chu trình. Dừng khi đã chọn n - 1 cạnh hoặc hết cạnh.

Cạnh 1-3 bị bỏ vì sau hai lựa chọn đầu đã có đường 1-2-3. Cạnh 3-4 nối phòng còn lại; lúc ấy đã đủ ba cạnh nên không cần xét 2-4. Bảng không ghi quyết định chọn hay bỏ cho cạnh chưa được xét.

Ta có thể dùng một mô phỏng nhỏ để xem các cạnh được chọn. Bộ nhóm đơn giản này dễ quan sát nhưng không dùng cho dữ liệu lớn.

edges = [(1, 1, 2), (2, 2, 3), (3, 1, 3), (4, 3, 4), (6, 2, 4)]
group = [0, 1, 2, 3, 4]
chosen = []
for w, u, v in sorted(edges):
    if group[u] != group[v]:
        old, new = group[v], group[u]
        group = [new if x == old else x for x in group]
        chosen.append((u, v, w))
        if len(chosen) == 3:
            break
print(chosen)
print(sum(w for _, _, w in chosen))

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

Danh sách kết quả chỉ chứa ba cạnh được chọn. Vòng lặp dừng ngay sau cạnh thứ ba, nên cạnh cuối không được xét. Cách đổi nhãn cả danh sách tốn O(n) mỗi lần gộp; DSU giúp xử lý hiệu quả hơn.

DSU cho biết hai đầu cạnh đã nối với nhau chưa

Cấu trúc tập hợp rời nhau (disjoint set union, DSU) lưu các nhóm đỉnh đã nối bằng cạnh được chọn. Xem Bài 20 để ôn cách nén đường đi và gộp theo kích thước. Ở đây, find(u) == find(v) nghĩa là đã có đường giữa hai đầu trong rừng hiện tại.

Khi hai đại diện khác nhau, gộp nhóm tạo một đường nối mới mà không tạo chu trình. Khi chúng giống nhau, một đường đã tồn tại; thêm cạnh tạo chu trình. Mỗi lần gộp thành công làm số thành phần giảm một.

Chương trình sau minh họa việc kiểm tra đại diện trên ba đỉnh.

parent = [0, 1, 1, 3]
def find(x):
    while parent[x] != x:
        x = parent[x]
    return x
print(find(1) == find(2))
print(find(1) == find(3))

True
False

Đỉnh 1 và 2 đã cùng nhóm, còn 3 ở nhóm riêng. Đại diện chỉ là nhãn để so sánh; không nên kết luận đỉnh có số nhỏ nhất là đại diện.

Thứ tự cập nhật rất quan trọng. Trước hết tìm đại diện của cả hai đầu. Chỉ khi hai đại diện khác nhau, ta nối một gốc vào gốc kia, cập nhật kích thước rồi cộng trọng số. Nếu cộng trước khi kiểm tra, cạnh tạo chu trình vẫn bị tính vào tổng.

Sau mỗi lần gộp, các cạnh đã chọn trong từng nhóm vẫn tạo thành cây. Nối hai cây khác nhau bằng một cạnh tạo một cây lớn hơn. Trong khi đó, nối hai đỉnh của cùng một cây tạo thêm đường thứ hai giữa chúng và hình thành chu trình.

Một lần quét cạnh tạo ra MST hoặc phát hiện không thể nối

Chương trình nhận n m, rồi m dòng u v w. Các đỉnh đánh số từ 1 đến n; cạnh có thể có trọng số âm hoặc bằng nhau. Nếu không nối được tất cả đỉnh, chương trình in IMPOSSIBLE.

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

import sys

data = list(map(int, sys.stdin.read().split()))
n, m = data[:2]
edges = []
for i in range(m):
    u, v, w = data[2 + 3*i:5 + 3*i]
    edges.append((w, u, v))
edges.sort()
parent = list(range(n + 1))
size = [1] * (n + 1)

def find(x):
    while x != parent[x]:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

total = 0
chosen = 0
for w, u, v in edges:
    a, b = find(u), find(v)
    if a == b:
        continue
    if size[a] < size[b]:
        a, b = b, a
    parent[b] = a
    size[a] += size[b]
    total += w
    chosen += 1
    if chosen == n - 1:
        break
print(total if chosen == n - 1 else "IMPOSSIBLE")

7

Kết quả là tổng 7, đúng bằng cách nối ở đầu bài, nên cách nối đó là một MST. Việc sắp xếp bộ (w, u, v) đặt trọng số lên trước; hai đầu chỉ quyết định thứ tự khi trọng số bằng nhau.

Ở dữ liệu này, sau cạnh giá 1, các nhóm là {1, 2}, {3} và {4}. Sau cạnh giá 2, ba đỉnh đầu ở cùng nhóm. Cạnh giá 3 nối 1 với 3 nên bị bỏ, dù giá của nó nhỏ hơn giá 4.

Tiếp đó, cạnh giá 4 nối nhóm ba đỉnh với đỉnh 4. Ta cộng giá này, tăng chosen lên 3 và dừng. Tổng 7 gồm 1, 2 và 4; nó không gồm cạnh giá 3 đã bỏ hoặc cạnh giá 6 chưa xét.

Để dùng danh sách cạnh ở nơi khác sau khi sắp xếp, có thể tạo bản mới bằng sorted(edges). Lệnh edges.sort() trong chương trình thay đổi chính danh sách đó. Hai cách đều cho đúng thứ tự theo trọng số nếu phần tử bắt đầu bằng w.

Với n = 1 và không có cạnh, chosen = 0 = n - 1, nên kết quả là 0. Nếu n > 1 và thiếu cạnh nối, chosen < n - 1. Khi đó tổng đã cộng chỉ là chi phí của một rừng, không phải MST của toàn mạng.

Nếu một số dây đã lắp và bắt buộc giữ, trước tiên gộp hai đầu từng dây có sẵn trong DSU. Các dây này không tốn thêm tiền, nên có thể xem chúng có giá 0 và xét trước các dây mua có giá dương. Cáp sẵn tạo chu trình vẫn được giữ; phép gộp không làm giảm số thành phần khi hai đầu đã cùng nhóm.

Trong ví dụ sau, ba phòng đầu đã nối sẵn. Ta xét các dây có thể mua theo giá tăng, chỉ cộng tiền khi dây nối hai nhóm, rồi dừng khi còn một nhóm.

n = 4
installed = [(1, 2), (2, 3), (1, 3)]
offers = [(1, 1, 3), (3, 2, 4), (5, 3, 4)]
parent = list(range(n + 1))
size = [1] * (n + 1)
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
def union(u, v):
    a, b = find(u), find(v)
    if a == b:
        return False
    if size[a] < size[b]:
        a, b = b, a
    parent[b] = a
    size[a] += size[b]
    return True
components = n
for u, v in installed:
    if union(u, v):
        components -= 1
total = 0
for w, u, v in sorted(offers):
    if components == 1:
        break
    if union(u, v):
        components -= 1
        total += w
print(total if components == 1 else "IMPOSSIBLE")

3

Cạnh sẵn 1-3 tạo chu trình nên không giảm số nhóm; cáp đó vẫn được giữ. Cáp mua giá 1 cũng không nối nhóm mới; cáp giá 3 nối phòng 4 với ba phòng đầu. Đếm thành phần giúp kết luận đúng ngay cả khi số cáp sẵn lớn hơn số lần gộp thành công.

Cạnh âm, cạnh song song và cạnh tự nối vẫn có quy tắc rõ ràng

Trọng số âm có thể biểu thị khoản trợ giá. Kruskal vẫn xét cạnh âm trước, và không cần loại cạnh âm chỉ vì giá của nó nhỏ hơn 0. Hai cạnh song song có cùng hai đầu; cạnh rẻ hơn được xét trước.

Một cạnh tự nối có hai đầu trùng nhau. Hai đầu đã cùng nhóm ngay từ đầu, nên cạnh đó bị bỏ dù trọng số âm. Cạnh như vậy không giúp nối thêm phòng và không được thuộc cây khung.

edges = [(-5, 1, 1), (-2, 1, 2), (3, 1, 2)]
for w, u, v in sorted(edges):
    print(u, v, w, "tự nối" if u == v else "giữa hai đỉnh")

1 1 -5 tự nối
1 2 -2 giữa hai đỉnh
1 2 3 giữa hai đỉnh

Cạnh giá -5 tự nối nên bị bỏ. Trong mạng chỉ có hai đỉnh này, cạnh giá -2 tạo cây khung; cạnh giá 3 không cần xét sau khi đã chọn đủ một cạnh. Nếu không dừng sớm, DSU cũng loại cạnh giá 3 vì hai đầu đã nối.

Lập luận đổi cạnh giải thích lựa chọn tham lam

Giả sử các cạnh đã chọn đều nằm trong một MST nào đó. Ta xét cạnh e rẻ nhất còn lại nối hai thành phần khác nhau của rừng. Nếu MST đó đã chứa e, điều cần chứng minh đã xong.

Nếu không, thêm e vào MST tạo đúng một chu trình. Trên đường cũ giữa hai đầu e, có một cạnh f đi ra khỏi thành phần chứa đầu thứ nhất. Cạnh f không thuộc rừng đã chọn, vì các cạnh trong rừng không đi ra khỏi thành phần của nó.

Do Kruskal xét cạnh theo thứ tự tăng dần, f không thể có trọng số nhỏ hơn e. Nếu nhỏ hơn, nó đã được xét và hai đầu đã khác nhóm khi ấy. Các nhóm chỉ gộp thêm, nên khi đó f đã được chọn; điều này mâu thuẫn với việc nó đi ra khỏi thành phần hiện tại.

Thay f bằng e phá chu trình và vẫn nối mọi đỉnh. Tổng không tăng; vì cây ban đầu đã tối ưu, cây thay thế cũng là MST. Lặp lập luận này cho từng cạnh được chọn, ta giữ được một MST chứa toàn bộ rừng đã chọn.

Điểm mấu chốt là so sánh cạnh qua ranh giới của một thành phần hiện tại, không phải chọn tùy ý cạnh rẻ giữa hai tập bất kỳ. Đường trong MST phải đi từ thành phần đó ra ngoài để tới đầu còn lại của e. Vì vậy cạnh f cần cho phép đổi chắc chắn tồn tại.

old_total = 12
removed = 5
added = 4
print("tổng trước:", old_total)
print("tổng sau:", old_total - removed + added)
print("không tăng:", added <= removed)

tổng trước: 12
tổng sau: 11
không tăng: True

Đây chỉ là phép tính minh họa việc thay một cạnh. Trong chứng minh, tính liên thông và việc không tạo chu trình sau thay thế cũng cần được giải thích như trên. Nếu hai cạnh bằng giá, phép đổi giữ nguyên tổng và có thể tạo một MST khác.

Số cạnh được chọn quyết định rừng hay cây

Một rừng bắt đầu với n thành phần. Mỗi cạnh được chọn gộp đúng hai thành phần nên sau k cạnh còn n - k thành phần. Khi k = n - 1, chỉ còn một thành phần và rừng là cây khung.

n = 5
for chosen in range(5):
    print(chosen, n - chosen)

0 5
1 4
2 3
3 2
4 1

Khi duyệt hết cạnh mà còn nhiều thành phần, không có cạnh nào nối các thành phần đó trong đồ thị ban đầu. Các cây thu được tạo rừng khung nhỏ nhất (minimum spanning forest), mỗi cây tối ưu trong một thành phần liên thông. Đề yêu cầu một cây cho toàn mạng thì phải báo không thể, không được in tổng rừng như một MST.

Muốn giữ lại nhiều cụm, hãy dừng ở số thành phần yêu cầu

Giả sử bốn phòng cần chia thành đúng hai cụm độc lập. Ban đầu có bốn cụm; cần hai lần gộp thành công để còn hai. Ta xét cạnh tăng dần như Kruskal, nhưng dừng khi số cạnh đã chọn bằng n - k, với k là số cụm cần giữ.

Ví dụ, thứ tự các cạnh có giá 1, 2, 3, 4. Hai cạnh đầu nối lần lượt phòng 1 với 2 và phòng 2 với 3. Khi đó {1, 2, 3} là một cụm, còn {4} là cụm kia.

n, k = 4, 2
chosen_weights = [1, 2]
print("cạnh cần chọn:", n - k)
print("số cụm còn lại:", n - len(chosen_weights))
print("tổng:", sum(chosen_weights))

cạnh cần chọn: 2
số cụm còn lại: 2
tổng: 3

Mỗi cạnh được chọn là cạnh rẻ nhất hiện có nối hai thành phần. Lập luận đổi cạnh ở trên cũng áp dụng khi chỉ chọn đủ n - k cạnh. Nếu hết cạnh mà chưa đủ số lần gộp, không thể đạt đúng k cụm.

Trường hợp k = n cần kiểm tra ngay trước vòng lặp, vì chưa cần chọn cạnh nào. Với yêu cầu tổng nhỏ nhất của mọi tập cạnh, cách dừng ở rừng cần thêm điều kiện trọng số không âm. Nếu được phép chọn cạnh âm tạo chu trình, cạnh đó có thể làm tổng giảm mà không đổi số cụm.

Tính tiền bán cáp thừa bằng tổng trừ chi phí giữ lại

Một khu nhà đã mua ba đoạn cáp giá 2, 3 và 4. Để nối ba phòng, khu nhà giữ cây khung nhỏ nhất và bán các đoạn còn lại. Khi mọi giá không âm, bỏ cạnh thừa của một mạng liên thông không làm tăng tiền phải giữ.

all_costs = [2, 3, 4]
kept_costs = [2, 3]
print("đã mua:", sum(all_costs))
print("giữ lại:", sum(kept_costs))
print("bán được:", sum(all_costs) - sum(kept_costs))

đã mua: 9
giữ lại: 5
bán được: 4

Nếu đầu vào có cạnh song song hoặc tự nối, vẫn cộng giá của chúng vào tổng đã mua. Chúng chỉ được giữ lại khi thực sự cần trong cây; cạnh tự nối không bao giờ nối thêm phòng. Nếu mạng ban đầu không liên thông, đề cần quy định rõ có báo không thể hay chỉ tối ưu từng thành phần.

Không được áp dụng phép biến đổi này một cách máy móc khi giá có thể âm. Chẳng hạn, nếu giữ thêm một cạnh âm được phép và giúp giảm tổng giá giữ, cây khung không còn mô tả mọi lựa chọn tối ưu. Hãy đọc chính xác xem đề bắt buộc giữ một cây hay cho phép giữ mạng có chu trình.

Lưu cạnh được chọn khi đề cần phương án thi công

Có đề chỉ hỏi tổng, nhưng đội thi công cần biết đoạn dây nào được lắp. Khi find(u) khác find(v), ta lưu thêm cặp (u, v) hoặc mã cạnh gốc. Việc sắp xếp có thể thay thứ tự cạnh, nên mã cạnh gốc giúp phân biệt hai cạnh song song.

edges = [(4, 1, 2, 1), (2, 2, 3, 2), (3, 1, 3, 3)]
edges.sort()
print("thứ tự mã sau sắp xếp:", [edge[3] for edge in edges])
print("mã hai cạnh được chọn:", [edges[0][3], edges[1][3]])

thứ tự mã sau sắp xếp: [2, 3, 1]
mã hai cạnh được chọn: [2, 3]

Ví dụ này có ba đỉnh và hai cạnh rẻ nhất nối được cả ba. Với dữ liệu khác, không thể chỉ lấy n - 1 cạnh đầu: vẫn phải dùng DSU để loại chu trình. Khi có nhiều MST, chỉ in một phương án nếu đề chấp nhận bất kỳ phương án tối ưu nào.

Nếu đề yêu cầu thứ tự hoặc cách chọn duy nhất, hãy xem quy tắc phá hòa của đề. Thứ tự (w, u, v) tự phá hòa theo số hiệu hai đầu, nhưng không tự bảo đảm mọi quy tắc bổ sung. Tính đúng của tổng MST không phụ thuộc thứ tự giữa các cạnh cùng trọng số.

Chi phí sắp xếp thường lớn hơn chi phí DSU

Với n đỉnh và m cạnh, khởi tạo DSU tốn O(n). Sắp xếp cạnh tốn O(m log m); các thao tác DSU dùng nén đường đi và gộp theo kích thước có tổng gần tuyến tính. Cách viết đầy đủ là O(n + m log m + m α(n)), với α tăng rất chậm.

Ví dụ m = 100000 thì log₂(m) nhỏ hơn 17. Sắp xếp vì vậy có cỡ 1,7 triệu đơn vị tăng trưởng so sánh, không phải phép đo thời gian chính xác. Lưu danh sách cạnh và DSU tốn O(n + m) bộ nhớ.

import math
m = 100000
print(math.ceil(math.log2(m)))
print(m * math.ceil(math.log2(m)))

17
1700000

Con số này giúp so sánh quy mô với việc thử mọi tập cạnh, vốn tăng theo 2^m. Thời gian thực còn phụ thuộc dữ liệu, máy chấm và cách cài đặt.

Lỗi thường gặp

Tóm tắt

Kruskal xét cạnh tăng dần và dùng DSU để tránh chu trình. Sau n - 1 lần gộp thành công, tổng là chi phí MST. Nếu duyệt hết mà chưa đủ cạnh, đồ thị không có cây khung toàn mạng.

Kiểm tra nhanh

Đọc thêm

• Kruskal với DSU — CP-Algorithms
• DSU — CP-Algorithms