Kruskal vs Prim
Στην επιστήμη των υπολογιστών, οι αλγόριθμοι του Prim και του Kruskal είναι ένας άπληστος αλγόριθμος που βρίσκει ένα ελάχιστο εκτεινόμενο δέντρο για ένα συνδεδεμένο σταθμισμένο μη κατευθυνόμενο γράφημα. Ένα εκτεινόμενο δέντρο είναι ένα υπογράφημα ενός γραφήματος έτσι ώστε κάθε κόμβος του γραφήματος να συνδέεται με μια διαδρομή, η οποία είναι ένα δέντρο. Κάθε δέντρο που εκτείνεται έχει ένα βάρος και τα ελάχιστα δυνατά βάρη/κόστος όλων των δέντρων που εκτείνονται είναι το ελάχιστο εκτεινόμενο δέντρο (MST).
Περισσότερα για τον αλγόριθμο Prim
Ο αλγόριθμος αναπτύχθηκε από τον Τσέχο μαθηματικό Vojtěch Jarník το 1930 και αργότερα ανεξάρτητα από τον επιστήμονα υπολογιστών Robert C. Prim το 1957. Ανακαλύφθηκε ξανά από τον Edsger Dijkstra το 1959. Ο αλγόριθμος μπορεί να δηλωθεί σε τρία βασικά βήματα.
Δεδομένου του συνδεδεμένου γραφήματος με n κόμβους και το αντίστοιχο βάρος κάθε ακμής, 1. Επιλέξτε έναν αυθαίρετο κόμβο από το γράφημα και προσθέστε τον στο δέντρο T (που θα είναι ο πρώτος κόμβος)
2. Εξετάστε τα βάρη κάθε άκρης που συνδέεται με τους κόμβους στο δέντρο και επιλέξτε το ελάχιστο. Προσθέστε την άκρη και τον κόμβο στο άλλο άκρο του δέντρου T και αφαιρέστε την άκρη από το γράφημα. (Επιλέξτε οποιοδήποτε εάν υπάρχουν δύο ή περισσότερα ελάχιστα)
3. Επαναλάβετε το βήμα 2, μέχρι να προστεθούν n-1 άκρες στο δέντρο.
Σε αυτήν τη μέθοδο, το δέντρο ξεκινά με έναν μόνο αυθαίρετο κόμβο και επεκτείνεται από αυτόν τον κόμβο και μετά με κάθε κύκλο. Ως εκ τούτου, για να λειτουργήσει σωστά ο αλγόριθμος, το γράφημα πρέπει να είναι ένα συνδεδεμένο γράφημα. Η βασική μορφή του αλγορίθμου του Prim έχει χρονική πολυπλοκότητα O(V2).
Περισσότερα για τον Αλγόριθμο του Kruskal
Ο αλγόριθμος που αναπτύχθηκε από τον Joseph Kruskal εμφανίστηκε στα πρακτικά της American Mathematical Society το 1956. Ο αλγόριθμος του Kruskal μπορεί επίσης να εκφραστεί σε τρία απλά βήματα.
Δίνεται το γράφημα με n κόμβους και το αντίστοιχο βάρος κάθε ακμής, 1. Επιλέξτε το τόξο με το μικρότερο βάρος ολόκληρου του γραφήματος και προσθέστε το στο δέντρο και διαγράψτε από το γράφημα.
2. Από τα υπόλοιπα επιλέξτε τη λιγότερο σταθμισμένη άκρη, με τρόπο που να μην σχηματίζει κύκλο. Προσθέστε την άκρη στο δέντρο και διαγράψτε από το γράφημα. (Επιλέξτε οποιοδήποτε εάν υπάρχουν δύο ή περισσότερα ελάχιστα)
3. Επαναλάβετε τη διαδικασία στο βήμα 2.
Σε αυτήν τη μέθοδο, ο αλγόριθμος ξεκινά με το λιγότερο σταθμισμένο άκρο και συνεχίζει επιλέγοντας κάθε ακμή σε κάθε κύκλο. Επομένως, στον αλγόριθμο το γράφημα δεν χρειάζεται να συνδεθεί. Ο αλγόριθμος του Kruskal έχει χρονική πολυπλοκότητα O(logV)
Ποια είναι η διαφορά μεταξύ του αλγόριθμου Kruskal και του Prim;
• Ο αλγόριθμος του Prim ξεκινά με έναν κόμβο, ενώ ο αλγόριθμος του Kruskal ξεκινά με ένα άκρο.
• Οι αλγόριθμοι του Prim εκτείνονται από τον έναν κόμβο στον άλλο, ενώ ο αλγόριθμος του Kruskal επιλέγει τις άκρες με τρόπο ώστε η θέση της ακμής να μην βασίζεται στο τελευταίο βήμα.
• Στον αλγόριθμο prim, το γράφημα πρέπει να είναι ένα συνδεδεμένο γράφημα, ενώ το Kruskal μπορεί να λειτουργεί και σε αποσυνδεδεμένα γραφήματα.
• Ο αλγόριθμος του Prim έχει χρονική πολυπλοκότητα O(V2) και η χρονική πολυπλοκότητα του Kruskal είναι O(logV).
