minimum spanning tree tutorial
Denne C ++ -vejledning forklarer, hvad der er et Minimum Spanning Tree (MST) sammen med Prim og Kruskals algoritmer for at finde MST i en graf og dens applikationer:
Et spændende træ kan defineres som en delmængde af en graf, der består af alle hjørner, der dækker mindst mulige kanter og ikke har en cyklus. Spændende træ kan ikke frakobles.
Hver tilsluttet og ikke-rettet graf har mindst et spændende træ. En frakoblet graf har ikke et spændende træ, da det ikke er muligt at inkludere alle hjørner.
=> Se her for at udforske den komplette C ++ tutorials-liste.
Hvad du lærer:
Spændende træ i C ++
Overvej følgende tilsluttede graf.
Som vist ovenfor har vi for den givne tilsluttede graf indeholdende 3 hjørner tre spændende træer. Generelt, hvis N er antallet af noder i en graf, så har en komplet tilsluttet graf maksimalt NN-2antal spændende træer. Således har den i ovenstående graf N = 3 derfor 3(3-2)= 3 spændende træer.
Nogle af egenskaberne ved det spændende træ er anført nedenfor:
- En tilsluttet graf kan have mere end en spændende træ.
- Alle træer i en graf har det samme antal noder og kanter.
- Hvis vi fjerner en kant fra det spændende træ, bliver den minimalt forbundet og vil gøre grafen afbrudt.
- På den anden side vil tilføjelse af en kant til det spændende træ gøre det maksimalt acyklisk derved skabe en løkke.
- Et spændende træ har ikke en løkke eller en cyklus.
Hvad er et minimum spændende træ (MST)
Et minimum spændende træ er det, der indeholder mindst vægt blandt alle de andre spændende træer i en tilsluttet vægtet graf. Der kan være mere end ét minimum spændende træ til en graf.
Der er to mest populære algoritmer, der bruges til at finde det mindste spændende træ i en graf.
De omfatter:
- Kruskals algoritme
- Prims algoritme
Lad os diskutere begge disse algoritmer!
Kruskals algoritme
Kruskals algoritme er en algoritme til at finde MST i en tilsluttet graf.
Kruskals algoritme finder en delmængde af en graf G således, at:
- Det danner et træ med hvert toppunkt i det.
- Summen af vægtene er det mindste blandt alle de spændende træer, der kan dannes ud fra denne graf.
Sekvensen af trin for Kruskals algoritme gives som følger:
- Sorter først alle kanter fra den laveste vægt til den højeste.
- Tag kanten med den laveste vægt og tilføj den til det spændende træ. Hvis cyklen oprettes, skal du kassere kanten.
- Bliv ved med at tilføje kanter som i trin 1, indtil alle hjørner tages i betragtning.
Pseudokode til Kruskals algoritme
Nedenfor er pseudokoden for Kruskals algoritme
Lad os nu se illustrationen af Kruskals algoritme.
Nu vælger vi kanten med den mindste vægt, der er 2-4.
Vælg derefter den næste korteste kant 2-3.
Derefter vælger vi næste kant med den korteste kant, og det skaber ikke en cyklus, dvs. 0-3
bedste datagendannelsessoftware windows 10
Det næste trin er at vælge den korteste kant, så den ikke danner en cyklus. Dette er 0-1.
Som vi kan se, har vi dækket alle hjørnerne, og vi har et spændende træ med minimale omkostninger her.
Dernæst implementerer vi Kruskals algoritme ved hjælp af C ++.
#include #include #include using namespace std; #define graph_edge pair class Graph { private: int V; // number of nodes in graph vector> G; // vector for graph vector> T; // vector for mst int *parent; public: Graph(int V); void AddEdge(int u, int v, int wt); int find_set(int i); void union_set(int u, int v); void kruskal_algorithm(); void display_mst(); }; Graph::Graph(int V) { parent = new int(V); for (int i = 0; i Produktion:
Minimum Spanning Tree (MST) ifølge Kruskals algoritme:
Kant: Vægt
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Bemærk, at vi har brugt den samme eksempeldiagram i programmet, som vi har brugt i illustrationen af Kruskals algoritme ovenfor. I denne implementering bruger vi to vektorer; en til at gemme graf og en anden for at gemme det mindst mulige spændende træ. Vi finder rekursivt kanterne med mindst vægt og tilføjer dem til MST-vektoren, indtil alle hjørner er dækket.
Prims algoritme
Prims algoritme er endnu en algoritme til at finde det minimum, der spænder over en graf. I modsætning til Kruskals algoritme, der starter med grafkanter, starter Prims algoritme med et toppunkt. Vi starter med et toppunkt og fortsætter med at tilføje kanter med mindst vægt, indtil alle hjørner er dækket.
Sekvensen af trin for Prims algoritme er som følger:
- Vælg et tilfældigt toppunkt som startpunkt, og initialiser et minimumspændende træ.
- Find de kanter, der forbinder med andre hjørner. Find kanten med den mindste vægt og tilføj den til det spændende træ.
- Gentag trin 2, indtil det spændende træ er opnået.
Pseudokode til Prims algoritme
Lad os nu se en illustration af Prims algoritme.
Til dette bruger vi det samme eksempelgraf, som vi brugte i illustrationen af Kruskals algoritme.
Lad os vælge node 2 som tilfældig toppunkt.
Dernæst vælger vi kanten med mindst vægt fra 2. Vi vælger kant 2-4.
Dernæst vælger vi et andet toppunkt, der endnu ikke er i det spændende træ. Vi vælger kanten 2-3.
Lad os nu vælge en kant med mindst vægt fra ovenstående hjørner. Vi har kant 3-0, som har mindst vægt.
Dernæst vælger vi en kant med mindst vægt fra toppunkt 0. Dette er kanten 0-1.
Fra ovenstående figur ser vi, at vi nu har dækket alle hjørnerne i grafen og opnået et komplet spændende træ med minimale omkostninger.
Lad os nu implementere Prims algoritme i C ++.
Bemærk, at vi også i dette program har brugt ovenstående eksempeldiagram som input, så vi kan sammenligne output givet af programmet sammen med illustrationen.
Programmet er angivet nedenfor:
#include #include using namespace std; #define INF 9999 // graph contains 5 vertices #define V 5 // an array G that stores adjacency matrix for input graph int G(V)(V) = { {0, 3, 0, 3, 0}, {3, 0, 0, 0, 4}, {0, 0, 0, 2, 1}, {3, 3, 2, 0, 0}, {0, 4, 1, 0, 0}}; int main () { int num_edge; // number of edge // mst_vertex - array to track vertices selected for spanning tree int mst_vertex(V); // set selected false initially memset (mst_vertex, false, sizeof (mst_vertex)); // set number of edge to 0 num_edge = 0; //let 0th vertex be the first to be selected mst_vertex(0) = true; int x; // row int y; // col // print details of MST cout<<'The Minimum Spanning Tree as per Prim's Algorithm:'< G(i)(j)) { min = G(i)(j); x = i; y = j; } } } } } cout << x << ' - ' << y << ' : ' << G(x)(y); cout << endl; mst_vertex(y) = true; num_edge++; } return 0; } Produktion:
Det mindst spændende træ i henhold til Prims algoritme:
Kant: Vægt
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Anvendelser af spændende træ
Nogle af anvendelserne af minimum spændende træer er som følger:
# 1) Opsætning af kommunikationsnetværk: Når vi ønsker at oprette et kommunikationsnetværk ved hjælp af kommunikationslink, bestemmes omkostningerne ved opsætning af kommunikationslink mellem to punkter bedst ved hjælp af en MST.
# 2) Klyngeanalyse: Det kan bruges til at løse K-klyngeproblemet ved at finde et minimum spændende træ og slette de k-1 dyreste kanter.
# 3) Udlægning af vej- / jernbanenet: Når vi lægger forskellige vej- eller jernbanenet mellem eller inden for byer, er projektomkostningerne en meget vigtig faktor. Vi kan finde den bedste vej med minimale omkostninger ved hjælp af minimum træer.
# 4) Planlægning af boligfaciliteter: Faciliteter som elektricitet, vand, spildevand osv., Der skal leveres til et antal huse, skal også have de bedste omkostninger, og dette gøres ved hjælp af en MST.
# 5) Løsning af den rejsende sælgerproblem: Vi kan bruge en MST til at løse det rejsende sælgerproblem, som kræver at besøge hvert punkt mindst en gang.
Konklusion
Det mindste spændende træ er delmængden af grafen g, og denne delmængde har alle hjørnerne i grafen, og de samlede omkostninger ved kanter, der forbinder hjørnerne, er minimale.
Vi diskuterede to algoritmer, dvs. Kruskal og Prim's, for at finde det mindste spændende træ fra grafen. Anvendelserne af det spændende træ blev også forklaret her i denne vejledning.
=> Tjek de bedste C ++ træningsvejledninger her.
Anbefalet læsning
- Java Reflection Tutorial med eksempler
- B Tree og B + Tree Datastruktur i C ++
- Python DateTime-tutorial med eksempler
- Bugzilla Tutorial: Defect Management Tool Hands-on Tutorial
- Datastruktur for binært træ i C ++
- 20+ MongoDB-vejledning til begyndere: Gratis MongoDB-kursus
- MongoDB Sharding Tutorial med eksempel
- MongoDB Opret databasevejledning
