Thuật toán Kruskal – Tìm cây bao trùm nhỏ nhất | Chuong Le Hoang

1. Mô tả:

- Giống như Prim, thuật toán Kruskal cũng tìm cây khung nhỏ nhất nhưng không phụ thuộc vào điểm bắt đầu.

- Hình 1, đồ thị như sau:

Hình 1

- Bước 1: lập bảng, liệt kê tăng dần theo trọng số của các cạnh.

- Bước 2: dựa vào thứ tự bảng trên để đánh giá cạnh đó có thuộc cây khung tối tiểu hay không. Một cạnh thõa điều kiện khi nó không góp phần tạo thành một chu trình với tất cả các cạnh đã tìm được.

1-4-1: Ta nhận thấy cạnh 1-4 không tạo ra một chu trình nào. Vì vậy, thêm 1-4 vào tập hợp

Hình 2

6-7-1: Ta nhận thấy cạnh 6-7 không tạo ra một chu trình nào. Vì vậy, thêm 6-7 vào tập hợp

Hình 3

4-6-2: Ta nhận thấy cạnh 4-6 không tạo ra một chu trình nào. Vì vậy, thêm 4-6 vào tập hợp

Hình 4

1-2-3: Ta nhận thấy cạnh 1-2 không tạo ra một chu trình nào. Vì vậy, thêm 1-2 vào tập hợp

Hình 5

1-6-3: Ta nhận thấy cạnh 1-6 tạo ra một chu trình. Không thêm vào tập hợp.

Hình 6

2-3-4: Ta nhận thấy cạnh 2-3 tạo ra một chu trình. Không thêm vào tập hợp.

Hình 7

3-7-5: Ta nhận thấy cạnh 3-7 tạo ra một chu trình. Không thêm vào tập hợp.

Hình 8

5-6-5: Ta nhận thấy cạnh 5-6 không tạo ra một chu trình nào. Vì vậy, thêm 5-6 vào tập hợp

Hình 9

CÂY BAO TRÙM THU ĐƯỢC, Hình 10:

Hình 10

Nguồn từ: http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Kruskal

2. Cài đặt:

- Bước 1, khai báo các biến, ta sẽ không sử dụng ma trận kề để lưu đồ thị, mà sẽ sử dụng danh sách các cạnh đã khai báo để lưu từng cạnh, vì vậy khi nhập dữ liệu vào, ta cần gán dữ liệu vào danh sách các cạnh:

- Bước 2, cài đặt thuật toán Kruskal:

- Hàm thực hiện sắp xếp các cạnh tăng dần theo trọng số:

- Hàm tìm nút cha của một đỉnh:

- Hàm thực hiện việc kết nối 2 nút lại với nhau:

Như vậy là mình vừa hướng dẫn các bạn thuật toán Kruskal - tìm cây khung nhỏ nhất, chúc các bạn cài đặt thành công ^_^