Cho A a8 8 là ủồ thị vụ hướng liờn thụng cú trọng số. Với một cõy khung của A, ta gọi trọng số của cây , ký hiệu , là tổng trọng số các cạnh trong . Bài toỏn ủặt ra là trong số cỏc cõy khung của A, 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 nhỏ nhất (minimum
152
spanning tree) của ủồ thị. 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ố, cả hai thuật toỏn này ủều là thuật toỏn tham lam.
2.1. Phương pháp chung
Xột ủồ thị vụ hướng liờn thụng cú trọng số A a8 8 . Cả hai thuật toỏn ủể tỡm cõy khung ngắn nhất ủều dựa trờn một cỏch làm chung: Nở dần cõy khung.
Cỏch làm này ủược mụ tả như sau: Thuật toỏn quản lý một tập cỏc cạnh ệ và cố gắng duy trì tính chất sau (tính bất biến vòng lặp):
× luôn nằm trong tập cạnh của một cây khung nhỏ nhất.
Tại mỗi bước lặp, thuật toỏn tỡm một cạnh @8 ủể thờm vào tập sao cho tớnh bất biến vũng lặp ủược duy trỡ, tức là ỉ @8 phải nằm trong tập cạnh của một cõy khung nhỏ nhất. Ta núi những cạnh @8 như vậy là an toàn (safe) ủối với tập .
procedure FindMST; //Tìm cây khung ngắn nhất
begin A := ;
while ôA chưa phải cõy khungằ do begin
ôTỡm cạnh an toàn (u, v) ủối với Aằ;
A := A ỉ {(u, v)}; //Bổ sung (u, v) vào A
end;
end;
Vấn ủề cũn lại là tỡm một thuật toỏn hiệu quả ủể tỡm cạnh an toàn ủối với tập . Chỳng ta cần một số khỏi niệm ủể giải thớch tớnh ủỳng ủắn của những thuật toỏn sau này.
Một lỏt cắt (cut) trờn ủồ thị là một cỏch phõn hoạch tập ủỉnh a thành hai tập rời nhau 8 Ù: ỉ Ù a Ú Ù . Ta núi một lỏt cắt a ỉ Ù tương thớch với tập nếu khụng cú cạnh nào của nối giữa một ủỉnh thuộc và một ủỉnh thuộc Ù. Trong những cạnh nối với Ù, ta gọi những cạnh có trọng số nhỏ nhất là những cạnh nhẹ (light edge) của lỏt cắt a ỉ Ù.
153
Hình 2.3. Lát cắt và cạnh nhẹ
ðịnh lý 2-1
Cho ủồ thị vụ hướng liờn thụng cú trọng số A a8 8 . Gọi là một tập con của tập cạnh của một cõy khung nhỏ nhất và a ỉ Ù là một lỏt cắt tương thớch với . Khi ủú mỗi cạnh nhẹ của lỏt cắt a ỉ Ù ủều là cạnh an toàn ủối với .
Chứng minh
Gọi @8 là một cạnh nhẹ của lỏt cắt a ỉ Ù, gọi là cõy khung nhỏ nhất chứa tất cả cỏc cạnh của . Nếu chứa cạnh @8 , ta cú ủiều phải chứng minh.
Nếu khụng chứa cạnh @8 , ta thờm cạnh @8 vào sẽ ủược một chu trỡnh, trờn chu trỡnh này cú ủỉnh thuộc và cũng cú ủỉnh thuộc Ù, vỡ vậy sẽ phải cú ớt nhất hai cạnh trên chu trình nối với Ù. Ngoài cạnh @8 nối với Ù, ta gọi
@Û8 Û là một cạnh khác nối với Ù trên chu trình, theo giả thiết @8 là cạnh nhẹ nờn @8 N @Û8 Û. Ngoài ra do lỏt cắt a ỉ Ù tương thớch với nờn
@Û8 Û ê .
Cắt bỏ cạnh @Û8 Û khỏi cây , cây sẽ bị tách rời làm hai thành phần liên thông, sau ủú thờm cạnh @8 vào cõy nối lại hai thành phần liờn thụng ủú ủể ủược cõy Û. Ta có
Û C @Û8 Û @8 N
Do là cây khung nhỏ nhất, Û cũng phải là cây khung nhỏ nhất. Ngoài ra cây Û chứa cạnh @8 và tất cả cỏc cạnh của . Ta cú ủiều phải chứng minh.
Hệ quả
Cho ủồ thị vụ hướng liờn thụng cú trọng số A a8 8 . Gọi là một tập con của tập cạnh của một cõy khung nhỏ nhất. Gọi F là tập cỏc ủỉnh của một thành phần liờn thụng trờn ủồ thị Aĩ a8 . Khi ủú nếu @8 5 là cạnh trọng số
Ù
3 5
1 1 1
2 2
Lát cắt
154
nhỏ nhất nối từ F tới một thành phần liên thông khác thì @8 là cạnh an toàn ủối với .
Chứng minh
Xột lỏt cắt a F ỉ a C F, lỏt cắt này tương thớch với và cạnh @8 là cạnh nhẹ của lỏt cắt này. Theo ðịnh lý 3-17, @8 an toàn ủối với .
Chỳng ta sẽ trỡnh bày hai thuật toỏn tỡm cõy khung nhỏ nhất trờn ủơn ủồ thị vụ hướng và cài ủặt chương trỡnh với khuụn dạng Input/Output như sau:
Input
Dũng 1 chứa số ủỉnh N 777 và số cạnh của ủồ thị
dũng tiếp theo, mỗi dũng chứa chỉ số hai ủỉnh ủầu mỳt và trọng số của một cạnh. Trọng số cạnh là số nguyờn cú giỏ trị tuyệt ủối khụng quỏ 1000.
Output
Cõy khung nhỏ nhất của ủồ thị
Sample Input Sample Output 6 8
1 2 3 1 3 3 2 4 3 2 5 3 3 5 4 4 5 2 4 6 2 5 6 1
Minimum Spanning Tree:
(5, 6) = 1 (4, 5) = 2 (1, 2) = 3 (2, 5) = 3 (1, 3) = 3 Weight = 12
2.2. Thuật toán Kruskal
Thuật toán Kruskal [27] dựa trên mô hình xây dựng cây khung bằng thuật toán hợp nhất, 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: ðể tỡm cõy khung ngắn nhất của ủồ thị A a8 8 , thuật toỏn khởi tạo cõy ban ủầu khụng cú cạnh nào. Duyệt danh sỏch cạnh của ủồ thị từ cạnh cú trọng số nhỏ ủến cạnh cú trọng số lớn, mỗi khi xột tới một cạnh và việc thờm cạnh ủú vào khụng tạo thành chu trỡnh ủơn trong thỡ kết nạp thờm cạnh ủú vào … Cứ làm như vậy cho tới khi:
1 2
3
4
5 6 3
3
3 3
4 2
2
1
155
Hoặc ủó kết nạp ủược a C cạnh vào trong thỡ ta ủược là cõy khung nhỏ nhất
Hoặc khi duyệt hết danh sỏch cạnh mà vẫn chưa kết nạp ủủ a C cạnh.
Trong trường hợp này ủồ thị A là khụng liờn thụng, việc tỡm kiếm cõy khung thất bại.
Như vậy cần làm rừ hai thao tỏc sau khi cài ủặt thuật toỏn Kruskal:
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.
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.
a) a)
a) a) DuyDuyDuyDuy;;;;t danh sách ct danh sách ct danh sách c9999nht danh sách c nhnh nh
Vỡ cỏc cạnh của ủồ thị phải ủược xột 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 một thuật toỏn sắp xếp danh sỏch cạnh rồi sau ủú duyệt lại danh sỏch ủó sắp xếp. Tuy nhiờn khi cài ủặt cụ thể, ta cú thể khộo lộo lồng thuật toỏn Kruskal vào QuickSort hoặc HeapSort ủể ủạt hiệu quả cao hơn.
Chẳng hạn với QuickSort, ý tưởng là sau khi phõn ủoạn danh sỏch cạnh bằng một cạnh chốt B, ta ủược ba phõn ủoạn: ðoạn ủầu gồm cỏc cạnh cú trọng số N B, tiếp theo là cạnh B, ủoạn sau gồm cỏc cạnh cú trọng số w B. Ta gọi ủệ quy ủể sắp xếp và xử lý cỏc cạnh thuộc ủoạn ủầu, tiếp theo xử lý cạnh B, cuối cựng lại gọi ủệ quy ủể sắp xếp và xử lý cỏc cạnh thuộc ủoạn sau. Dễ thấy rằng thứ tự xử lý cỏc cạnh như vậy ủỳng theo thứ tự tăng dần của trọng số. Ngoài ra khi thấy ủó cú ủủ C cạnh ủược kết nạp vào cây khung, ta có thể ngưng ngay QuickSort mà không cần xử lý tiếp nữa.
b) b)
b) b) KKKK****t nt nt nt n9999p cp cp c9999nh và hp c nh và hnh và hnh và h0000p câyp câyp câyp cây
Trong quá trình xây dựng cây khung, các cạnh trong ở các bước sẽ tạo thành một rừng (ủồ thị khụng cú chu trỡnh ủơn), mỗi thành phần liờn thụng của rừng này là một cây khung. Muốn thêm một cạnh @8 vào mà không tạo thành chu trỡnh ủơn thỡ @8 phải nối hai cõy khỏc nhau của rừng . ðiều này làm chỳng ta nghĩ ủến cấu trỳc dữ liệu biểu diễn cỏc tập rời nhau: Ban ủầu ta khởi tạo tập k(8 k+8 8 k., mỗi tập chứa ủỳng một ủỉnh của ủồ thị. Khi xột tới cạnh
156
@8 , nếu @ và thuộc hai tập khác nhau k¨8 k© thì ta hợp nhất k¨8 k© lại thành một tập.
Vậy cú hai thao tỏc cần phải cài ủặt hiệu quả trong thuật toỏn Kruskal: phộp kiểm tra hai ủỉnh cú thuộc hai tập khỏc nhau hay khụng và phộp hợp nhất hai tập. Một trong những cấu trỳc dữ liệu hiệu quả ủể cài ủặt những thao tỏc này là rừng cỏc tập rời nhau (disjoint-set forest). Cấu trỳc dữ liệu này ủược cài ủặt như sau:
Mỗi tập kE ủược biểu diễn bởi một cõy, trong ủú mỗi ủỉnh trong tập tương ứng với một nỳt trờn cõy. Cõy ủược biểu diễn bởi mảng con trỏ tới nỳt cha: 0 là nỳt cha của nỳt . Trong trường hợp là nỳt gốc của cõy, ta ủặt:
0 z Chạng của cây
Hạng (rank) của một cõy là một số nguyờn khụng nhỏ hơn ủộ cao của cõy. Ban ủầu mỗi tập kE chỉ gồm một ủỉnh, nờn họ cỏc tập k(8 k+8 8 k. ủược khởi tạo với cỏc nhón 0 z 7, L 5 a tương ứng với một rừng gồm cõy ủộ cao 0.
ðể xỏc ủịnh hai ủỉnh @8 cú thuộc 2 tập khỏc nhau hay khụng, ta chỉ cần xỏc ủịnh xem gốc của cõy chứa @ và gốc của cõy chứa cú khỏc nhau hay khụng.
Việc xỏc ủịnh gốc của cõy chứa @ ủược thực hiện bởi hàm ?k@: ði từ @ lờn nỳt cha, ủến khi gặp nỳt gốc (nỳt ! cú 0! N 7) thỡ dừng lại. ði kốm với hàm ?k@ là phộp nộn ủường (path compression): Dọc trờn ủường ủi từ @ tới nỳt gốc !, ủi qua ủỉnh nào ta cho luụn ủỉnh ủú làm con của !:
function FindSet(u: Integer): Integer;
//Xỏc ủịnh gốc cõy chứa ủỉnh u
begin
if lab[u] <= 0 then Result := u
//u là gốc của một tập S[.] nào ủú, trả về chớnh u
else //u không phải gốc
begin
Result := FindSet(lab[u]); //Gọi ủệ quy tỡm gốc
lab[u] := Result; //Nộn ủường, cho u làm con của nỳt gốc luụn
end;
end;
157
Việc hợp nhất hai tập tức là xây dựng cây mới chứa tất cả các phần tử trong hai cõy ban ủầu. Giả sử ! và " là gốc của hai cõy tương ứng với hai tập cần hợp nhất. Khi ủú:
Nếu cây gốc ! có hạng cao hơn cây gốc ", ta cho " làm con của !, hạng của cõy gốc ! khụng thay ủổi, tương tự cho trường hợp cõy gốc ! thấp hơn cõy gốc ".
Nếu hai cõy ban ủầu cú cựng hạng, ta cho cõy gốc ! làm con của gốc " khi ủú cõy gốc " cú thể sẽ bị tăng ủộ cao, do vậy ủể hợp lý húa ta tăng hạng của
" lờn 1, tương ủương với việc giảm 0" ủi 1.
procedure Union(r, s: Integer); //Hợp nhất hai tập r và s
begin
if lab[r] < lab[s] then //hạng của r lớn hơn
lab[s] := r //cho s làm con của r
else begin
if lab[r] = lab[s] then Dec(lab[s]);
//Nếu hai tập bằng hạng, tăng hạng của s
lab[r] := s; //Cho r làm con của s
end;
end;
Hình 2.4 mô tả hai cây biểu diễn hai tập rời nhau, sau khi xét tới một cạnh @8 nối giữa hai tập, hai cõy ủược hợp nhất lại bằng cỏch cho một cõy làm cõy con của gốc cây kia.
Hỡnh 2.4. Hai tập rời nhau ủược hợp nhất lại khi xột tới một cạnh nối một ủỉnh của tập này với một ủỉnh của tập kia
KRUSKAL.PAS Thuật toán Kruskal {$MODE OBJFPC}
program MinimumSpanningTree;
! "
@
!
"
@
158 const
maxN = 1000;
maxM = maxN * (maxN - 1) div 2;
type
TEdge = record //Cấu trúc cạnh
x, y: Integer; //Hai đỉnh đầu mút
w: Integer; //Trọng số
Selected: Boolean; //Đánh dấu chọn/không chọn vào cây khung
end;
var
lab: array[1..maxN] of Integer; //Nhãn của disjoint set forest
e: array[1..maxM] of TEdge; //Danh sách cạnh
n, m, k: Integer;
procedure Enter; //Nhập dữ liệu
var i: Integer;
begin
ReadLn(n, m);
for i := 1 to m do with e[i] do begin
ReadLn(x, y, w);
Selected := False; //Chưa chọn cạnh nào
end;
for i := 1 to n do lab[i] := 0;
//Khởi tạo n tập rời nhau hạng của mỗi tập bằng 0
k := 0; //Biến đếm số cạnh được kết nạp vào cây khung
end;
function FindSet(u: Integer): Integer; //Xác định tập chứa đỉnh u
begin
if lab[u] <= 0 then Result := u //u là gốc của một tập S[.] nào đó
else //u không phải gốc
begin
Result := FindSet(lab[u]); //Gọi đệ quy tìm gốc
lab[u] := Result; //Nén đường
end;
end;
procedure Union(r, s: Integer); //Hợp nhất hai tập r và s
begin
159
if lab[r] < lab[s] then //hạng của r lớn hơn
lab[s] := r //cho s làm con của r
else begin
if lab[r] = lab[s] then Dec(lab[s]);
//Nếu hai tập bằng hạng, tăng hạng của s
lab[r] := s; //Cho r làm con của s
end;
end;
procedure ProcessEdge(var e: TEdge); //Xử lý một cạnh e
var r, s: Integer;
begin
with e do begin
r := FindSet(x);
s := FindSet(y); //Xác định 2 tập tương ứng với 2 đầu mút
if r <> s then //Hai đầu mút thuộc hai tập khác nhau
begin
Selected := True; //Cạnh e sẽ ủược chọn vào cõy khung nhỏ nhất
Inc(k); //Tăng biến đếm số cạnh được kết nạp
Union(r, s); //Hợp nhất hai tập thành một
end;
end;
end;
procedure QuickSort(L, H: Integer); //Xử lý danh sách cạnh e[L...H]
var
i, j: Integer;
pivot: TEdge;
begin
//Nếu cây đã có đủ k cạnh hoặc danh sách cạnh rỗng thì thoát luôn
if (L > H) or (k = n - 1) then Exit;
//Chú ý L > H, không phải L ≥ H như trong QuickSort
i := L + Random(H - L + 1);
pivot := e[i];
e[i] := e[L];
i := L;
j := H;
repeat
160 while (e[j].w > pivot.w) and (i < j) do Dec(j);
if i < j then begin
e[i] := e[j];
Inc(i);
end
else Break;
while (e[i].w < pivot.w) and (i < j) do Inc(i);
if i < j then begin
e[j] := e[i];
Dec(j);
end
else Break;
until i = j;
QuickSort(L, i - 1);
//Cỏc cạnh e[L...i – 1] cú trọng số ≤ Pivot.w, gọi ủệ quy xử lý trước
e[i] := Pivot;
if k < n - 1 then ProcessEdge(e[i]); //Xử lý tiếp cạnh e[i] = Pivot
QuickSort(i + 1, H);
//Cỏc cạnh e[i + 1...H] cú trọng số ≥ Pivot.w, gọi ủệ quy xử lý sau
end;
procedure PrintResult;
var
i, Weight: Integer;
begin
if k < n - 1 then //Không kết nạp đủ n – 1 cạnh, đồ thị không liên thông
WriteLn('Graph is not connected!') else //In ra cây khung nhỏ nhất
begin
WriteLn('Minimum Spanning Tree:');
Weight := 0;
for i := 1 to m do with e[i] do
if Selected then //In ra cách cạnh được đánh dấu chọn
begin
WriteLn('(', x, ', ', y, ') = ', w);
Inc(Weight, w);
161
end;
WriteLn('Weight = ', Weight);
end;
end;
begin Enter;
QuickSort(1, m); //Lồng thuật toán Kruskal vào QuickSort
PrintResult;
end.
Tớnh ủỳng ủắn của thuật toỏn Kruskal ủược suy ra từ ðịnh lý 3-17: ðể ý rằng cỏc cạnh ủược kết nạp vào cõy khung sau mỗi bước sẽ tạo thành một rừng (ủồ thị khụng cú chu trỡnh ủơn). Mỗi khi cạnh @8 ủược xột ủến, nú sẽ chỉ ủược kết nạp vào cây khung nếu như @ và thuộc hai cây (hai thành phần liên thông) ă8 â khỏc nhau. Ký hiệu là tập cạnh của ă, khi ủú lỏt cắt a ăỉ a C ă là tương thích với tập , @8 là cạnh nhẹ của lát cắt nên @8 cũng phải là một cạnh trên một cây khung nhỏ nhất.
c) c) c)
c) ThThThThUUUUi gian thi gian thi gian thLi gian thLLLc hic hic hic hi;;;;n gin gin gin gii thui thui thui thu tttt
Với hai số tự nhiờn 8 , hàm Ackermann 8 ủược ủịnh nghĩa như sau:
8 8 nếu 7
C 88 nếu 1 7 và 7
g C 8 8 C h8 nếu 1 7 và 1 7
Dưới ủõy là bảng một số giỏ trị hàm Ackermann:
162
: :
0 1 2 3 4
0 1 2 3 4 5
1 2 3 4 5 6
2 3 5 7 9 11
3 5 13 29 61 125
4 13 65533 ; C V ;+íịịíC V ;+,íịịí C V Hàm 8 là một hàm tăng rất nhanh theo ủối số . Cú thể chứng minh ủược
78 8 ;
;8 ; V V8 ;.K C V X8 ;ò+,
.K lũy thừa
C V
Chẳng hạn X8; là một số có 19729 chữ số, X8X là một số mà số chữ số của nú lớn hơn cả số nguyờn tử trong phần vũ trụ mà con người biết ủến.
Khi 1 7, xột hàm 8 , gọi là nghịch ủảo của hàm Ackerman, ủịnh nghĩa như sau:
8 ào à w M f8 ỏ
âi w %' ã
Người ta ủó chứng minh ủược rằng với cấu trỳc dữ liệu rừng cỏc tập rời nhau, việc thực hiện thao tỏc ?k và mất thời gian $g8 h. Ở ủõy
8 là một hằng số rất nhỏ (trên tất cả các dữ liệu thực thế, không bao giờ
8 vượt quỏ 4). ðiều ủú chỉ ra rằng ngoại trừ việc sắp xếp danh sỏch cạnh, thuật toán Kruskal ở trên có thời gian thực hiện $g8 ah.
Tuy nhiên nếu phải thực hiện sắp xếp danh sách cạnh, chúng ta cần cộng thêm thời gian thực hiện giải thuật sắp xếp $ %' nữa.
163
2.3. Thuật toán Prim a)
a) a)
a) TF tFTF tFTF tFTF tFBBBBng cng cng cng c<<<<a thua thua thua thu t toánt toánt toánt toán
Trong trường hợp ủồ thị dày (cú nhiều cạnh), cú một thuật toỏn hiệu quả hơn ủể tìm cây khung ngắn nhất là thuật toán Prim [32]. Với một cây khung và một ủỉnh ê , ta gọi khoảng cỏch từ tới , ký hiệu , là trọng số nhỏ nhất của một cạnh nối với một ủỉnh nằm trong :
àoă5ọ6@8 9
Tư tưởng của thuật toỏn cú thể trỡnh bày như sau: Ban ủầu khởi tạo một cõy chỉ gồm 1 ủỉnh bất kỳ của ủồ thị, sau ủú ta cứ tỡm ủỉnh gần nhất (cú khoảng cách tới ngắn nhất) kết nạp vào và kết nạp luôn 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 ủủ ủỉnh vào , ta cú một cõy khung ngắn nhất.
Hoặc chưa kết nạp ủủ ủỉnh nhưng khụng cũn cạnh nào nối một ủỉnh trong với một ủỉnh ngoài . Ta kết luận ủồ thị khụng liờn thụng và khụng thể tồn tại cây khung.
b) b) b)
b) KKKK```` thuthuthuthu t cài "t cài "t cài "t cài "::::tttt
Khi cài ủặt thuật toỏn Prim, ta sử dụng cỏc nhón khoảng cỏch ủể lưu khoảng cỏch từ tới tại mỗi bước. Mỗi khi cõy bổ sung thờm một ủỉnh @, ta tính lại các nhãn khoảng cách theo công thức sau:
mới z ào 6cũ8 @8 9
Tớnh ủỳng ủắn của cụng thức cú thể hỡnh dung như sau: là khoảng cỏch từ tới cõy , theo ủịnh nghĩa là trọng số nhỏ nhất trong số cỏc cạnh nối với một ủỉnh nằm trong . Khi cõy “nở” ra thờm ủỉnh @ nữa mà ủỉnh @ này lại gần hơn tất cả cỏc ủỉnh khỏc trong , ta ghi nhận khoảng cỏch mới là trọng số cạnh @8 , nếu không ta vẫn giữ khoảng cách cũ.
164 Hình 2.5. Cơ chế cập nhật nhãn khoảng cách
Tại mỗi bước, ủỉnh ngoài cõy cú nhón khoảng cỏch nhỏ nhất sẽ ủược kết nạp vào cõy, sau ủú cỏc nhón khoảng cỏch ủược cập nhật và lặp lại. Mụ hỡnh cài ủặt của thuật toán có thể viết như sau:
u := ôMột ủỉnh bất kỳằ;
T := {u};
for Lv ∉ T do d[v] := +∞;
//Cỏc ủỉnh ngoài T ủược khởi tạo nhón khoảng cỏch +∞
for i := 1 to n - 1 do //Làm n – 1 lần
begin
for (Lv ∉ T:(u, v)5 E) do d[v] := min{d[v], w(u, v)};
//Cập nhật nhón khoảng cỏch của cỏc ủỉnh kề u nằm ngoài T
u := arg min{d[v]:v ∉ T};
//Chọn u là ủỉnh cú nhón khoảng cỏch nhỏ nhất trong số cỏc ủỉnh nằm ngoài T
if d[u] = +∞ then //ðồ thị không liên thông
begin
Output ← "Không tồn tại cây khung";
Break;
end;
T := T ∪ {u}; //Bổ sung u vào T
end;
Output ← T;
Cài ủặt dưới ủõy sử dụng ma trận trọng số ủể biểu diễn ủồ thị. Kỹ thuật ủỏnh dấu ủược sử dụng ủể biết một ủỉnh ủang nằm ngoài (@" !@) hay nằm trong cõy (@" ?"). Ngoài ra ủể tiện lợi hơn trong việc chỉ ra cõy khung nhỏ nhất, với mỗi ủỉnh nằm ngoài ta lưu lại !l là ủỉnh @ nằm trong mà cạnh @8 tạo ra khoảng cách gần nhất từ tới : @8
@ cũ
@8