Trong bài đăng này, chúng ta sẽ hiểu sự khác biệt giữa thuật toán của Prim và Kruskal.
Thuật toán của Kruskal cho Cây kéo dài Mininum (MST)
- Khi một đồ thị được kết nối và vô hướng được cung cấp, cây bao trùm của một đồ thị như vậy là đồ thị con là cây kết nối tất cả các đỉnh.
- Một biểu đồ có thể có nhiều cây khung.
- Cây khung tối thiểu (MST) (còn được gọi là cây khung có trọng số tối thiểu) cho đồ thị có trọng số, được kết nối và vô hướng là cây khung có trọng lượng nhỏ hơn hoặc bằng trọng lượng của mọi cây khung khác.
- Trọng số của cây khung được xác định bằng cách cộng các trọng số liên quan đến mọi cạnh của cây khung.
- Cây kéo dài tối thiểu có thể được xây dựng từ đỉnh có trọng số tối thiểu trong biểu đồ.
- Một nút chỉ được duyệt một lần.
- Nó chạy nhanh trong các biểu đồ thưa thớt.
- Độ phức tạp về thời gian là O (E log V), trong đó V là số đỉnh.
- Nó cũng có thể hoạt động với các thành phần bị ngắt kết nối.
Các bước tìm MST bằng thuật toán Kruskal:
- Sắp xếp các cạnh theo thứ tự tăng dần của trọng số liên quan của chúng.
- Chọn cạnh nhỏ nhất.
- Kiểm tra xem nó có tạo thành một chu trình với cây bao trùm đã được hình thành cho đến thời điểm đó hay không.
- Nếu chu kỳ chưa được hình thành, thì cạnh này phải được bao gồm.
- Nếu không, nó có thể bị loại bỏ.
- Các bước 2,3,4 được lặp lại cho đến khi cây khung chứa các cạnh V-1.
Thuật toán của Prim Cây kéo dài mininum (MST)
- Điều này tương tự với thuật toán của Kruskal, tức là nó là một thuật toán tham lam.
- Nó bắt đầu với một cây khung trống. Hai bộ đỉnh được duy trì.
- Tập hợp đầu tiên sẽ chứa các đỉnh đã được đưa vào MST, trong khi tập hợp khác chứa các đỉnh chưa được đưa vào.
- Ở mỗi bước, thuật toán xem xét tất cả các cạnh sẽ kết nối hai tập hợp. Sau đó, nó chọn cạnh trọng lượng tối thiểu trong số các cạnh này.
- Sau bước này, thuật toán sẽ di chuyển đến điểm cuối khác của cạnh của tập hợp chứa MST.
- Cây mở rộng tối thiểu có thể được xây dựng từ bất kỳ đỉnh nào trong biểu đồ.
- Một nút được di chuyển nhiều lần để nhận được giá trị khoảng cách nhỏ nhất.
- Nó có độ phức tạp về thời gian là O (V2), trong đó V là số đỉnh. Độ phức tạp thời gian này có thể được nâng cao lên thành O (E + log V) bằng cách sử dụng các đống Fibonacci.
- Nó chạy nhanh trong các biểu đồ dày đặc.
- Nó cung cấp cho các thành phần được kết nối và chỉ hoạt động với biểu đồ được kết nối.
Các bước tìm MST bằng thuật toán Prim:
- Một mstSet được tạo, theo dõi các đỉnh đã được đưa vào MST.
- Một giá trị khóa được chỉ định cho tất cả các đỉnh của đồ thị đầu vào.
- Các giá trị khóa ban đầu được chỉ định là 'INFINITE'.
- Giá trị khóa 0 được gán cho đỉnh đầu tiên để nó có thể được chọn trước.
- Khi mstSet không bao gồm tất cả các đỉnh, các bước dưới đây được thực hiện theo các bước sau.
- Một đỉnh 'u' được chọn không có trong mstSet và cũng có giá trị khóa tối thiểu.
- Chữ 'u' này hiện đã được đưa vào mstSet.
- Giá trị khóa của tất cả các đỉnh liền kề của 'u' đều được cập nhật.
- Điều này có thể được thực hiện bằng cách lặp lại qua tất cả các đỉnh liền kề.
- Đối với mọi đỉnh lân cận 'v', nếu trọng số của cạnh "u" - "v" nhỏ hơn trọng số của giá trị khóa trước đó của "v", thì giá trị khóa được cập nhật thành trọng số của 'u-v '.