minimum spanning tree tutorial
Deze C ++ Tutorial legt uit wat een Minimum Spanning Tree (MST) is, samen met de algoritmen van Prim en Kruskal om MST in een grafiek en zijn toepassingen te vinden:
Een overspanningsboom kan worden gedefinieerd als een subset van een graaf, die bestaat uit alle hoekpunten die zo min mogelijk randen bedekken en geen cyclus heeft. Spanning tree kan niet worden losgekoppeld.
Elke verbonden en niet-gerichte graaf heeft ten minste één spanning tree. Een losgekoppelde graaf heeft geen spanning tree omdat het niet mogelijk is om alle hoekpunten op te nemen.
Zie hier om de volledige lijst met C ++ - zelfstudies te verkennen.
Wat je leert:
Boom overspannen in C ++
Beschouw de volgende verbonden grafiek.
Zoals hierboven getoond, hebben we voor de gegeven verbonden grafiek met 3 hoekpunten drie opspannende bomen. In het algemeen, als N het aantal knooppunten in een grafiek is, dan heeft een volledig verbonden grafiek maximaal NN-2aantal opspannende bomen. Dus in de bovenstaande grafiek N = 3, daarom heeft het 3(3-2)= 3 opspannende bomen.
Enkele van de eigenschappen van de spanning tree worden hieronder opgesomd:
- Een verbonden graaf kan meer dan één opspannende boom hebben.
- Alle opspannende bomen in een grafiek hebben hetzelfde aantal knooppunten en randen.
- Als we één rand van de opspannende boom verwijderen, wordt het minimaal aangesloten en zal de grafiek loskoppelen.
- Aan de andere kant zal het toevoegen van een rand aan de opspannende boom het maken maximaal acyclisch waardoor er een lus ontstaat.
- Een opspannende boom heeft geen lus of cyclus.
Wat is een Minimum Spanning Tree (MST)
Een minimale spanning tree is degene die het minste gewicht bevat tussen alle andere spanning trees van een verbonden gewogen graaf. Er kan meer dan één minimale spanning tree voor een graaf zijn.
Er zijn twee meest populaire algoritmen die worden gebruikt om de minimale spanning tree in een grafiek te vinden.
Ze bevatten:
- Het algoritme van Kruskal
- Prim's algoritme
Laten we beide algoritmen bespreken!
Het algoritme van Kruskal
Het algoritme van Kruskal is een algoritme om de MST in een verbonden grafiek te vinden.
Het algoritme van Kruskal vindt een subset van een grafiek G zodat:
- Het vormt een boom met elk hoekpunt erin.
- De som van de gewichten is het minimum van alle opspannende bomen die uit deze grafiek kunnen worden gevormd.
De volgorde van de stappen voor het algoritme van Kruskal wordt als volgt weergegeven:
- Sorteer eerst alle randen van het laagste gewicht naar het hoogste.
- Neem de rand met het laagste gewicht en voeg deze toe aan de opspannende boom. Als de cyclus is gemaakt, gooit u de rand weg.
- Blijf randen toevoegen zoals in stap 1 totdat alle hoekpunten zijn overwogen.
Pseudocode voor het algoritme van Kruskal
Hieronder staat de pseudo-code voor het algoritme van Kruskal
Laten we nu eens kijken naar de illustratie van het algoritme van Kruskal.
Nu kiezen we de rand met het minste gewicht, namelijk 2-4.
Kies vervolgens de volgende kortste rand 2-3.
Dan kiezen we volgende snede met de kortste snede en dat levert geen cyclus op, d.w.z. 0-3
applicaties om video's van youtube te downloaden
De volgende stap is om de kortste rand te kiezen, zodat deze geen cyclus vormt. Dit is 0-1.
Zoals we kunnen zien, hebben we alle hoekpunten gedekt en hebben we hier een opspannende boom met minimale kosten.
Vervolgens zullen we het algoritme van Kruskal implementeren met C ++.
Uitgang:
De Minimum Spanning Tree (MST) volgens het algoritme van Kruskal:
Rand: gewicht
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Merk op dat we dezelfde voorbeeldgrafiek in het programma hebben gebruikt als in de illustratie van het algoritme van Kruskal hierboven. Bij deze implementatie maken we gebruik van twee vectoren; één om de grafiek op te slaan en een andere om de minimale spanning tree op te slaan. We zoeken recursief de randen met het minste gewicht en voegen ze toe aan de MST-vector totdat alle hoekpunten bedekt zijn.
Prim's algoritme
Het algoritme van Prim is nog een ander algoritme om het minimum te vinden dat de boomstructuur van een grafiek overspant. In tegenstelling tot het algoritme van Kruskal dat begint met grafiekranden, begint het algoritme van Prim met een hoekpunt. We beginnen met één hoekpunt en blijven randen met het minste gewicht toevoegen totdat alle hoekpunten bedekt zijn.
De stappenreeks voor het algoritme van Prim is als volgt:
- Kies een willekeurig hoekpunt als startpunt en initialiseer een minimale spanning tree.
- Zoek de randen die aansluiten op andere hoekpunten. Zoek de rand met minimaal gewicht en voeg deze toe aan de opspannende boom.
- Herhaal stap 2 totdat de opspannende boom is verkregen.
Pseudocode voor het algoritme van Prim
Laten we nu een illustratie bekijken van het algoritme van Prim.
Hiervoor gebruiken we dezelfde voorbeeldgrafiek die we hebben gebruikt in de illustratie van het algoritme van Kruskal.
Laten we knooppunt 2 selecteren als het willekeurige hoekpunt.
Vervolgens selecteren we de rand met het minste gewicht van 2. We kiezen rand 2-4.
Vervolgens kiezen we een ander hoekpunt dat nog niet in de opspannende boom staat. We kiezen voor de rand 2-3.
Laten we nu een rand met het minste gewicht selecteren uit de bovenstaande hoekpunten. We hebben rand 3-0 die het minste gewicht heeft.
Vervolgens kiezen we een rand met het minste gewicht vanaf hoekpunt 0. Dit is de rand 0-1.
Uit de bovenstaande figuur zien we dat we nu alle hoekpunten in de grafiek hebben bestreken en een complete spanning tree hebben verkregen met minimale kosten.
Laten we nu het algoritme van de Prim in C ++ implementeren.
Merk op dat we ook in dit programma de bovenstaande voorbeeldgrafiek als invoer hebben gebruikt, zodat we de uitvoer van het programma samen met de illustratie kunnen vergelijken.
Het programma is hieronder weergegeven:
Uitgang:
De minimale overspanningsboom volgens het algoritme van Prim:
Rand: gewicht
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Toepassingen van Spanning Tree
Enkele van de toepassingen van Minimum Spanning Trees zijn als volgt:
# 1) Communicatie Netwerk instellen: Als we een communicatienetwerk willen opzetten met communicatieverbindingen, dan kunnen de kosten voor het opzetten van communicatieverbindingen tussen twee punten het beste worden bepaald met behulp van een MST.
# 2) Clusteranalyse: Het kan worden gebruikt om het K-clusteringprobleem op te lossen door een minimale spanning tree te vinden en de k-1 duurste randen te verwijderen.
# 3) Weg- / spoorwegnetwerken aanleggen: Wanneer we verschillende wegen- of spoornetten tussen of binnen steden leggen, zijn de kosten van het project een zeer belangrijke factor. We kunnen het beste pad vinden met minimale kosten met minimale opspannende bomen.
# 4) Planning van huisvestingsfaciliteiten: Ook voorzieningen als elektriciteit, water, riolering etc. die aan een aantal huizen geleverd moeten worden, moeten tegen een optimale kostprijs zijn en dit gebeurt met behulp van een MST.
# 5) Het probleem van de handelsreiziger oplossen: We kunnen een MST gebruiken om het handelsreizigersprobleem op te lossen, waarbij elk punt minstens één keer moet worden bezocht.
Gevolgtrekking
De minimale spanning tree is de subset van graaf g en deze subset heeft alle hoekpunten van de graaf en de totale kosten van de randen die de hoekpunten verbinden zijn minimaal.
We hebben twee algoritmen besproken, namelijk Kruskal's en Prim's, om de minimale spanning tree uit de grafiek te vinden. De toepassingen van de spanning tree werden hier in deze tutorial ook uitgelegd.
Bekijk hier de beste C ++ trainingshandleidingen.
Aanbevolen literatuur
- Zelfstudie over reflectie in Java met voorbeelden
- B Tree en B + Tree gegevensstructuur in C ++
- Python DateTime-zelfstudie met voorbeelden
- Bugzilla-zelfstudie: Praktische zelfstudie met hulpprogramma voor defectbeheer
- Binaire boomgegevensstructuur in C ++
- 20+ MongoDB-zelfstudie voor beginners: gratis MongoDB-cursus
- MongoDB Sharding-zelfstudie met voorbeeld
- MongoDB Create Database-zelfstudie