Kruskal vs Prim
Trong khoa học máy tính, thuật toán của Prim và Kruskal là một thuật toán tham lam tìm cây bao trùm tối thiểu cho một biểu đồ vô hướng có trọng số được kết nối. Cây bao trùm là một đồ thị con của đồ thị sao cho mỗi nút của đồ thị được nối với nhau bằng một đường dẫn, đó là một cây. Mỗi cây bao trùm đều có trọng số và trọng số / chi phí tối thiểu có thể có của tất cả các cây bao trùm là cây bao trùm tối thiểu (MST).
Tìm hiểu thêm về Thuật toán Prim
Thuật toán được phát triển bởi nhà toán học người Séc Vojtěch Jarník vào năm 1930 và sau đó được nhà khoa học máy tính Robert C. Prim độc lập vào năm 1957. Nó được phát hiện lại bởi Edsger Dijkstra vào năm 1959. Thuật toán có thể được nêu trong ba bước chính;
Cho đồ thị liên thông với n nút và trọng số tương ứng của mỗi cạnh, 1. Chọn một nút tùy ý từ biểu đồ và thêm nó vào cây T (sẽ là nút đầu tiên)
2. Xem xét trọng số của mỗi cạnh được kết nối với các nút trong cây và chọn giá trị nhỏ nhất. Thêm cạnh và nút ở đầu kia của cây T và xóa cạnh khỏi đồ thị. (Chọn bất kỳ nếu tồn tại hai hoặc nhiều điểm tối thiểu)
3. Lặp lại bước 2, cho đến khi n-1 cạnh được thêm vào cây.
Trong phương pháp này, cây bắt đầu với một nút tùy ý duy nhất và mở rộng từ nút đó trở đi với mỗi chu kỳ. Do đó, để thuật toán hoạt động bình thường, đồ thị cần phải là đồ thị liên thông. Dạng cơ bản của thuật toán Prim có độ phức tạp thời gian là O (V2).
Tìm hiểu thêm về Thuật toán Kruskal
Thuật toán do Joseph Kruskal phát triển đã xuất hiện trong quá trình tố tụng của Hiệp hội Toán học Hoa Kỳ vào năm 1956. Thuật toán của Kruskal cũng có thể được thể hiện bằng ba bước đơn giản.
Cho đồ thị có n nút và trọng số tương ứng của mỗi cạnh, 1. Chọn cung có trọng số nhỏ nhất trong toàn bộ biểu đồ và thêm vào cây và xóa khỏi biểu đồ.
2. Trong số còn lại, hãy chọn cạnh có trọng số nhỏ nhất, theo cách không tạo thành chu trình. Thêm cạnh vào cây và xóa khỏi biểu đồ. (Chọn bất kỳ nếu tồn tại hai hoặc nhiều điểm tối thiểu)
3. Lặp lại quy trình ở bước 2.
Trong phương pháp này, thuật toán bắt đầu với cạnh có trọng số nhỏ nhất và tiếp tục chọn từng cạnh ở mỗi chu kỳ. Do đó, trong thuật toán, đồ thị không cần được kết nối. Thuật toán của Kruskal có độ phức tạp về thời gian là O (logV)
Sự khác biệt giữa Kruskal’s và Prim’s Algorithm là gì?
• Thuật toán của Prim khởi tạo bằng một nút, trong khi thuật toán của Kruskal bắt đầu bằng một cạnh.
• Các thuật toán của Prim trải dài từ nút này sang nút khác trong khi thuật toán của Kruskal chọn các cạnh theo cách mà vị trí của cạnh không dựa trên bước cuối cùng.
• Trong thuật toán của nguyên tắc, biểu đồ phải là một biểu đồ được kết nối trong khi Kruskal’s cũng có thể hoạt động trên các biểu đồ bị ngắt kết nối.
• Thuật toán của Prim có độ phức tạp về thời gian là O (V2) và độ phức tạp về thời gian của Kruskal là O (logV).
