Algoritme van Prim

Het algoritme van Prim is een algoritme om de minimaal opspannende boom van een graaf te vinden.

Het algoritme werd in 1930 ontdekt door de wiskundige Vojtěch Jarník en in 1957 onafhankelijk herontdekt door de informaticus Robert C. Prim. In 1959 werd het ook door Dijkstra ontdekt. Het algoritme wordt ook wel eens het DJP-algoritme of algoritme van Jarnik genoemd.

Algoritme

Gegeven een samenhangende gewogen graaf $G = (V, E)$ met een verzameling knopen $V = {v_1, v_2, ..., v_n}$. De volgende procedure is een algoritme dat een minimale opspannende boom T construeert.

• Start: $T = ({v_1}, 0)$
• Stop?: stoppen indien $T$ $(n-1)$ bogen heeft
• Boog toevoegen:

Van alle bogen die een knoop van $T$ verbinden met een knoop die niet tot $T$ behoort, voeg de boog met het kleinste gewicht toe (indien meerdere met het kleinste gewicht 1 kiezen).

Deze boog bestaat aangezien het een samenhangende graaf is en $T$ nog niet alle knopen bevat. $T$ zal door deze stap geen kringen bevatten aangezien de toegevoegde knoop nog niet in $T$ zat. Ga terug naar de stap Stop?

Zie ook

• Kruskals algoritme
• Grafentheorie

Mediabestanden

Zie de categorie Prim's Algorithm van Wikimedia Commons voor meer mediabestanden.