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

  • Aktuel
  • I træet
  • Ved siden af træet
  • Bedste kant indtil nu
  • Ville lukke en kreds

Mere om minimalt udspændende træer

Minimalt udspændende træ

Du vil forbinde alle byer med kabel, alle huse med vandrør eller alle computere i et netværk og bruge så lidt materiale som muligt. Svaret er et minimalt udspændende træ: de kanter, der forbinder alle knuder med den mindste samlede længde. Vælg Kruskals eller Prims algoritme, og gå trin for trin for at se træet vokse, én kortest tilladt kant ad gangen. 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. Vælg algoritmen: Kruskal prøver kanterne fra kortest til længst, Prim lader ét træ vokse fra starten; klik på en knude for at gøre den til Prims start. Tallet på hver kant er dens længde. Under grafen står listen over kanter, der endnu skal prøves, eller de knuder, der venter på at komme med, med længden af deres bedste kant til træet. 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. Vælg Kruskals eller Prims algoritme. Ved Prim klikker du på en knude for at gøre den til start.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst.
  3. Se kanterne komme med i træet og den samlede længde vokse. Ny graf laver en anden graf, du kan prøve.

Kruskals algoritme

Sortér alle kanter fra kortest til længst, og prøv dem i den rækkefølge. Hvis en kant forbinder to stykker, der endnu ikke er forbundet, kommer den med i træet. Hvis dens to ender allerede er forbundet gennem træet, ville den lukke en kreds, så den springes over. Stop, når træet har én kant færre, end der er knuder. For hurtigt at se, om to knuder allerede er forbundet, holder Kruskals algoritme styr på stykkerne i en union-find-struktur.

Prims algoritme

Start med et træ med én knude. Hver knude uden for træet husker sin korteste kant til træet. Tilføj igen og igen den knude, hvis kant er kortest, sammen med den kant, og undersøg dens kanter: en af dem kan give en nabo en kortere vej ind i træet. Prims algoritme ligner Dijkstras algoritme, men den sammenligner enkelte kanter, ikke hele afstande fra starten. Begge algoritmer ender altid med den samme samlede længde.

Ofte stillede spørgsmål

Hvad er et minimalt udspændende træ?

For en sammenhængende graf, hvis kanter har længder, er et udspændende træ en mængde kanter, der forbinder alle knuderne uden nogen kreds; med n knuder har det altid n − 1 kanter. Et minimalt udspændende træ er et udspændende træ, hvis samlede længde er så lille som muligt.

Hvad er forskellen på Kruskals og Prims algoritme?

Kruskals algoritme gennemgår hele grafens kanter fra kortest til længst og samler adskilte stykker til ét træ. Prims algoritme lader ét træ vokse fra en start og tilføjer altid den korteste kant, der går ud fra det. Begge er grådige og finder et træ med samme samlede længde; Kruskal passer til tynde grafer, Prim til tætte.

Er det minimalt udspændende træ entydigt?

Ja, når alle kantlængder er forskellige. Når nogle længder er ens, kan der være flere træer med den samme mindste sum, og algoritmerne kan vælge forskellige, alt efter hvordan de vælger mellem lige lange kanter.

Er et minimalt udspændende træ det samme som korteste veje?

Nej. Det minimalt udspændende træ holder den samlede længde af alle kanter lille, men vejen mellem to knuder i træet kan være meget længere end deres korteste vej. Brug Dijkstras algoritme til korteste veje.

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