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 weleens het DJP-algoritme of algoritme van Jarnik genoemd.

Algoritme

Gegeven een samenhangende gewogen graaf ${\displaystyle G=(V,E)}$ met een verzameling knopen ${\displaystyle V=\{v_{1},v_{2},\ldots ,v_{n}\}}$. De volgende procedure is een algoritme dat een minimale opspannende boom T construeert.

• Start: Initialiseer ${\displaystyle T=\{\{v_{1},v_{i}\}\}}$ met ${\displaystyle i}$ zodanig dat ${\displaystyle \{v_{1},v_{i}\}}$ de tak van minimale lengte vanuit ${\displaystyle v_{1}}$ is. (Merk op dat ${\displaystyle \{v_{i},v_{j}\}}$ de notatie voor ongeordende paren is: de bogen zijn ongericht.)
• Stop: Stop zodra ${\displaystyle T}$ precies ${\displaystyle n-1}$ bogen heeft.
• Boog toevoegen:

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

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

Voorbeeld

	Dit is de gegeven graaf, waarin de getallen naast de bogen de gewichten van die bogen voorstellen.
	Bij de start kiezen we een willekeurige knoop uit, knoop D. Deze is verbonden met (in het blauw aangegeven) knopen A, B, E en F door de bogen DA, DB, DE en DF. Daarvan heeft DA (lichtblauw) het kleinste gewicht. Dus wordt boog DA met knoop A aan de graaf T toegevoegd.
	Met de knopen A en D in de reeds gevormde (groene) graaf T zijn de knopen B, E en F verbonden door de bogen AB, DB, DE en DF. Van deze vier bogen heeft DF het kleinste gewicht. Dus wordt boog DF met knoop F aan de graaf T toegevoegd.
	Met de gevormde graaf T kunnen nu de knopen B, E en G verbonden worden door de bogen AB, DB, DE, FE en FG. Hiervan heeft boog AB het kleinste gewicht. Dus wordt boog AB met knoop B aan de graaf T toegevoegd.
	Met de gevormde graaf T kunnen nu de knopen C, door boog BC, E, door de bogen BE, DE en FE, en G, door de boog FG, verbonden worden. Van deze bogen heeft BE het kleinste gewicht. Dus wordt boog BE met knoop E toegevoegd aan T.
	Met de reeds gevormde graaf T kunnen de knopen C, door bogen BC en EC, en G, door de bogen EG en FG, verbonden worden. Van deze bogen heeft EC het kleinste gewicht. Dus wordt EC en knoop C aan T toegevoegd.
	De overblijvende knoop G kan door bogen EG en FG verbonden worden met graaf T. De boog EG heeft het kleinste gewicht, en dus wordt EG en knoop G toegevoegd aan T.
	Alle knopen zijn nu toegevoegd aan T en T vormt een minimaal opspannende boom van de gegeven graaf.

Zie ook

• Kruskals algoritme
• Grafentheorie

Mediabestanden

Zie de categorie Prim's algorithm van Wikimedia Commons voor mediabestanden over dit onderwerp.