A minimaal opspannende boom (MST) wordt gedefinieerd als een overspannende boom dat het minimale gewicht heeft van alle mogelijke opspannende bomen
A overspannende boom wordt gedefinieerd als een boomachtige subgraaf van een verbonden, ongerichte grafiek die alle hoekpunten van de grafiek omvat. Of, om het in de woorden van de leek te zeggen: het is een subset van de randen van de grafiek die een boom vormt ( acyclisch ) waarbij elk knooppunt van de grafiek deel uitmaakt van de boom.
De minimaal opspannende boom heeft alle eigenschappen van een opspannende boom, met als extra beperking dat hij de minimaal mogelijke gewichten heeft tussen alle mogelijke opspannende bomen. Net als bij een spanning tree kunnen er ook veel mogelijke MST's voor een grafiek zijn.
Eigenschappen van een overspannende boom:
De opspannende boom houdt de onderstaande principes :
- Het aantal hoekpunten ( IN ) in de grafiek en de spanning tree is hetzelfde.
- Er is een vast aantal randen in de opspannende boom dat gelijk is aan één minder dan het totale aantal hoekpunten ( EN = V-1 ).
- De opspannende boom zou dat niet moeten zijn losgekoppeld , omdat er slechts één bron van componenten mag zijn, niet meer dan dat.
- De opspannende boom zou dat moeten zijn acyclisch, welke betekent dat er geen cyclus in de boom zou zijn.
- De totale kosten (of het gewicht) van de opspannende boom worden gedefinieerd als de som van de randgewichten van alle randen van de opspannende boom.
- Er kunnen veel mogelijke opspannende bomen voor een grafiek zijn.
Minimale spanningsboom:
A minimaal opspannende boom (MST) wordt gedefinieerd als een overspannende boom dat het minimale gewicht heeft van alle mogelijke opspannende bomen.
De minimaal opspannende boom heeft alle eigenschappen van een opspannende boom, met als extra beperking dat hij de minimaal mogelijke gewichten heeft tussen alle mogelijke opspannende bomen. Net als bij een spanning tree kunnen er ook veel mogelijke MST's voor een grafiek zijn.
- Laten we eens kijken naar de MST van de bovenstaande voorbeeldgrafiek,
Minimale spanningsboom
Algoritmen om de minimale spanningsboom te vinden:
Er zijn verschillende algoritmen om de minimaal opspannende boom uit een bepaalde grafiek te vinden. Enkele daarvan staan hieronder vermeld:
Kruskal's Minimum Spanning Tree-algoritme:
Dit is een van de populaire algoritmen voor het vinden van de minimaal opspannende boom uit een verbonden, ongerichte grafiek. Dit is een Eerst sorteert het alle randen van de grafiek op basis van hun gewicht,
Dit algoritme kan efficiënt worden geïmplementeerd met behulp van een DSU-gegevensstructuur (Disjoint-Set) om de verbonden componenten van de grafiek bij te houden. Dit wordt gebruikt in een verscheidenheid aan praktische toepassingen, zoals netwerkontwerp, clustering en data-analyse.
Volg het artikel op Kruskal's Minimum Spanning Tree-algoritme voor een beter begrip en implementatie van het algoritme.
Prim's Minimum Spanning Tree-algoritme:
Dit is ook een hebzuchtig algoritme. Dit algoritme heeft de volgende workflow:
- Het begint met het selecteren van een willekeurig hoekpunt en het vervolgens toevoegen aan de MST.
- Vervolgens controleert het herhaaldelijk op het minimale randgewicht dat een hoekpunt van MST verbindt met een ander hoekpunt dat zich nog niet in de MST bevindt.
- Dit proces wordt voortgezet totdat alle hoekpunten in de MST zijn opgenomen.
Om efficiënt de minimale gewichtsrand voor elke iteratie te selecteren, gebruikt dit algoritme prioriteit_wachtrij om de hoekpunten op te slaan, gesorteerd op hun huidige minimale randgewicht. Het houdt ook tegelijkertijd de MST bij met behulp van een array of een andere datastructuur die geschikt is gezien het datatype dat het opslaat.
Dit algoritme kan in verschillende scenario's worden gebruikt, zoals beeldsegmentatie op basis van kleur, textuur of andere kenmerken. Voor Routing, zoals het vinden van het kortste pad tussen twee punten dat een bestelwagen kan volgen.
Volg het artikel op Prim's Minimum Spanning Tree-algoritme voor een beter begrip en implementatie van dit algoritme.
array versus arraylijst
Boruvka's minimum spanningsboomalgoritme:
Dit is ook een algoritme voor het doorlopen van grafieken dat wordt gebruikt om de minimaal opspannende boom van een verbonden, ongerichte grafiek te vinden. Dit is een van de oudste algoritmen. Het algoritme werkt door iteratief de minimaal opspannende boom op te bouwen, te beginnen met elk hoekpunt in de grafiek als zijn eigen boom. In elke iteratie vindt het algoritme de goedkoopste rand die een boom met een andere boom verbindt, en voegt die rand toe aan de minimaal opspannende boom. Dit komt vrijwel overeen met het Prim-algoritme voor het vinden van de minimaal opspannende boom. Het algoritme heeft de volgende workflow:
- Initialiseer een bos met bomen, waarbij elk hoekpunt in de grafiek zijn eigen boom is.
- Voor elke boom in het bos:
- Zoek de goedkoopste rand die hem met een andere boom verbindt. Voeg deze randen toe aan de minimaal opspannende boom.
- Werk het bos bij door de bomen die met elkaar verbonden zijn door de toegevoegde randen samen te voegen.
- Herhaal de bovenstaande stappen totdat het bos slechts één boom bevat, wat de minimaal opspannende boom is.
Het algoritme kan worden geïmplementeerd met behulp van een datastructuur zoals een prioriteitswachtrij om efficiënt de goedkoopste rand tussen bomen te vinden. Het algoritme van Boruvka is een eenvoudig en gemakkelijk te implementeren algoritme voor het vinden van minimaal opspannende bomen, maar het is mogelijk niet zo efficiënt als andere algoritmen voor grote grafieken met veel randen.
Volg het artikel op Boruvka's minimum spanningsboomalgoritme voor een beter begrip en implementatie van dit algoritme.
Als u meer wilt weten over de eigenschappen en kenmerken van de Minimum Spanning Tree, klikt u op hier.
Toepassingen van minimaal overspannende bomen:
- Netwerk ontwerp : Spanningsbomen kunnen worden gebruikt bij netwerkontwerp om het minimumaantal verbindingen te vinden dat nodig is om alle knooppunten met elkaar te verbinden. Vooral minimaal opspannende bomen kunnen helpen de kosten van de verbindingen te minimaliseren door de goedkoopste randen te selecteren.
- Afbeelding verwerken : Overspannende bomen kunnen worden gebruikt bij beeldverwerking om gebieden met een vergelijkbare intensiteit of kleur te identificeren, wat handig kan zijn voor segmentatie- en classificatietaken.
- Biologie : Overspannende bomen en minimaal overspannende bomen kunnen in de biologie worden gebruikt om fylogenetische bomen te construeren om evolutionaire relaties tussen soorten of genen weer te geven.
- Analyse van sociale netwerken : Overspannende bomen en minimaal overspannende bomen kunnen worden gebruikt bij de analyse van sociale netwerken om belangrijke verbindingen en relaties tussen individuen of groepen te identificeren.
Enkele populaire interviewproblemen op MST
| 1. | Vind de minimale kosten om alle steden met elkaar te verbinden | Oefening |
Enkele veelgestelde vragen over bomen met een minimale spanning:
1. Kunnen er meerdere minimaal opspannende bomen zijn voor een bepaalde grafiek?
Ja, een grafiek kan meerdere minimaal opspannende bomen hebben als er meerdere sets randen zijn met hetzelfde minimale totale gewicht.
2. Kunnen het algoritme van Kruskal en het algoritme van Prim worden gebruikt voor gerichte grafieken?
Nee, het algoritme van Kruskal en het algoritme van Prim zijn alleen ontworpen voor ongerichte grafieken.
3. Kan een losgekoppelde graaf een minimaal opspannende boom hebben?
Nee, een losgekoppelde graaf kan geen opspannende boom hebben, omdat deze niet alle hoekpunten omvat. Daarom kan het ook geen minimaal opspannende boom hebben.
4. Kan een minimaal opspannende boom worden gevonden met behulp van het algoritme van Dijkstra?
Nee, het algoritme van Dijkstra wordt gebruikt om het kortste pad tussen twee hoekpunten in een gewogen grafiek te vinden. Het is niet ontworpen om een minimaal opspannende boom te vinden.
5. Wat is de tijdscomplexiteit van de algoritmen van Kruskal en Prim?
Zowel de algoritmen van Kruskal als Prim hebben een tijdscomplexiteit van O(ElogE) , waarbij E het aantal randen in de grafiek is.