Prims algoritm
Sign in to saveAlso known as DJP algorithm, Jarník algorithm, Prim–Jarník algorithm, Prim–Dijkstra algorithm, Jarnik algorithm
algorithm for finding the minimum spanning tree for weighted undirected graphs
Article · Svenska
Prims algoritm är en girig algoritm för att skapa ett minimalt uppspännande träd från en godtycklig sammanhängande, kostnadad och oriktad graf. Algoritmen finner i varje iteration den länk med lägst kostnad som kan förbinda trädet med en nod som ännu inte finns med i trädet, varpå trädet utökas med denna länk (och den nod som den ansluter till). Iterationen fortsätter så länge det finns noder som inte lagts till i trädet.
Abstract from DBpedia / Wikipedia · CC BY-SA