- Aktuell
- I trädet
- Intill trädet
- Bästa kant hittills
- Skulle sluta en cykel
Minimalt uppspännande träd
Du vill koppla ihop varje stad med kabel, varje hus med vattenledningar eller varje dator i ett nätverk, med så lite material som möjligt. Svaret är ett minimalt uppspännande träd: de kanter som förbinder varje nod med minsta totala längd. Välj Kruskals eller Prims algoritm och gå steg för steg för att se trädet växa, en kortaste tillåten kant i taget. Tryck på Spela för att se trädet växa, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Välj algoritm: Kruskal provar kanterna från kortast till längst, Prim låter ett träd växa från starten; klicka på en nod för att göra den till Prims start. Talet på varje kant är dess längd. Under grafen finns listan över kanter som återstår att prova, eller noderna som väntar på att ansluta med längden på sin bästa kant till trädet. Ny graf skapar en annan graf; välj hur många noder och kanter den har. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Välj Kruskals eller Prims algoritm. För Prim klickar du på en nod för att göra den till start.
- Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst.
- Se kanterna läggas i trädet och den totala längden växa. Ny graf skapar en annan graf att prova.
Kruskals algoritm
Sortera alla kanter från kortast till längst och prova dem i den ordningen. Om en kant förenar två delar som inte är förbundna än, läggs den i trädet. Om dess två ändar redan är förbundna genom trädet skulle den sluta en cykel, så den hoppas över. Sluta när trädet har en kant färre än det finns noder. För att snabbt avgöra om två noder redan är förbundna håller Kruskals algoritm reda på delarna i en union-find-struktur.
Prims algoritm
Börja med ett träd med en nod. Varje nod utanför trädet minns sin kortaste kant till trädet. Lägg gång på gång till den nod vars kant är kortast, tillsammans med den kanten, och kontrollera dess kanter: någon av dem kan ge en granne en kortare väg in i trädet. Prims algoritm liknar Dijkstras algoritm, men den jämför enskilda kanter, inte hela avstånd från starten. Båda algoritmerna slutar alltid med samma totala längd.
Ofta ställda frågor
Vad är ett minimalt uppspännande träd?
För en sammanhängande graf vars kanter har längder är ett uppspännande träd en mängd kanter som förbinder alla noder utan någon cykel; med n noder har det alltid n − 1 kanter. Ett minimalt uppspännande träd är ett uppspännande träd vars totala längd är så liten som möjligt.
Vad är skillnaden mellan Kruskals och Prims algoritm?
Kruskals algoritm går igenom hela grafens kanter från kortast till längst och förenar separata delar till ett träd. Prims algoritm låter ett enda träd växa från en start och lägger alltid till den kortaste kanten som går ut från det. Båda är giriga och hittar ett träd med samma totala längd; Kruskal passar glesa grafer, Prim täta.
Är det minimala uppspännande trädet unikt?
Ja, när alla kantlängder är olika. När vissa längder är lika kan det finnas flera träd med samma minsta summa, och algoritmerna kan välja olika beroende på hur de väljer mellan lika långa kanter.
Är ett minimalt uppspännande träd samma sak som kortaste vägar?
Nej. Det minimala uppspännande trädet håller den totala längden av alla kanter liten, men vägen mellan två noder i trädet kan vara mycket längre än deras kortaste väg. Använd Dijkstras algoritm för kortaste vägar.
Skickas min graf någonstans?
Nej. Grafen skapas och trädet byggs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor