Hopp til innhold

Prims algoritme

Fra Wikipedia, den frie encyklopedi
Sideversjon per 18. sep. 2005 kl. 12:46 av 84.188.221.30 (diskusjon) (Artikkelen er veldig kort, men det er ingenting galt med den, så jeg fjerner {{språkvask}}.)

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.