Toppfrågor
Tidslinje
Chatt
Perspektiv
Kruskals algoritm
Från Wikipedia, den fria encyklopedin
Remove ads
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.
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.
Remove ads
Pseudokod
Algoritmen kan beskrivas på följande sätt:
- För att hitta ett minimalt uppspännande träd T i den sammanhängande grafen G
- Upprepa tills T innehåller alla noder i G
- Låt v vara den kortaste sträckan i G som inte märkts som förbrukad
- Märk v som förbrukad
- Om v inte bildar en cykel i T
- Lägg v till T
- T är ett minimalt uppspännande träd
Exempel
Remove ads
Se även
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads