Het algoritme van Kruskal

Ga uit van een samenhangende gewogen graaf G op minstens drie punten en een graaf H met dezelfde punten als G, maar nog géén lijnen.

1. Begin: Voeg een lijn van G met laagste gewicht toe aan H.

2. Uitbreiding: Kies een lijn van G die nog niet in H zit, zodat 

- de graaf die uit H ontstaat door de lijn aan H toe te voegen geen cykel bevat.

- Het gewicht van die lijn zo laag mogelijk is.

3. Einde: Stop op het moment dat er bij stap 2 geen nieuwe lijn gekozen kan worden. H is dan een minimale opspannende boom van G.

Voorbeeld

Bepaal nu met het algoritme van Kruskal een goedkoopste netwerk van figuur 34. Wat zijn de totale kosten van dit netwerk?

1. Het laagste gewicht dat voorkomt in de graaf is 2. Daarom stoppen we als eerste de lijn met gewicht 2 in H.

Vervolgens hebben 3 en 4 als laagste gewicht dat in de graaf voorkomt. Die stoppen we dan als volgt in de graaf H.

2. Er zijn 6 lijnen met gewicht 5; ah, gh, fe, bc, eh en cd. Maakt niet uit welke we kiezen want geen van de lijnen creërt een cykel in de graaf H. We kiezen voor bc.

3. We gaan terug naar stap 2 om te kijken of er nog meer lijnen aan H toegevoegd kunnen worden.

Tweede ronde

2. ah, gh, fe, eh en cd hebben dezelfde laagste waarde. We kiezen cd want deze maakt geen cykel in H.

3. Opnieuw stap 2.

Derde ronde

2. ah, gh, fe en eh hebben dezelfde laagste waarde. We kiezen eh want deze maakt geen cykel in H.

3. opnieuw stap 2.

Vierde ronde

2. ah en ef maken een cykel dus die kunnen we niet gebruiken in H dan is gh de laagste waarde. We kiezen gh.

3. opnieuw stap 2

Vijfde ronde

2. elke lijn geeft een cykel.

totale gewicht van H is

2+3+4+5+5+5+5=29

opdracht 20

Gebruik het algoritme van Kruskal om een goedkoopste netwerk te vinden tussen de steden uit figuur 35. Geef ook de totale kosten van dit netwerk.

figuur 35