3.7.3

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

Αρχικά, ο αλγόριθμος του Kruskal ταξινομεί τις ακμές του γράϕου κατά αύξον

βάρος. Έπειτα, επιλέγει την ακμή με το ελάχιστο βάρος και την προσθέτει στο

δέντρο. Σε κάθε επανάληψη, δημιουργεί ένα δάσος δέντρων ως υπό-γραϕήματα του

G, επιλέγει την ακμή με το μικρότερο βάρος και την προσθέτει στο αντίστοιχο δέντρο

εϕόσον η προσθήκη της δεν δημιουργεί κύκλο με αυτές που έχουν ήδη προστεθεί.

Ο αλγόριθμος τερματίζει όταν έχουν προστεθεί

|V | − 1 ακμές στο δέντρο. Στον

αλγόριθμο 5 δίνεται ο ψευδοκώδικας για τον αλγόριθμο του Kruskal.

Function Kruskal (G : weighted u n d i r e c t e d graph )

T =

empty subgraph o f G

S o r t edges by weight i n a l i s t

Fori = 1 u n t i l i =

|V | − 1

Find edge e with t h e l o w e s t weight

I f adding e does not c r e a t e a c i r c l e

then T = T + e

e l s e remove e from l i s t

Return T

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

Ο αλγόριθμος του Kruskal υπολογίζει το Ελάχιστο Γεννητικό Δέντρο με ανομοιό-

μορϕο τρόπο, ο οποίος υποδεικνύεται από την κατάταξη των ακμών και των βαρών.

Η πολυπλοκότητα του αλγορίθμου σε σχέση με το πλήθος των ακμών και κορυϕών

του μπορεί να είναι O(

|E| ∗ log|E|) για αραιά γραϕήματα και O(|E| ∗ log|V |) για

πυκνά. Ενδείκνυται για περιπτώσεις στις οποίες τα βάρη των ακμών μπορούν να

ταξινομηθούν σε μικρό χρόνο, όπως οταν είναι μικροί ακέραιοι αριθμοί ή οταν το

γράϕημα είναι αραιό, δεν περιέχει δηλαδή πολλές ακμές. Στο σχήμα 3.9 βλέπουμε

σχηματικά την βηματική εκτέλεση του αλγορίθμου Kruskal.

Στην παρούσα διπλωματική εργασία, για την κατασκευή των Ελαχίστων Γεν-

νητικών Δέντρων χρησιμοποιήθηκε ο αλγόριθμος του Kruskal καθώς πειραματικά

βρέθηκε ότι είναι 25% πιο αποδοτικός σε σχέση με τον αλγόριθμο του Prim και τον

αλγόριθμο του Borůvka.

Ο αλγόριθμος του Kruskal ως έξοδο έχει το Ελάχιστο Γεννητικό Δέντρο της

περιοχής του κάθε οχήματος σε μορϕή γράϕου. Για το σχήμα 3.6, το υπολογισμένο

42