Thuật toán Prim - Kruscal

Thuật toán Prim - Kruscal

Đào Đức Minh

Bài toán: Cho một đồ thị vô hướng. Hãy tìm cây bao trùm ngắn nhất (Tức là tổng các

trọng số các cạnh của cây là nhỏ nhất).

Giới hạn:

INPUT:

Dòng đầu: Gồm 2 số n,d: (n,d thuộc [0;100]), n là số đỉnh, d: Số cạnh.

D dòng tiếp theo: Mỗi dòng gồm các số i,j,s.

+ Cho biết trọng số cạnh i,j là s (i,j là số hiệu đỉnh).

OUTPUT:

- Dòng đầu: Gồm 1 số m duy nhất cho biết số cạnh của cây (luôn bằng (n-1))

- m (hay (n-1)) dòng tiếp theo: Mỗi dòng gồm các số a,b,s: Cho biết đỉnh a nối với đỉnh b

có trọng số cạnh ab là s.

(n-1) dòng tiếp theo này cho biết các cạnh của cây.

- Dòng cuối: T cho biết tổng trọng số của cây bao trùm ngắn nhất.

- Nếu không liên thông thì xuất ″đồ thị không liên thông″

*) Giải thuật:

Có lẽ thuật toán Prim và Kruscal đã quen thuộc để giải loại bài toán này. (Đã từng được

giới thiệu trên báo THNT) , Nhưng mỗi thuật toán tôi lại cảm thấy không được tối ưu cho

lắm vì các bước cần giải quyết khá phức tạp.

*) Thuật toán Prim: Tư tưởng chủ đạo là chọn cạnh, mỗi lần chọn cạnh lại phải kiểm tra

có tạo chu trình hay không, nếu cạnh ấy có tạo chu trình thì loại bỏ cạnh ấy.

Thuật toán Kruscal: Tư tưởng chủ đạo là chọn đỉnh, phải chọn đỉnh không ở trong tập

đỉnh đã chọn, có cung nối đỉnh đó với đỉnh đã chọn và có trọng số là nhỏ nhất.

Các bước trong thuật toán trên khá phức tạp, tốn kém thời gian, khi dữ liệu quá lớn thì có

lẽ đó là chưa là thuật toán tốt. Em đã nghĩ ra thuật toán kết hợp tinh hoa của hai thuật toán

trên trở thành ″Thuật toán Prim − Kruscal″

Các bước của thuật toán:

Bước 1. Sắp xếp các cạnh từ nhỏ đến lớn theo trọng số (Dùng kiểu record), Chọn cạnh đầu

tiên.

Bước 2. Tìm cạnh tiếp theo: cạnh được chọn phải thoả: 1 đỉnh ở trong tập hợp đỉnh đã

chọn và một đỉnh ngoài tập hợp đỉnh đã chọn và cạnh đó chưa được chọn.

Bước 3: Trở lại đầu dãy cạnh đã sắp xếp.

Trở lại bước 2 và chỉ thoát khi chọn đủ (n-1) cạnh hoặc chưa chọn đủ (n-1) cạnh nhưng

không thể chọn thêm cạnh nữa (trường hợp này đồ thị không liên thông).

*) Ví dụ minh hoạ: Gọi T là tập các đỉnh đã chọn, C là tâp các cạnh đã chọn.