Kanter i træet
Samlet længde
Undersøgte kanter

  • Aktuel
  • I træet
  • Ville lukke en kreds

Mere om Kruskals algoritme

Kruskals algoritme

Kruskals algoritme bygger et minimalt udspændende træ, det billigste sæt kanter, der forbinder alle knuder, på den enklest tænkelige måde: tag kanterne fra kortest til længst, og behold hver enkelt, medmindre den ville lukke en kreds. Gå trin for trin for at se adskilte stykker vokse og smelte sammen til ét træ, og de kanter, der springes over. Tryk på Afspil for at se træet vokse, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Tallet på hver kant er dens længde. Under grafen står de kanter, der endnu skal prøves, fra kortest til længst; en kant, hvis ender allerede er forbundet, ville lukke en kreds og tegnes stiplet med rødt. Ny graf laver en anden graf; vælg, hvor mange knuder og kanter den har. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.

Sådan virker det

  1. Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen.
  2. Træk i trinskyderen for at springe hvorhen som helst. De kanter, der endnu skal prøves, står under grafen, kortest først.
  3. Hold øje med kanterne, der er stiplet med rødt: de ville lukke en kreds. Ny graf laver en anden graf, du kan prøve.

Sådan virker Kruskals algoritme

Sortér alle kanter fra kortest til længst. Start med hver knude som sit eget stykke. Prøv kanterne i rækkefølge: hvis en kant forbinder to forskellige stykker, kommer den med i træet, og de to stykker bliver ét; hvis dens to ender allerede er i samme stykke, ville den lukke en kreds, så spring den over. Stop, når alt er ét stykke. Det sker efter én kant færre, end der er knuder, ofte længe før den sidste kant er prøvet.

Union-find

For hver kant skal Kruskals algoritme spørge, om dens to ender allerede er forbundet. En union-find-struktur svarer hurtigt på det: hvert stykke har én repræsentant, find følger henvisningerne hen til den, og union kobler den ene repræsentant til den anden. Med to enkle tricks, stikomprimering og forening efter størrelse, tager hvert spørgsmål næsten konstant tid, så sorteringen af kanterne er den langsomste del, med et arbejde, der vokser med E log E.

Ofte stillede spørgsmål

Hvad er Kruskals algoritme?

En grådig algoritme, der bygger et minimalt udspændende træ ved at sortere alle kanter fra kortest til længst og tilføje hver kant, der ikke lukker en kreds med de kanter, der allerede er valgt.

Hvordan opdager Kruskals algoritme en kreds?

En kant lukker en kreds, netop når dens to ender allerede er forbundet af valgte kanter. En union-find-struktur holder styr på, hvilke knuder der er forbundet, og svarer på det spørgsmål næsten med det samme.

Hvorfor virker Kruskals algoritme?

På grund af kredsegenskaben: den længste kant i en kreds er aldrig nødvendig for et minimalt udspændende træ. Hver kant, Kruskal springer over, er den længste i den kreds, den ville lukke, da alle kanter før den var kortere eller lige så lange.

Hvornår skal jeg bruge Kruskal i stedet for Prim?

Kruskals algoritme er enkel og hurtig på tynde grafer og virker direkte på en almindelig liste over kanter. Prims algoritme passer til tætte grafer og grafer, der er gemt som nabolister. Begge finder et træ med samme samlede længde.

Bliver min graf sendt nogen steder hen?

Nej. Grafen laves, og træet bygges i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor