minimaal opspannende boom

De minimaal opspannende boom van een verbonden, gewogen graaf is de verbonden subgraaf daarvan met het kleinste totale gewicht. Deze kleinste subgraaf is altijd een boom, dat wil zeggen een graaf zonder cycli. Een algoritme om de minimaal opspannende boom te vinden is het algoritme van Prim: * kies een willekeurige knoop, de eerste bezochte knoop * kies de zijde met de laagste waarde verbonden met deze knoop * neem de knoop aan de andere zijde van de zijde op in de verzameling bezochte knopen * kies de zijde met de laagste waarde uit deze verzameling naar een knoop die nog niet is bezocht en voeg deze zijde aan de minimaal opspannende boom toe * neem de nieuwe bereikte knoop op in je verzameling * ga door tot alle knopen van de graaf bezocht zijn Hier een ander algoritme voor is Kruskals algoritme, maar er zijn er meer. Een gegeven graaf kan in het algemeen verschillende minimaal opspannende bomen hebben. Alleen wanneer alle zijden van de graaf een verschillend gewicht hebben is er een unieke, minimaal opspannende boom.