A minsta spännträd (MST) definieras som en Spanning Tree som har minsta vikt bland alla möjliga spännträd
A Spanning Tree definieras som en trädliknande subgraf av en sammankopplad, oriktad graf som inkluderar alla hörn i grafen. Eller, för att säga med lekmans ord, det är en delmängd av grafens kanter som bildar ett träd ( acyklisk ) där varje nod i grafen är en del av trädet.
Det minsta spännträdet har alla egenskaper som ett spännträd med en extra begränsning att ha minsta möjliga vikt bland alla möjliga spännträd. Liksom ett spännträd kan det också finnas många möjliga MST:er för en graf.
Egenskaper hos ett spännande träd:
Spännträdet håller nedan nämnda principer :
- Antalet hörn ( I ) i grafen och spännträdet är detsamma.
- Det finns ett fast antal kanter i spännträdet som är lika med en mindre än det totala antalet hörn ( OCH = V-1 ).
- Spännträdet ska inte vara det osammanhängande , eftersom det bara borde finnas en enda källa till komponent, inte mer än så.
- Spännträdet ska vara acyklisk, som betyder att det inte skulle finnas någon cykel i trädet.
- Den totala kostnaden (eller vikten) för spännträdet definieras som summan av kantvikterna för alla kanter av spännträdet.
- Det kan finnas många möjliga spännträd för en graf.
Minsta spännvidd:
A minsta spännträd (MST) definieras som en Spanning Tree som har minsta vikt bland alla möjliga spännträd.
Det minsta spännträdet har alla egenskaper som ett spännträd med en extra begränsning att ha minsta möjliga vikt bland alla möjliga spännträd. Liksom ett spännträd kan det också finnas många möjliga MST:er för en graf.
- Låt oss titta på MST i exemplet ovan,
Minsta spannande träd
Algoritmer för att hitta minsta spännträd:
Det finns flera algoritmer för att hitta det minsta spännträdet från en given graf, några av dem är listade nedan:
Kruskals Minimum Spanning Tree Algorithm:
Detta är en av de populära algoritmerna för att hitta det minsta spännträdet från en ansluten, oriktad graf. Det här är en Först sorterar den alla kanter på grafen efter deras vikt,
Denna algoritm kan implementeras effektivt med hjälp av en DSU ( Disjoint-Set ) datastruktur för att hålla reda på de anslutna komponenterna i grafen. Detta används i en mängd praktiska tillämpningar som nätverksdesign, klustring och dataanalys.
java sträng understräng
Följ artikeln på Kruskals Minimum Spanning Tree Algorithm för en bättre förståelse och implementering av algoritmen.
Prims algoritm för minimum spannning tree:
Detta är också en girig algoritm. Denna algoritm har följande arbetsflöde:
- Det börjar med att välja en godtycklig vertex och sedan lägga till den i MST.
- Sedan kontrollerar den upprepade gånger efter den lägsta kantvikten som förbinder en topp av MST med en annan vertex som ännu inte är i MST.
- Denna process fortsätter tills alla hörn är inkluderade i MST.
För att effektivt välja lägsta viktkant för varje iteration använder denna algoritm priority_queue för att lagra hörnen sorterade efter deras lägsta kantvikt för närvarande. Den håller också samtidigt reda på MST med hjälp av en array eller annan datastruktur som är lämplig med tanke på vilken datatyp den lagrar.
Denna algoritm kan användas i olika scenarier som bildsegmentering baserat på färg, struktur eller andra funktioner. För routing, som att hitta den kortaste vägen mellan två punkter för en lastbil att följa.
Följ artikeln på Prims algoritm för minimum spannning tree för en bättre förståelse och implementering av denna algoritm.
Boruvkas minimum spannning tree-algoritm:
Detta är också en grafövergångsalgoritm som används för att hitta det minsta spännträdet för en ansluten, oriktad graf. Detta är en av de äldsta algoritmerna. Algoritmen fungerar genom att iterativt bygga minsta spännträd, med början med varje vertex i grafen som sitt eget träd. I varje iteration hittar algoritmen den billigaste kanten som kopplar ett träd till ett annat träd och lägger till den kanten till det minsta spännträdet. Detta liknar nästan Prims algoritm för att hitta det minsta spännträdet. Algoritmen har följande arbetsflöde:
- Initiera en skog av träd, med varje vertex i grafen som sitt eget träd.
- För varje träd i skogen:
- Hitta den billigaste kanten som kopplar den till ett annat träd. Lägg till dessa kanter till det minsta spännträdet.
- Uppdatera skogen genom att slå samman träden som är förbundna med de tillagda kanterna.
- Upprepa stegen ovan tills skogen bara innehåller ett träd, vilket är det minsta spännträdet.
Algoritmen kan implementeras med hjälp av en datastruktur såsom en prioritetskö för att effektivt hitta den billigaste kanten mellan träden. Boruvkas algoritm är en enkel och lättimplementerad algoritm för att hitta minsta spännträd, men den kanske inte är lika effektiv som andra algoritmer för stora grafer med många kanter.
Följ artikeln på Boruvkas Minimum Spanning Tree Algorithm för en bättre förståelse och implementering av denna algoritm.
För att veta mer om egenskaperna och egenskaperna hos Minimum Spanning Tree, klicka här.
Tillämpningar av träd med minsta spännvidd:
- Nätverksdesign : Spännande träd kan användas i nätverksdesign för att hitta det minsta antal anslutningar som krävs för att ansluta alla noder. Särskilt minsta spännande träd kan hjälpa till att minimera kostnaden för anslutningarna genom att välja de billigaste kanterna.
- Bildbehandling : Spännande träd kan användas i bildbehandling för att identifiera områden med liknande intensitet eller färg, vilket kan vara användbart för segmenterings- och klassificeringsuppgifter.
- Biologi : Spännande träd och minsta spännande träd kan användas inom biologin för att konstruera fylogenetiska träd för att representera evolutionära relationer mellan arter eller gener.
- Analys av sociala nätverk : Spännande träd och minsta spännträd kan användas i sociala nätverksanalyser för att identifiera viktiga kopplingar och relationer mellan individer eller grupper.
Några populära intervjuproblem på MST
| 1. | Hitta den lägsta kostnaden för att ansluta alla städer | Öva |
Några vanliga frågor om minsta spännande träd:
1. Kan det finnas flera minimi-spännande träd för en given graf?
Ja, en graf kan ha flera minsta spännträd om det finns flera uppsättningar kanter med samma minsta totalvikt.
2. Kan Kruskals algoritm och Prims algoritm användas för riktade grafer?
Nej, Kruskals algoritm och Prims algoritm är endast utformade för oriktade grafer.
3. Kan en frånkopplad graf ha ett minsta spännträd?
Nej, en frånkopplad graf kan inte ha ett spännträd eftersom det inte spänner över alla hörn. Därför kan den inte heller ha ett minsta spännträd.
4. Kan ett minimum spännträd hittas med Dijkstras algoritm?
Nej, Dijkstras algoritm används för att hitta den kortaste vägen mellan två hörn i en viktad graf. Den är inte utformad för att hitta ett minsta spännträd.
5. Vad är tidskomplexiteten för Kruskals och Prims algoritmer?
Både Kruskals och Prims algoritmer har en tidskomplexitet på O(ElogE) , där E är antalet kanter i grafen.