Prims algoritme

Prims algoritme ble oppdaget av Vojtech Jarnik i 1930, og senere, uavhengig, av Robert Clay Prim i 1957. Prims algoritme er en grådig algoritme som finner det minste utspennende treet i en vektet graf. Algoritmen har en tidskompleksitet på O(|E| log|V|), der |V| er antall hjørner og |E| er antall kanter i grafen. Tidskompleksiteten til algoritmen er avhengig av implementeringen av prioritetskøen. Om denne implementeres med en Fibonnaci heap, vil tidskompleksiteten bli O(|E| + |V|log|V|). Algoritme er med andre ord noe rart, skummelt og ikke særlig forståelig.

Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.