So sánh giữa thuật toán prim và kruskal năm 2024

Bài này đề cập lý thuyết về cây khung và cây khung nhỏ nhất, để xem thuật toán tìm cây khung nhỏ/lớn nhất, xem thuật toán Kruskal và thuật toán Prim.

Cho đồ thị vô hướng, cây khung (spanning tree) của đồ thị là một cây con chứa tất cả các đỉnh của đồ thị. Nói cách khác, cây khung là một tập hợp các cạnh của đồ thị, không chứa chu trình và kết nối tất cả các đỉnh của đồ thị.

Trong đồ thị có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh nhỏ nhất. Định nghĩa tương tự với cây khung lớn nhất.

Các tính chất cây khung lớn nhất

Đường đi rộng nhất

Gọi độ rộng của một đường đi trên đồ thị là trọng số nhỏ nhất trong các trọng số trên đường đi đó. Khi đó ta có: đường đi giữa 2 đỉnh u và v trên cây khung lớn nhất chính là đường đi rộng nhất giữa 2 đỉnh đó.

Mở rộng hơn, ta có đường đi trên cây khung nhỏ nhất chính là đường đi có cạnh lớn nhất là nhỏ nhất, còn đường đi trên cây khung lớn nhất có cạnh nhỏ nhất là lớn nhất.

Cần chú ý tính chất này vì nó được sử dụng trong nhiều bài tập.

Tính duy nhất

Nếu tất cả các cạnh đều có trọng số khác nhau thì chỉ có duy một cây khung nhỏ nhất. Ngược lại, nếu một vài cạnh có trọng số giống nhau thì có thể có nhiều hơn một cây khung nhỏ nhất.

Tính chất chu trình

Trong một chu trình \(C\) bất kì, nếu cạnh \(e\) có trọng số lớn hơn tất cả các cạnh còn lại thì \(e\) không thể nằm trong cây khung nhỏ nhất.

Tính chất cắt

Xét một lát cắt \(C\) bất kì, gọi \(E\) là tập hợp các cạnh trong lát cắt đó (các cạnh bị loại bỏ để đồ thị bị chia làm 2 thành phần liên thông). Nếu \(e\) là cạnh trong \(E\) và \(e\) có trọng số nhỏ hơn tất cả các cạnh khác của \(E\) thì \(e\) nằm trong cây khung nhỏ nhất của đồ thị.

Tính chất cạnh nhỏ nhất

Nếu \(e\) là cạnh có trọng số nhỏ nhất của đồ thị, và không có cạnh nào có trọng số bằng \(e\) thì \(e\) nằm trong mọi cây khung nhỏ nhất của đồ thị.

Cây khung (Spanning Tree): là một cây con của đồ thị, tập hợp các cạnh của đồ thị thỏa mãn tập cạnh này không chứa chu trình và liên thông.

• Trong đồ thị có trọng số, cây khung nhỏ nhất (minimum spanning tree) là cây khung có tổng trọng số các cạnh trong cây nhỏ nhất.

THUẬT TOÁN

1. Thuật toán Prim:
2. Là thuật toán tìm cây khung nhỏ nhất dựa vào giải thuật tham lam.
   • Bắt đầu bằng việc chọn một đỉnh bất kỳ, đặt nó vào cây khung T.
   • Trong khi cây khung T có ít hơn n đỉnh: Ghép vào T cạnh có trọng số nhỏ nhất liên thuộc với một đỉnh của T và không tạo ra chu trình trong T.
   • Thuật toán dừng lại khi T có đủ n đỉnh hoặc (n-1) cạnh.
3. Để hiểu sâu hơn, chúng ta vào giải ví dụ sau đây:

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

Xóa các vòng cà các cạnh song song từ đồ thị đã cho. Khi xóa các cạnh song song, giữ lại cạnh có trọng số nhỏ nhất và xóa cạnh còn lại.

Sau khi thêm nút D vào cây khung, chúng ta còn 2 cạnh có cùng trọng số 2 là DT và DB. Ta tiếp tục thêm 2 cạnh này vào cây khung Từ đó, ta đã có một cây khung nhỏ nhất hoàn chỉnh:

1. Thuật toán Kruskal
   • Tương tự Prim, thuật toán Kruskal là thuật toán tìm cây khung nhỏ nhất dựa vào giải thuật tham lam.
     • Bắt đầu từ chọn một cạnh có trọng số nhỏ nhất, đặt nó vào cây khung T.
     • Trong khi cây khung T có ít hơn (n-1) cạnh: Ghép vào T cạnh có trọng số nhỏ nhất và không tạo ra chu trình trong T.
   • Để hiểu giải thuật này, chúng ta cùng giải ví dụ sau đây:

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

Xóa các vòng và các cạnh song song. Khi xóa các cạnh song song, giữ 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 Tạo một tập các cạnh và trọng số. Sắp xếp chúng theo thứ tự tăng dần về trọng số.

Bước 3: Thêm một cạnh có trọng số nhỏ nhất Bắt đầu thêm các cạnh của đồ thị từ cạnh có trọng số thấp nhất. Kiểm tra các thuộc tính của cây khung, nếu phá vỡ thuộc tính thì bỏ cạnh đó.

Bài toán cây khung (cây bao trùm) nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị có nhiều ứng dụng khác nhau trong đời sống. Để minh hoạ thuật toán, chúng ta tham khảo một vài mô hình thực tế tiêu biểu của bài toán:

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 vô hướ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.Thuật toán Kruskal là một ví dụ của thuật toán tham lam.

Thuật toán này xuất bản lần đầu tiên năm 1956, bởi Joseph Kruskal.

Một vài thuật toán khác cho bài toán này bao gồm thuật toán Prim, thuật toán xóa ngược, và thuật toán Borůvka.

Bài toán dẫn nhập[sửa | sửa mã nguồn]

Cho một đồ thị có trọng số với n đỉnh. Yêu cầu tìm ra cây khung nhỏ nhất.

Tư tưởng thuật toán[sửa | sửa mã nguồ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[sửa | sửa mã nguồ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ả[sửa | sửa mã nguồn]

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 3.

Kỹ thuật đánh nhãn đỉnh[sửa | sửa mã nguồn]

Kỹ thuật đánh nhãn đỉnh Trong thuật toán Kruskal, để kiểm tra xem T + {e} có chứa chu trình hay không ta có thể dùng kỹ thuật gắn nhãn đỉnh, kỹ thuật này khá đơn giản và hiệu quả.

• Ngay sau bước 1 của thuật toán, ta gắn đỉnh i của đồ thị một nhãn là i
• Trong bước 2:
  • Nếu hai đầu cạnh e có cùng nhãn (tức là nhãn của e.v1 và nhãn của e.v2 bằng nhau) thì T+{e} tạo chu trình, ta không đưa e vào T.
  • Ngược lại [nếu Label(e.v1)!= Label(e.v2) ] thì ta đưa e vào T và thực hiện công việc ghép nhãn bằng cách:
    • lab1 = Min(Label(e.v1), Label (e.v2))
    • lab2 = Max(Label(e.v1), Label (e.v2))
    • Sửa nhãn của tất cả các đỉnh nào có nhãn là lab2 thành nhãn lab1

Ghi chú[sửa | sửa mã nguồn]

• Trong quá trình xây dựng T thì các cạnh có thể không liên thông nhau lúc đó T chỉ là rừng chứ chưa trở thành cây.
• Khi thuật toán dừng:
  • Nếu T chưa đủ n - 1 cạnh thì đồ thị G không liên thông(không có cây khung)
  • Ngược lại thì T là cây khung cần tìm.

Thời gian thực hiện[sửa | sửa mã nguồn]

• Nếu E là số cạnh và V là số đỉnh của đồ thị thì thuật toán Kruskal chạy trong thời gian O(E log V).
• Có thể đạt được thời gian này bằng phương pháp sau: sắp xếp tất cả các cạnh theo trọng số trong thời gian O(E log E). Điều này cho phép thực hiện bước "xóa cạnh nhỏ nhất trong S" trong thời gian hằng số. Sau đó sử dụng cấu trúc dữ liệu cho các tập hợp không giao nhau để lưu trữ thông tin đỉnh nào nằm ở cây nào trong F. Ta cần thực hiện O(E) thao tác, hai thao tác 'tìm' và không quá một thao tác 'hợp' cho mỗi cạnh. Ngay cả những thuật toán đơn giản cho bài toán này, chẳng hạn hợp bằng trọng số cũng có thể thực hiện O(E) thao tác trong thời gian O(E log V). Vì vậy tổng thời gian là O(E log E) = O(E log V).

Chứng minh tính đúng đắn[sửa | sửa mã nguồn]

Chứng minh gồm hai phần: chứng minh kết quả thuật toán là một cây bao trùm và cây bao trùm đó là nhỏ nhất.

Cây bao trùm[sửa | sửa mã nguồn]

F luôn là một rừng do việc nối hai cây bằng một cạnh luôn tạo ra một cây mới. Giả thiết phản chứng F gồm ít nhất hai cây A và B. Khi cạnh đầu tiên nối các đỉnh trong A của F với phần còn lại của đồ thị được xem xét (cạnh này tồn tại do G liên thông) thì rõ ràng thuật toán sẽ chọn nó. Vì vậy A không thể là một cây trong F khi thuật toán kết thúc. Do đó, F liên thông và là một cây bao trùm.

Nhỏ nhất[sửa | sửa mã nguồn]

Ta chứng minh mệnh đề P sau đây bằng quy nạp: Nếu F là tập hợp các cạnh đã chọn tại bất kì thời điểm nào trong quá trình thực thi thuật toán thì tồn tại cây bao trùm nhỏ nhất chứa F.

• Rõ ràng P đúng khi thuật toán bắt đầu vì F là rỗng.
• Giả sử P là đúng cho một tập hợp F và giả sử T là một cây bao trùm nhỏ nhất chứa F. Nếu cạnh được thêm vào tiếp theo là e cũng nằm trong T, thì P đúng cho F + e. Nếu không, thì T + e chứa chu trình C và tồn tại cạnh f nằm trên C nhưng không trong F. (Nếu không có cạnh f, thì không thể thêm e vào F, do sẽ tạo ra chu trình C trong F.) Do đó T − f + e là một cây, và nó có cùng trọng số với T, do T có trọng số nhỏ nhất và f không thể nhỏ hơn e, vì nếu không thuật toán đã xem xét f trước e và chọn f. Vì vậy T − f + e là một cây bao trùm nhỏ nhất chứa F + e và P là đúng.
• Như vậy, P đúng khi thuật toán kết thúc và F là một cây bao trùm. Điều này chỉ có thể xảy ra nếu F là một cây bao trùm nhỏ nhất.

Ví dụ[sửa | sửa mã nguồn]

• Cho đồ thị G như hình vẽ:. Yêu cầu tìm ra cây khung nhỏ nhất của đồ thị G.
• G gồm có 7 đỉnh
• Đồ thị G có n phần tử. Thuật toán Kruskal sẽ dừng khi có n-1 trong tập hợp T
  • n = 7
  • Vậy số cạnh trong tập hợp T: n - 1 = 7 - 1 = 6(*)
    
    Đồ thị G

Bước 1: Liệt kê tất cả cạnh với trọng số của cạnh đó: Dựa vào đồ thị ta liệt kê ra các cạnh gồm đỉnh đầu, đỉnh cuối và trọng số: