(α)

(β)

Σχήμα 3.7: Διαθέτουμε ένα γρήγορο όχημα, (κόκκινο) και ένα αργό όχημα (πράσσινο) (α). Ο τροπο-
ποιημένος αλγόριθμος DARP θα διαμοιράσει κατάλληλα την συνολική αρχική περιοχή στα οχήματα
βάσει της ταχύτητάς τους (β).

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

T :=

f o r e s t c o n s i s t i n g o f G’ s v e r t e x e s and no edges

While T i s not connected

For each T

i

i n T

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

t h a t c o n n e c t s T

i

with T

i

’

∈ T

Connect T

i

and T

i

’ v i a e

Return T

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

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

με το ελάχιστο βάρος ακμής προς μια κορυϕή του δέντρου που δεν έχει προστεθεί

ήδη σε αυτό. Στον αλγόριθμο 4 δίνεται ο ψευδοκώδικας για τον αλγόριθμο του

Prim.

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

T :=

t r e e with v e r t e x V

i

∈ V

For i = 1 u n t i l i =

|V | − 2

Find edge uv with t h e l o w e s t weight so t h a t

u

∈ V (T ) and v /∈ V (T )

T :=

T+uv

Return T

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

41