Nội dung được xóa Nội dung được thêm vào
|
|
|
** Nếu không thì loại bỏ cạnh đó.
Khi thuật toán kết thúc, rừng chỉ gồm đúng một cây và đó là một cây bao trùm nhỏ nhất của đồ thị ''G''.
==Mã giả==
Cho đồ thị '''G=(X, E)'''.
<code>
Bước 1: Sắp xếp các cạnh của đồ thị theo thứ tự trọng số tăng dần.
Bước 2: Khởi tạo T := Ø
Bước 3: Lần lượt lấy từng cạnh thuộc danh sách đã sắp xếp. Nếu T+{e} không chứa chu trình thì gán T:=T+{e}.
Bước 4: Nếu T đủ n - 1 phần tử thì dừng, ngược lại làm tiếp bước 2.
</code>
===Ghi chú===
*Trong quá trình xây dựng T thì các cạnh có thể không [[tập hợp liên thông|liên thông]] nhau lúc đó T chỉ là [[rừng]] chứ chưa trở thành [[cây]].
*Khi [[thuật toán]] dừng:
**Nếu T chưa đủ n - 1 cạnh thì [[đồ thị]] G không liên thông(không có cây khung)
**Ngược lại thì T là [[cây bao trùm|cây khung]] cần tìm.
== Thời gian thực hiện ==
|
