Giải thuật và lập trình: §9. Bài toán cây khung nhỏ nhất
Giải phóng thời gian, khai phóng năng lực
9.1. Bài toán cây khung nhỏ nhất
Cho G = (V, E) là đồ thị vô hướng liên thông có trọng số, với một cây khung T của G, ta gọi trọng số của cây T là tổng trọng số các cạnh trong T. Bài toán đặt ra là trong số các cây khung của G, chỉ ra cây khung có trọng số nhỏ nhất, cây khung như vậy được gọi là cây khung (hay cây bao trùm) nhỏ nhất của đồ thị, và bài toán đó gọi là bài toán cây khung nhỏ nhất. Sau đây ta sẽ xét hai thuật toán thông dụng để giải bài toán cây khung nhỏ nhất của đơn đồ thị vô hướng có trọng số.
Input: file văn bản MINTREE.INP:
• Dòng 1: Ghi hai số số đỉnh n (≤ 100) và số cạnh m của đồ thị cách nhau ít nhất 1 dấu cách
• m dòng tiếp theo, mỗi dòng có dạng 3 số u, v, c[u, v] cách nhau ít nhất 1 dấu cách thể hiện đồ thị có cạnh (u, v) và trọng số cạnh đó là c[u, v]. (c[u, v] là số nguyên có giá trị tuyệt đối không quá 100).
Output: file văn bản MINTREE.OUT ghi các cạnh thuộc cây khung và trọng số cây khung
9.2. Thuật toán Kruskal (Joseph Kruskal - 1956)
Thuật toán Kruskal dựa trên mô hình xây dựng cây khung bằng thuật toán hợp nhất (§5), chỉ có điều thuật toán không phải xét các cạnh với thứ tự tuỳ ý mà xét các cạnh theo thứ tự đã sắp xếp: Với đồ thị vô hướng G = (V, E) có n đỉnh. Khởi tạo cây T ban đầu không có cạnh nào. Xét tất cả các cạnh của đồ thị từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn, nếu việc thêm cạnh đó vào T không tạo thành chu trình đơn trong T thì kết nạp thêm cạnh đó vào T. Cứ làm như vậy cho tới khi:
Hoặc đã kết nạp được n - 1 cạnh vào trong T thì ta được T là cây khung nhỏ nhất.
Hoặc chưa kết nạp đủ n - 1 cạnh nhưng hễ cứ kết nạp thêm một cạnh bất kỳ trong số các cạnh còn lại thì sẽ tạo thành chu trình đơn. Trong trường hợp này đồ thị G là không liên thông, việc tìm kiếmcây khung thất bại.
Như vậy có hai vấn đề quan trọng khi cài đặt thuật toán Kruskal:
Thứ nhất, làm thế nào để xét được các cạnh từ cạnh có trọng số nhỏ tới cạnh có trọng số lớn. Ta có thể thực hiện bằng cách sắp xếp danh sách cạnh theo thứ tự không giảm của trọng số, sau đó duyệt\ từ đầu tới cuối danh sách cạnh. Trong trường hợp tổng quát, thuật toán HeapSort là hiệu quả nhất bởi nó cho phép chọn lần lượt các cạnh từ cạnh trọng nhỏ nhất tới cạnh trọng số lớn nhất ra khỏi Heap và có thể xử lý (bỏ qua hay thêm vào cây) luôn.
Thứ hai, làm thế nào kiểm tra xem việc thêm một cạnh có tạo thành chu trình đơn trong T hay không. Để ý rằng các cạnh trong T ở các bước sẽ tạo thành một rừng (đồ thị không có chu trình đơn). Muốn thêm một cạnh (u, v) vào T mà không tạo thành chu trình đơn thì (u, v) phải nối hai cây khác nhau của rừng T, bởi nếu u, v thuộc cùng một cây thì sẽ tạo thành chu trình đơn trong cây đó.
Ban đầu, ta khởi tạo rừng T gồm n cây, mỗi cây chỉ gồm đúng một đỉnh, sau đó, mỗi khi xét đến cạnh nối hai cây khác nhau của rừng T thì ta kết nạp cạnh đó vào T, đồng thời hợp nhất hai cây đó lại thành một cây.
Nếu cho mỗi đỉnh v trên cây một nhãn Lab[v] là số hiệu đỉnh cha của đỉnh v trong cây, trong trường hợp v là gốc của một cây thì Lab[v] được gán một giá trị âm. Khi đó ta hoàn toàn có thể xác định được gốc của cây chứa đỉnh v bằng hàm GetRoot dưới đây:
function GetRoot(v∈V): ∈V; begin while Lab[v] > 0 do v := Lab[v]; GetRoot := v; end;
Vậy để kiểm tra một cạnh (u, v) có nối hai cây khác nhau của rừng T hay không? ta có thể kiểm tra GetRoot(u) có khác GetRoot(v) hay không, bởi mỗi cây chỉ có duy nhất một gốc.
Để hợp nhất cây gốc r1 và cây gốc r2 thành một cây, ta lưu ý rằng mỗi cây ở đây chỉ dùng để ghi nhận một tập hợp đỉnh thuộc cây đó chứ cấu trúc cạnh trên cây thế nào thì không quan trọng. Vậy để hợp nhất cây gốc r1 và cây gốc r2, ta chỉ việc coi r1 là nút cha của r2 trong cây bằng cách đặt: Lab[r2] := r1.
Hai cây gốc r1 và r2 và cây mới khi hợp nhất chúng
Tuy nhiên, để thuật toán làm việc hiệu quả, tránh trường hợp cây tạo thành bị suy biến khiến cho hàm GetRoot hoạt động chậm, người ta thường đánh giá: Để hợp hai cây lại thành một, thì gốc cây nào ít nút hơn sẽ bị coi là con của gốc cây kia.
Thuật toán hợp nhất cây gốc r1 và cây gốc r2 có thể viết như sau:
{Count[k] là số đỉnh của cây gốc k} procedure Union(r1, r2 ∈ V); begin if Count[r1] < Count[r2] then {Hợp nhất thành cây gốc r2} begin Count[r2] := Count[r1] + Count[r2]; Lab[r1] := r2; end else {Hợp nhất thành cây gốc r1} begin Count[r1] := Count[r1] + Count[r2]; Lab[r2] := r1; end; end;
Khi cài đặt, ta có thể tận dụng ngay nhãn Lab[r] để lưu số đỉnh của cây gốc r, bởi như đã giải thích ở trên, Lab[r] chỉ cần mang một giá trị âm là đủ, vậy ta có thể coi Lab[r] = -Count[r] với r là gốc của một cây nào đó.
procedure Union(r1, r2 ∈ V); {Hợp nhất cây gốc r1 với cây gốc r2} begin x := Lab[r1] + Lab[r2]; {-x là tổng số nút của cả hai cây} if Lab[r1] > Lab[r2] then {Cây gốc r1 ít nút hơn cây gốc r2, hợp nhất thành cây gốc r2} begin Lab[r1] := r2; {r2 là cha của r1} Lab[r2] := x; {r2 là gốc cây mới, -Lab[r2] giờ đây là số nút trong cây mới} end else {Hợp nhất thành cây gốc r1} begin Lab[r1] := x; {r1 là gốc cây mới, -Lab[r1] giờ đây là số nút trong cây mới} Lab[r2] := r1; {cha của r2 sẽ là r1} end; end;
Mô hình thuật toán Kruskal:
for ∀k∈V do Lab[k] := -1; for ∀(u, v)∈E (theo thứ tự từ cạnh trọng số nhỏ tới cạnh trọng số lớn) do begin r1 := GetRoot(u); r2 := GetRoot(v); if r1 ≠ r2 then {(u, v) nối hai cây khác nhau} begin <Kết nạp (u, v) vào cây, nếu đã đủ n - 1 cạnh thì thuật toán dừng> Union(r1, r2); {Hợp nhất hai cây lại thành một cây} end; end;
P_4_09_1.PAS * Thuật toán Kruskal program Minimal_Spanning_Tree_by_Kruskal; const InputFile = 'MINTREE.INP'; OutputFile = 'MINTREE.OUT'; maxV = 100; maxE = (maxV - 1) * maxV div 2; type TEdge = record {Cấu trúc một cạnh} u, v, c: Integer; {Hai đỉnh và trọng số} Mark: Boolean; {Đánh dấu có được kết nạp vào cây khung hay không} end; var e: array[1..maxE] of TEdge; {Danh sách cạnh} Lab: array[1..maxV] of Integer; {Lab[v] là đỉnh cha của v, nếu v là gốc thì Lab[v] = - số con cây gốc v} n, m: Integer; Connected: Boolean; procedure LoadGraph; var i: Integer; f: Text; begin Assign(f, InputFile); Reset(f); ReadLn(f, n, m); for i := 1 to m do with e[i] do ReadLn(f, u, v, c); Close(f); end; procedure Init; var i: Integer; begin for i := 1 to n do Lab[i] := -1; {Rừng ban đầu, mọi đỉnh là gốc của cây gồm đúng một nút} for i := 1 to m do e[i].Mark := False; end; function GetRoot(v: Integer): Integer; {Lấy gốc của cây chứa v} begin while Lab[v] > 0 do v := Lab[v]; GetRoot := v; end; procedure Union(r1, r2: Integer); {Hợp nhất hai cây lại thành một cây} var x: Integer; begin x := Lab[r1] + Lab[r2]; if Lab[r1] > Lab[r2] then begin Lab[r1] := r2; Lab[r2] := x; end else begin Lab[r1] := x; Lab[r2] := r1; end; end; procedure AdjustHeap(root, last: Integer); {Vun thành đống, dùng cho HeapSort} var Key: TEdge; child: Integer; begin Key := e[root]; while root * 2 <= Last do begin child := root * 2; if (child < Last) and (e[child + 1].c < e[child].c) then Inc(child); if Key.c <= e[child].c then Break; e[root] := e[child]; root := child; end; e[root] := Key; end; procedure Kruskal; var i, r1, r2, Count, a: Integer; tmp: TEdge; begin Count := 0; Connected := False; for i := m div 2 downto 1 do AdjustHeap(i, m); for i := m - 1 downto 0 do begin tmp := e[1]; e[1] := e[i + 1]; e[i + 1] := tmp; AdjustHeap(1, i); r1 := GetRoot(e[i + 1].u); r2 := GetRoot(e[i + 1].v); if r1 <> r2 then {Cạnh e[i + 1] nối hai cây khác nhau} begin e[i + 1].Mark := True; {Kết nạp cạnh đó vào cây} Inc(Count); {Đếm số cạnh} if Count = n - 1 then {Nếu đã đủ số thì thành công} begin Connected := True; Exit; end; Union(r1, r2); {Hợp nhất hai cây thành một cây} end; end; end; procedure PrintResult; var i, Count, W: Integer; f: Text; begin Assign(f, OutputFile); Rewrite(f); if not Connected then WriteLn(f, 'Error: Graph is not connected') else begin WriteLn(f, 'Minimal spanning tree: '); Count := 0; W := 0; for i := 1 to m do {Duyệt danh sách cạnh} with e[i] do begin if Mark then {Lọc ra những cạnh đã kết nạp vào cây khung} begin WriteLn(f, '(', u, ', ', v, ') = ', c); Inc(Count); W := W + c; end; if Count = n - 1 then Break; {Cho tới khi đủ n - 1 cạnh} end; WriteLn(f, 'Weight = ', W); end; Close(f); end; begin LoadGraph; Init; Kruskal; PrintResult; end.
Xét về độ phức tạp tính toán, ta có thể chứng minh được rằng thao tác GetRoot có độ phức tạp là O(log2n), còn thao tác Union là O(1). Giả sử ta đã có danh sách cạnh đã sắp xếp rồi thì xét vòng lặp dựng cây khung, nó duyệt qua danh sách cạnh và với mỗi cạnh nó gọi 2 lần thao tác GetRoot, vậy thì độ phức tạp là O(mlog2n), nếu đồ thị có cây khung thì m ≥ n-1 nên ta thấy chi phí thời gian chủ yếu sẽ nằm ở thao tác sắp xếp danh sách cạnh bởi độ phức tạp của HeapSort là O(mlog2m). Vậy độ phức tạp tính toán của thuật toán là O(mlog2m) trong trường hợp xấu nhất. Tuy nhiên, phải lưu ý rằng để xây dựng cây khung thì ít khi thuật toán phải duyệt toàn bộ danh sách cạnh mà chỉ một phần của danh sách cạnh mà thôi.
9.3. Thuật toán Prim (Robert Prim - 1957)
Thuật toán Kruskal hoạt động chậm trong trường hợp đồ thị dày (có nhiều cạnh). Trong trường hợp đó người ta thường sử dụng phương pháp lân cận gần nhất của Prim. Thuật toán đó có thể phát biểu
hình thức như sau:
Đơn đồ thị vô hướng G = (V, E) có n đỉnh được cho bởi ma trận trong số C. Qui ước c[u, v] = +∞ nếu (u, v) không là cạnh. Xét cây T trong G và một đỉnh v, gọi khoảng cách từ v tới T là trọng số nhỏ nhất trong số các cạnh nối v với một đỉnh nào đó trong T: d[v] = min{c[u, v] ⎪ u∈T}
Ban đầu khởi tạo cây T chỉ gồm có mỗi đỉnh {1}. Sau đó cứ chọn trong số các đỉnh ngoài T ra một đỉnh gần T nhất, kết nạp đỉnh đó vào T đồng thời kết nạp luôn cả cạnh tạo ra khoảng cách gần nhất đó. Cứ làm như vậy cho tới khi:
Hoặc đã kết nạp được tất cả n đỉnh thì ta có T là cây khung nhỏ nhất.
Hoặc chưa kết nạp được hết n đỉnh nhưng mọi đỉnh ngoài T đều có khoảng cách tới T là +∞. Khi đó đồ thị đã cho không liên thông, ta thông báo việc tìm cây khung thất bại.
Về mặt kỹ thuật cài đặt, ta có thể làm như sau:
Sử dụng mảng đánh dấu Free. Free[v] = TRUE nếu như đỉnh v chưa bị kết nạp vào T.
Gọi d[v] là khoảng cách từ v tới T. Ban đầu khởi tạo d[1] = 0 còn d[2] = d[3] = ... = d[n] = +∞. Tại mỗi bước chọn đỉnh đưa vào T, ta sẽ chọn đỉnh u nào ngoài T và có d[u] nhỏ nhất. Khi kết nạp u
vào T rồi thì rõ ràng các nhãn d[v] sẽ thay đổi: d[v]mới := min(d[v]cũ, c[u, v]). Vấn đề chỉ có vậy (chương trình rất giống thuật toán Dijkstra, chỉ khác ở công thức tối ưu nhãn).
P_4_09_2.PAS * Thuật toán Prim program Minimal_Spanning_Tree_by_Prim; const InputFile = 'MINTREE.INP'; OutputFile = 'MINTREE.OUT'; max = 100; maxC = 10000; var c: array[1..max, 1..max] of Integer; d: array[1..max] of Integer; Free: array[1..max] of Boolean; Trace: array[1..max] of Integer; {Vết, Trace[v] là đỉnh cha của v trong cây khung nhỏ nhất} n, m: Integer; Connected: Boolean; procedure LoadGraph; {Nhập đồ thị} var i, u, v: Integer; f: Text; begin Assign(f, InputFile); Reset(f); ReadLn(f, n, m); for u := 1 to n do for v := 1 to n do if u = v then c[u, v] := 0 else c[u, v] := maxC; {Khởi tạo ma trận trọng số} for i := 1 to m do begin ReadLn(f, u, v, c[u, v]); c[v, u] := c[u, v]; end; Close(f); end; procedure Init; var v: Integer; begin d[1] := 0; {Đỉnh 1 có nhãn khoảng cách là 0} for v := 2 to n do d[v] := maxC; {Các đỉnh khác có nhãn khoảng cách +∞} FillChar(Free, SizeOf(Free), True); {Cây T ban đầu là rỗng} end; procedure Prim; var k, i, u, v, min: Integer; begin Connected := True; for k := 1 to n do begin u := 0; min := maxC; {Chọn đỉnh u chưa bị kết nạp có d[u] nhỏ nhất} for i := 1 to n do if Free[i] and (d[i] < min) then begin min := d[i]; u := i; end; if u = 0 then {Nếu không chọn được u nào có d[u] < +∞ thì đồ thị không liên thông} begin Connected := False; Break; end; Free[u] := False; {Nếu chọn được thì đánh dấu u đã bị kết nạp, lặp lần 1 thì dĩ nhiên u = 1 bởi d[1] = 0} for v := 1 to n do if Free[v] and (d[v] > c[u, v]) then {Tính lại các nhãn khoảng cách d[v] (v chưa kết nạp)} begin d[v] := c[u, v]; {Tối ưu nhãn d[v] theo công thức} Trace[v] := u; {Lưu vết, đỉnh nối với v cho khoảng cách ngắn nhất là u} end; end; end; procedure PrintResult; var v, W: Integer; f: Text; begin Assign(f, OutputFile); Rewrite(f); if not Connected then {Nếu đồ thị không liên thông thì thất bại} WriteLn(f, 'Error: Graph is not connected') else begin WriteLn(f, 'Minimal spanning tree: '); W := 0; for v := 2 to n do {Cây khung nhỏ nhất gồm những cạnh (v, Trace[v])} begin WriteLn(f, '(', Trace[v], ', ', v, ') = ', c[Trace[v], v]); W := W + c[Trace[v], v]; end; WriteLn(f, 'Weight = ', W); end; Close(f); end; begin LoadGraph; Init; Prim; PrintResult; end.
Xét về độ phức tạp tính toán, thuật toán Prim có độ phức tạp là O(n2). Tương tự thuật toán Dijkstra, nếu kết hợp thuật toán Prim với cấu trúc Heap sẽ được một thuật toán với độ phức tạp O((m+n)logn). Tuy nhiên, nếu đồ thị có đỉnh lớn và số cạnh nhỏ, người ta thường sử dụng thuật toán Kruskal để tìm cây khung chứ không dùng thuật toán Prim với cấu trúc Heap.
Bài tập
Bài 1
So sánh hiệu quả của thuật toán Kruskal và thuật toán Prim về tốc độ.
Bài 2
Trên một nền phẳng với hệ toạ độ Decattes vuông góc đặt n máy tính, máy tính thứ i được đặt ở toạ độ (Xi, Yi). Cho phép nối thêm các dây cáp mạng nối giữa từng cặp máy tính. Chi phí nối một dây
cáp mạng tỉ lệ thuận với khoảng cách giữa hai máy cần nối. Hãy tìm cách nối thêm các dây cáp mạng để cho các máy tính trong toàn mạng là liên thông và chi phí nối mạng là nhỏ nhất.
Bài 3
Tương tự như bài 2, nhưng ban đầu đã có sẵn một số cặp máy nối rồi, cần cho biết cách nối thêm ít chi phí nhất.
Bài 4
Hệ thống điện trong thành phố được cho bởi n trạm biến thế và các đường dây điện nối giữa các cặp trạm biến thế. Mỗi đường dây điện e có độ an toàn là p(e). ở đây 0 < p(e) ≤ 1. Độ an toàn của cả
lưới điện là tích độ an toàn trên các đường dây. Ví dụ như có một đường dây nguy hiểm: p(e) = 1% thì cho dù các đường dây khác là tuyệt đối an toàn (độ an toàn = 100%) thì độ an toàn của mạng cũng rất thấp (1%). Hãy tìm cách bỏ đi một số dây điện để cho các trạm biến thế vẫn liên thông và độ an toàn của mạng là lớn nhất có thể.
Bài 5
Hãy thử cài đặt thuật toán Prim với cấu trúc dữ liệu Heap chứa các đỉnh ngoài cây, tương tự như đối với thuật toán Dijkstra.
Giải phóng thời gian, khai phóng năng lực