Αλγόριθμος του Kruskal

Abstract

Kruskal&#39;s algorithm is a minimum-spanning-tree algorithm which finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.<br/><br/>1. create a forest F (a set of trees), where each vertex in the graph is a separate tree<br/>2. create a set S containing all the edges in the graph<br/>3. while S is nonempty and F is not yet spanning remove an edge with minimum weight from S<br/>4. if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree<br/><br/>At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, the forest has a single component and forms a minimum spanning tree.

Aν οι ακμές ενός Γράφου έχουν εφοδιαστεί με τιμές που είναι είτε μήκος είτε κόστος, τότε μπορούμε να βρούμε το συντομότερο, ή το φθηνότερο δέντρο σύνδεσης. Ο αλγόριθμος του Kruskal λύνει αυτό το πρόβλημα. Η ιδέα είναι σχετικά απλή. Πρώτα σβήνουμε όλες τις ακμές και αφήνουμε μόνο τις n κορυφές. Στη συνέχεια επανατοποθετούμε τις ακμές τη μια μετά την άλλη, κατά αυξουσα τάξη βάρους, αλλά προσέχουμε να αγνοήσουμε κάθε ακμή που θα συμπλήρωνε ένα κύκλωμα. Η διαδικασία τελειώνει με την τοποθέτηση της n-1 ακμής.