Tìm cây bao trùm nhỏ nhất dùng thuật toán kruskal

Chào mừng các bạn ghé blog của mình nè!

Ở bài viết này,Phong sẽ nói về thuật toán tìm cây bao trùm nhỏ nhất dùng thuật toán kruskal.Đây là bài tập của chương mới nên đầu tiên chúng ta cần tìm hiểu lý thuyết nè,mau mau lên search wiki thôi,hii.

Thuật toán Kruskal là một thuật toán trong lý thuyết đồ thị để tìm cây bao trùm nhỏ nhất của một đồ thị liên thông có trọng số. Nói cách khác, nó tìm một tập hợp các cạnh tạo thành một cây chứa tất cả các đỉnh của đồ thị và có tổng trọng số các cạnh là nhỏ nhất.

Tư tưởng thuật toán:

Thuật toán Kruskal dựa trên mô hình xây dựng cây khung nhỏ nhất bằng thuật toán hợp nhất.

  • Thuật toán không xét các cạnh với thứ tự tuỳ ý.
  • Thuật toán xét các cạnh theo thứ tự đã sắp xếp theo trọng số.
Để xây dựng tập n-1 cạnh của cây khung nhỏ nhất - tạm gọi là tập K, Kruskal đề nghị cách kết nạp lần lượt các cạnh vào tập đó theo nguyên tắc như sau:
  • Ưu tiên các cạnh có trọng số nhỏ hơn.
  • Kết nạp cạnh khi nó không tạo chu trình với tập cạnh đã kết nạp trước đó.
Đó là một nguyên tắc chính xác và đúng đắn, đảm bảo tập K nếu thu đủ n - 1 cạnh sẽ là cây khung nhỏ nhất.

Mô tả thuật toán:

Giả sử ta cần tìm cây bao trùm nhỏ nhất của đồ thị G. Thuật toán bao gồm các bước sau.

  • Khởi tạo rừng F (tập hợp các cây ), trong đó mỗi đỉnh của G tạo thành một cây riêng biệt
  • Khởi tạo tập S chứa tất cả các cạnh của G
  • Chừng nào S còn khác rỗng và F gồm hơn một cây
    • Xóa cạnh nhỏ nhất trong S
    • Nếu cạnh đó nối hai cây khác nhau trong F, thì thêm nó vào F và hợp hai cây kề với nó làm một
    • 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).
-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.

Trên đó là phần lý thuyết mình đã search tham khảo trên wiki,đọc nó cũng khá là dể hiểu phải hông nè,hii,giờ mình đi thẳng vào code luôn nhé!

Dựa vào phần mã giả mình đã viết code như sau,mình có chú thích cho các bạn rồi,các bạn xem xem có hiểu không nhé,nếu có thắc đừng quên comment bạn nhé,nếu mình chậm trả lời thì liên hệ facebook mình hổ trợ trực tiếp luôn nè.

Chúc các bạn hoàn thành tốt bài tập này nhé!

Lưu ý là thuật toán trên mình tự code nên chắc chắn không thể không có sai sót nên mong các bạn thông cảm và chỉ dùng để tham khảo thôi nhé.

Giấy phép Creative Commons Giấy phép Creative Commons Attribution-ShareAlike 4.0 Quốc tế .

Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :