Algoritme van Kruskal

Ik moet een groepswerk maken over grafen en één van de vragen is om het algoritme van Kruskal uit te leggen. Ik heb hiervoor gezocht met google en wat dingen gevonden, maar begrijp er geen snars van. Kunnen jullie mij helpen ?

Vicky
3de graad ASO - zaterdag 5 november 2005

Antwoord

Dag Vicky,

Op deze link staat het algoritme uitgelegd, en je kan het ook in zijn werk zien gaan (klik dan op Step Solve).

Het algoritme werkt als volgt: je hebt een begingraaf G met een aantal toppen, en een aantal bogen tussen deze toppen. Aan elk van de bogen is een bepaald gewicht toegekend. Nu zoekt het algoritme naar de 'minimal spanning tree', dit is een graaf H die aan volgende voorwaarden voldoet:
- De toppen van H zijn alle toppen van G
- De bogen van H is een deelverzameling van de bogen van G
- H is samenhangend
- H is een boom, dus bevat geen cykels, of nog anders uitgedrukt: als je één boog schrapt is hij niet meer samenhangend
- Het gewicht van alle bogen van H samen, is zo laag mogelijk.

Het algoritme werkt als volgt: je start met een lege H (geen bogen). Selecteer van alle bogen van G, die met het laagste gewicht, en voeg deze boog (dus de twee toppen en de verbinding ertussen) toe aan H. Dit blijf je steeds herhalen, dus na de eerste stap moet je de boog uit G kiezen met het op één na laagste gewicht, en die voeg je aan H toe, etc. Alleen, als de toevoeging van zo een boog aan H ervoor zou zorgen dat in H een cykel ontstaat, dan mag je die toevoeging niet uitvoeren.
Je blijft hiermee doorgaan tot H een samenhangende graaf is die alle toppen van G verbindt. Het algoritme levert altijd de gevraagde minimal spanning tree op.

Kijk op die link eens na of je de uitvoering van het algoritme begrijpt..

Groeten,
Christophe.

Christophe
zaterdag 5 november 2005

©2001-2024 WisFaq