Kruskals algoritm
From Wikipedia, the free encyclopedia
Kruskals algoritm är en girig algoritm för att skapa ett minimalt uppspännande träd från en godtycklig sammanhängande, viktad och oriktad graf.
Snabbfakta Uppkallad efter, Utgivningsdatum ...
Kruskals algoritm
Uppkallad efter | Joseph Kruskal | |
---|---|---|
Utgivningsdatum | 1956 | |
Upptäckare eller uppfinnare | Joseph Kruskal | |
Löser | minimalt uppspännande träd | |
Tidskomplexitet i värsta fall |
Stäng
Algoritmen bygger en skog av träd som allt eftersom växer ihop. Algoritmen är girig, eftersom den hela tiden lägger till den kortaste kanten den kan hitta till sina delträd.