Giải thuật Kruskal: tìm cây khung nhỏ nhất

---

---

Giải thuật Kruskal là gì ?

Giải thuật của Kruskal là tìm cây khung nhỏ nhất dựa trên giải thuật tham lam. Giải thuật Kruskal xem đồ thị như là một rừng cây và mỗi nút là một cây riêng lẻ trong rừng. Giải thuật Kruskal không phụ thuộc vào điểm bắt đầu. Một cây kết nối với cây khác nếu và chỉ nếu cây này có trọng số (weight - trong chương trước) nhỏ nhất trong số tất cả các cây đã tìm được và không vi phạm các đặc điểm của Cây khung nhỏ nhất (MST) – trong chương trước.

Để hiểu giải thuật Kruskal, mời bạn theo dõi ví dụ sau:

Bước 1: Xóa tất cả các vòng và các cạnh song song

Xóa tất cả các vòng và các cạnh song song từ độ thị ban đầu.

Trong trường hợp các cạnh song song, giữ các cạnh có trọng số nhỏ nhất và xóa cạnh còn lại.

Bước 2: Sắp xếp tất cả các cạnh theo trọng số tăng dần

Bước tiếp theo là tạo một tập các cạnh và trọng số và sắp xếp chúng theo thứ tự tăng dần về trọng số. (Giá trị trọng số là số hiển thị bên cạnh các cạnh trong hình minh họa trên.)

Bước 3: Thêm một cạnh có trọng số thấp nhất

Bây giờ chúng ta bắt đầu thêm các cạnh vào đồ thị bắt đầu từ cạnh có trọng số thấp nhất. Tại bất cứ thời điểm nào, chúng ta cũng cần kiểm tra các thuộc tính của cây khung có còn được duy trì hay không. Trong trường hợp khi thêm một cạnh mà làm phá vỡ thuộc tính của cây khung, thì chúng ta cần cân nhắc việc không thêm cạnh đó vào đồ thị.

Trọng số nhỏ nhất trong hình là 2 và đó là các cạnh là BD và DT, do đó chúng ta thêm hai cạnh này vào. Việc thêm hai cạnh này không vi phạm các đặc điểm của cây khung do đó chúng ta có thể tiếp tục lựa chọn cạnh tiếp theo.

Trọng số tiếp theo là 3 và đó là các cạnh AC và CD. Do đó chúng ta thêm hai cạnh này.

Trọng số tiếp theo trong hình là 4 và chúng ta thấy rằng khi thêm nó vào đồ thị sẽ tạo nên một chu trình trong đồ thị. Như hình minh họa:

Do đó chúng ta bỏ qua trọng số này. Tiến trình của chúng ta sẽ bỏ qua/tránh việc thêm các cạnh mà khi thêm cạnh đó vào sẽ tạo nên một chu trình trong đồ thị.

Tiếp theo với hai trọng số 5 và 6, chúng ta cũng thấy rằng chúng cũng tạo nên một chu trình. Do đó chúng ta bỏ qua hai trọng số này và chuyển tới trọng số tiếp theo.

Bây giờ đồ thị của chúng ta chỉ còn một nút để thêm vào. Giữa hai cạnh có trọng số lần lượt là 7 và 8, chúng ta thêm cạnh có trọng số nhỏ hơn.

Bằng việc thêm cạnh SA, chúng ta đã có một cây khung nhỏ nhất theo giải thuật của Kruskal.

---

---

---