Σχήμα 3.6: Στο σχήμα βλέπουμε τον διαχωρισμό της συνολικής περιοχής χρησιμοποιώντας τον αλ-
γόριθμο DARP για το σχήμα 3.4. Σε αυτήν την περίπτωση, έχουμε μόνο ένα όχημα. Συνεπώς, όλος
ο χώρος θα ανατεθεί στο ένα και μοναδικό όχημα.

3.7.1

Αλγόριθμος του Borůvka

Ο αλγόριθμος του Borůvka δημιουργεί το ΕΓΔ από ένα δάσος δέντρων το οποίο

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

ο αλγόριθμος εντοπίζει την ακμή με το ελάχιστο βάρος μεταξύ δυο διαϕορετικών

δέντρων του δάσους και συγχωνεύει τα υπολογισμένα δέντρα σε ένα μεγαλύτερο

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

έχουν ενωθεί δίνοντας το συνεκτικό τελικό ΕΓΔ [28]. Στον αλγόριθμο 3 δίνεται ο

ψευδοκώδικας για τον αλγόριθμο του Borůvka. Η πολυπλοκότητα του αλγορίθμου

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

O(

|E| ∗ log|V |).

3.7.2

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

Ο συγκεκριμένος αλγόριθμος, παρόλο που αρχικά προτάθηκε από τον Prim, V.

Jarnik και E. Dijkstra, έμεινε γνωστός ως ο αλγόριθμος του Prim. Αρχικά, ξεκινάει

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

αυτό μια ακμή κάθε ϕορά. Ο αλγόριθμος τερματίζει σε

|V | − 1 επαναλήψεις και σε

40