CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
4.Thuật toán Kruskal:
Xây dựng tập cạnh T của cây khung nhỏ nhất H=(V,T). Sắp xêp các cạnh của đồ thị G theo thứ tự không giảm của độ dài.
Bắt đầu T = Ø
Ở mỗi bước duyệt trong danh sách cạnh đã sắp xếp, từ cạnh có độ dài nhỏ đến cạnh có độ dài lớn hơn để tìm ra cạnh mà việc bổ sung vào tập T không tạo thành chu trình trong tập này.
Thuật toán sẽ kết thúc khi ta thu được tập T gồm có n-1 cạnh.
Code:
PROCEDURE KRUSKAL;
BEGIN
Sắp xếp các cạnh theo chiều không giảm;
T = Ø;
WHILE ( |T| < n-1 ) AND ( E <> Ø) DO
BEGIN
Chọn e in E là cạnh có độ dài nhỏ nhất.
E:= E - {e};
IF (T + {e}) không chứa chu trình THEN
T:=T+{e}
END;
END;