minimum spanning tree tutorial
Denne C ++ opplæringen forklarer hva som er et Minimum Spanning Tree (MST) sammen med Prim og Kruskals algoritmer for å finne MST i en graf og dens applikasjoner:
Et spennende tre kan defineres som en delmengde av en graf, som består av alle toppunktene som dekker minimum mulige kanter og ikke har en syklus. Spennende tre kan ikke kobles fra.
Hver koblet og ikke-rettet graf har minst ett spennende tre. En frakoblet graf har ikke et spennende tre, da det ikke er mulig å inkludere alle hjørner.
=> Se her for å utforske hele C ++ opplæringslisten.
Hva du vil lære:
Spennende tre i C ++
Tenk på følgende tilkoblede graf.
Som vist ovenfor, for den gitte tilkoblede grafen som inneholder 3 hjørner, har vi tre spennende trær. Generelt, hvis N er antall noder i en graf, så har en komplett tilkoblet graf maksimalt NN-2antall spennende trær. I den ovennevnte grafen N = 3 har den altså 3(3-2)= 3 spennende trær.
Noen av egenskapene til det spennende treet er listet opp nedenfor:
- En tilkoblet graf kan ha mer enn en som spenner over trær.
- Alle spennende trær i en graf har samme antall noder og kanter.
- Hvis vi fjerner den ene kanten fra det spennende treet, blir den minimalt tilkoblet og vil gjøre grafen frakoblet.
- På den annen side vil du legge den ene kanten til det spennende treet maksimalt syklisk og derved skape en løkke.
- Et spennende tre har ikke en løkke eller en syklus.
Hva er et minimum spaning tree (MST)
Et minimum spennende tre er det som inneholder minst vekt blant alle de andre spennende trærne i en tilkoblet vektet graf. Det kan være mer enn ett minimumspennende tre for en graf.
Det er to mest populære algoritmer som brukes til å finne det minste spennende treet i en graf.
De inkluderer:
- Kruskals algoritme
- Prims algoritme
La oss diskutere begge disse algoritmene!
Kruskals algoritme
Kruskals algoritme er en algoritme for å finne MST i en tilkoblet graf.
Kruskals algoritme finner en delmengde av en graf G slik at:
- Det danner et tre med hvert toppunkt i det.
- Summen av vektene er minimum blant alle de spennende trærne som kan dannes fra denne grafen.
Trinnrekkefølgen for Kruskals algoritme er gitt som følger:
- Først sorterer du alle kantene fra laveste vekt til høyeste.
- Ta kanten med den laveste vekten og legg den til det spennende treet. Hvis syklusen er opprettet, kast kanten.
- Fortsett å legge til kanter som i trinn 1 til alle toppunktene blir vurdert.
Pseudokode for Kruskals algoritme
Nedenfor er pseudokoden for Kruskals algoritme
La oss nå se illustrasjonen av Kruskals algoritme.
Nå velger vi kanten med minst vekt som er 2-4.
Velg deretter neste korteste kant 2-3.
Deretter velger vi neste kant med korteste kant, og det skaper ikke en syklus dvs. 0-3
hva er et datamaskinsystem
Neste trinn er å velge den korteste kanten slik at den ikke danner en syklus. Dette er 0-1.
Som vi kan se, har vi dekket alle toppunktene, og vi har et spennende tre med minimumskostnad her.
Deretter vil vi implementere Kruskals algoritme ved hjelp av 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 Produksjon:
Minimum Spanning Tree (MST) i henhold til Kruskals algoritme:
Kant: Vekt
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Vær oppmerksom på at vi har brukt samme eksempelgraf i programmet som vi har brukt i illustrasjonen av Kruskals algoritme ovenfor. I denne implementeringen bruker vi to vektorer; en for å lagre graf og en annen for å lagre minimum spennende tre. Vi finner rekursivt kantene med minst vekt og legger dem til MST-vektoren til alle toppunktene er dekket.
Prim’s Algorithm
Prims algoritme er nok en algoritme for å finne minimum som spenner over treet i en graf. I motsetning til Kruskals algoritme som starter med grafkanter, begynner Prims algoritme med et toppunkt. Vi starter med ett toppunkt og fortsetter å legge til kanter med minst vekt til alle toppunktene er dekket.
Trinnrekkefølgen for Prims algoritme er som følger:
- Velg et tilfeldig toppunkt som startpunkt, og initialiser et minimumspennende tre.
- Finn kantene som kobles til andre hjørner. Finn kanten med minimum vekt og legg den til det spennende treet.
- Gjenta trinn 2 til det spennende treet er oppnådd.
Pseudokode for Prims algoritme
La oss nå se en illustrasjon for Prims algoritme.
For dette bruker vi den samme eksempelgrafen som vi brukte i Illustrasjonen av Kruskals algoritme.
La oss velge node 2 som tilfeldig toppunkt.
Deretter velger vi kanten med minst vekt fra 2. Vi velger kant 2-4.
Deretter velger vi et annet toppunkt som ikke er i det spennende treet ennå. Vi velger kanten 2-3.
La oss nå velge en kant med minst vekt fra de ovennevnte toppunktene. Vi har kant 3-0 som har minst vekt.
Deretter velger vi en kant med minst vekt fra toppunkt 0. Dette er kanten 0-1.
Fra figuren ovenfor ser vi at vi nå har dekket alle toppunktene i grafen og fått et komplett spennende tre med minimal kostnad.
La oss nå implementere Prims algoritme i C ++.
Vær oppmerksom på at også i dette programmet har vi brukt eksemplet ovenfor som inndata, slik at vi kan sammenligne utdata gitt av programmet sammen med illustrasjonen.
Programmet er gitt 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; } Produksjon:
Minimum Spanning Tree i henhold til Prims algoritme:
Kant: Vekt
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Anvendelser av spennende tre
Noen av applikasjonene til Minimum Spanning Trees er som følger:
# 1) Oppsett av kommunikasjonsnettverk: Når vi ønsker å sette opp et kommunikasjonsnettverk ved hjelp av kommunikasjonskoblinger, bestemmes best kostnaden for å sette opp kommunikasjonskoblinger mellom to punkter ved hjelp av en MST.
# 2) Klyngeanalyse: Den kan brukes til å løse K-klyngeproblemet ved å finne et minimumspennende tre og slette de dyreste kantene på k-1.
# 3) Legge ut vei- / jernbanenett: Når vi legger forskjellige vei- eller jernbanenett mellom eller i byene, er kostnadene for prosjektet en veldig viktig faktor. Vi kan finne den beste banen med minimumskostnader ved å bruke minimum trær.
# 4) Planlegging av boligfasiliteter: Fasiliteter som elektrisitet, vann, avløp osv. Som skal leveres til en rekke hus, må også ha de beste kostnadene, og dette gjøres ved hjelp av en MST.
# 5) Løse problemet med den omreisende selgeren: Vi kan bruke en MST til å løse det reisende selgerproblemet som krever å besøke hvert punkt minst en gang.
Konklusjon
Det minste spennende treet er delsett av graf g, og dette delsettet har alle hjørnene i grafen, og den totale kostnaden for kanter som forbinder hjørnene er minimal.
Vi diskuterte to algoritmer, dvs. Kruskal og Prim's, for å finne det minste spennet fra grafen. Bruken av det spennende treet ble også forklart her i denne opplæringen.
=> Sjekk ut de beste C ++ opplæringsveiledningene her.
Anbefalt lesing
- 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 tre i C ++
- 20+ MongoDB-opplæring for nybegynnere: Gratis MongoDB-kurs
- MongoDB Sharding Tutorial med eksempel
- MongoDB Opprette databaseopplæring
