Sự khác biệt giữa Kruskal và Prim
Share
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 thấy một cây bao trùm tối thiểu cho một đồ thị vô hướng có trọng số được kết nối. Cây bao trùm là một sơ đồ con của đồ thị sao cho mỗi nút của đồ thị được kết nối bằng một đường dẫn, đó là một cây. Mỗi cây bao trùm có trọng lượng và trọng lượng / 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 của 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 lập bởi nhà khoa học máy tính Robert C. Prim vào năm 1957. Nó đã được Edsger Dijkstra khám phá lại vào năm 1959. Thuật toán có thể được nêu trong ba bước chính;
Cho đồ thị được kết nối với n nút và trọng lượng 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 các 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 mức tối thiểu. Thêm cạnh và nút ở đầu kia của cây T và xóa cạnh khỏi biểu đồ. (Chọn bất kỳ nếu có hai hoặc nhiều mức tối thiểu tồn tại)
3. Lặp lại bước 2, cho đến khi các cạnh n-1 được thêm vào cây.
Trong phương thức này, cây bắt đầu với một nút tùy ý và mở rộng từ nút đó trở đi với mỗi chu kỳ. Do đó, để thuật toán hoạt động chính xác, biểu đồ cần phải là biểu đồ được kết nối. 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 của Kruskal
Thuật toán được phát triển bởi Joseph Kruskal đã 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ị với n nút và trọng lượng tương ứng của mỗi cạnh,
1. Chọn cung có trọng số nhỏ nhất của 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 chọn cạnh có trọng số nhỏ nhất, theo cách không tạo thành một chu kỳ. Thêm cạnh vào cây và xóa khỏi biểu đồ. (Chọn bất kỳ nếu có hai hoặc nhiều mức tối thiểu tồn tại)
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 phải được kết nối. Thuật toán của Kruskal có độ phức tạp thời gian là O (logV)
Sự khác biệt giữa thuật toán của Kruskal và Prim là gì?
• Thuật toán của Prim khởi tạo với một nút, trong khi thuật toán của Kruskal khởi tạo với 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 primer, đồ thị phải là một đồ thị được kết nối trong khi Kruskal cũng có thể hoạt động trên các đồ thị bị ngắt kết nối.
• Thuật toán của Prim có độ phức tạp thời gian là O (V2) và độ phức tạp thời gian của Kruskal là O (logV).
