Toppfrågor
Tidslinje
Chatt
Perspektiv

Kruskals algoritm

Från Wikipedia, den fria encyklopedin

Kruskals algoritm
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.

Snabbfakta Uppkallad efter, Utgiv­nings­da­tum ...

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

Mer information Bild, Beskrivning ...
Remove ads

Se även

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads