minimum spanning tree tutorial
Denna C ++ -handledning förklarar vad som är ett minimalt spanande träd (MST) tillsammans med Prim och Kruskals algoritmer för att hitta MST i en graf och dess tillämpningar:
Ett spännande träd kan definieras som en delmängd av ett diagram, som består av alla hörn som täcker minsta möjliga kanter och inte har en cykel. Spännande träd kan inte kopplas bort.
Varje ansluten och opriktad graf har minst ett spännande träd. En urkopplad graf har inte ett spännande träd eftersom det inte är möjligt att inkludera alla hörn.
=> Se här för att utforska listan med fullständiga C ++ -studier.
Vad du kommer att lära dig:
Spännande träd i C ++
Tänk på följande anslutna diagram.
Som visat ovan, för den givna anslutna grafen som innehåller tre hörn, har vi tre spännande träd. I allmänhet, om N är antalet noder i ett diagram, har en fullständigt ansluten graf maximalt NN-2antal spännande träd. Således har den i ovanstående diagram N = 3 därför 3(3-2)= 3 spännande träd.
Några av egenskaperna hos det spännande trädet listas nedan:
- En ansluten graf kan ha mer än ett träd.
- Alla spännande träd i ett diagram har samma antal noder och kanter.
- Om vi tar bort en kant från det spännande trädet blir det minimalt ansluten och kommer att göra grafen frånkopplad.
- Å andra sidan kommer det att läggas till en kant i det spännande trädet maximalt acyklisk därigenom skapa en slinga.
- Ett spännande träd har inte en slinga eller en cykel.
Vad är ett minsta spännande träd (MST)
Ett minimalt spännande träd är det som innehåller minst vikt bland alla andra spännande träd i en ansluten viktad graf. Det kan finnas mer än ett minsta spännande träd för ett diagram.
Det finns två mest populära algoritmer som används för att hitta det minsta spännande trädet i en graf.
De inkluderar:
- Kruskals algoritm
- Prims algoritm
Låt oss diskutera båda dessa algoritmer!
Kruskals algoritm
Kruskals algoritm är en algoritm för att hitta MST i en ansluten graf.
Kruskals algoritm hittar en delmängd av ett diagram G så att:
- Det bildar ett träd med varje toppunkt i det.
- Summan av vikterna är minsta bland alla spännande träd som kan bildas från denna graf.
Stegsekvensen för Kruskals algoritm ges enligt följande:
- Sortera först alla kanter från lägsta vikt till högsta.
- Ta kanten med den lägsta vikten och lägg den till det spännande trädet. Kassera kanten om cykeln skapas.
- Fortsätt lägga till kanter som i steg 1 tills alla hörn beaktas.
Pseudokod för Kruskals algoritm
Nedan följer pseudokoden för Kruskals algoritm
Låt oss nu se illustrationen av Kruskals algoritm.
Nu väljer vi kanten med minst vikt som är 2-4.
Välj sedan nästa kortaste kant 2-3.
Sedan väljer vi nästa kant med den kortaste kanten och det skapar inte en cykel dvs 0-3
vad är ett datoroperativsystem
Nästa steg är att välja den kortaste kanten så att den inte bildar en cykel. Det här är 0-1.
Som vi kan se har vi täckt alla hörn och vi har ett spännande träd med lägsta kostnad här.
Därefter implementerar vi Kruskals algoritm med 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) enligt Kruskals algoritm:
Kant: Vikt
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Observera att vi har använt samma exempeldiagram i programmet som vi har använt i illustrationen av Kruskals algoritm ovan. I denna implementering använder vi två vektorer; en för att lagra diagram och en annan för att lagra det minsta spännande trädet. Vi hittar rekursivt kanterna med minst vikt och lägger till dem i MST-vektorn tills alla hörn är täckta.
Prim's Algorithm
Prims algoritm är ännu en algoritm för att hitta det minsta som spänner över trädet i en graf. Till skillnad från Kruskals algoritm som börjar med grafkanter, börjar Prims algoritm med ett toppunkt. Vi börjar med en topp och fortsätter att lägga till kanter med minst vikt tills alla topparna är täckta.
Stegsekvensen för Prims algoritm är som följer:
- Välj ett slumpmässigt topp som startpunkt och initialisera ett minimalt spännande träd.
- Hitta kanterna som ansluter till andra hörn. Hitta kanten med minsta vikt och lägg till den i det spännande trädet.
- Upprepa steg 2 tills det spännande trädet erhålls.
Pseudokod för Prims algoritm
Låt oss nu se en illustration för Prims algoritm.
För detta använder vi samma exempeldiagram som vi använde i illustrationen av Kruskals algoritm.
Låt oss välja nod 2 som slumpmässigt toppunkt.
Därefter väljer vi kanten med minst vikt från 2. Vi väljer kant 2-4.
Därefter väljer vi ett annat toppunkt som ännu inte finns i det spännande trädet. Vi väljer kanten 2-3.
Låt oss nu välja en kant med minst vikt från ovanstående hörn. Vi har kant 3-0 som har minst vikt.
Därefter väljer vi en kant med minsta vikt från vertex 0. Detta är kanten 0-1.
Från ovanstående figur ser vi att vi nu har täckt alla hörn i diagrammet och fått ett komplett spännande träd med lägsta kostnad.
Låt oss nu implementera Prims algoritm i C ++.
Observera att även i det här programmet har vi använt ovanstående diagram som ingång så att vi kan jämföra utmatningen från programmet tillsammans med illustrationen.
Programmet ges nedan:
#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:
Minsta spännande träd enligt Prims algoritm:
Kant: Vikt
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Tillämpningar av spännande träd
Några av tillämpningarna av minimisparande träd är som följer:
# 1) Inställningar för kommunikationsnätverk: När vi vill skapa ett kommunikationsnätverk med kommunikationslänkar bestäms kostnaden för att skapa kommunikationslänkar mellan två punkter bäst med hjälp av en MST.
# 2) Klusteranalys: Det kan användas för att lösa K-klusterproblemet genom att hitta ett minimum som spänner över träd och ta bort de k-1 dyraste kanterna.
# 3) Anläggning av väg- / järnvägsnät: När vi lägger olika väg- eller järnvägsnät mellan eller inom städer är kostnaden för projektet en mycket viktig faktor. Vi kan hitta den bästa vägen till lägsta kostnad med hjälp av minimala spännande träd.
# 4) Planera bostadsanläggningar: Anläggningar som el, vatten, avlopp etc. som ska tillhandahållas till ett antal hus kräver också att de kostar optimalt och detta görs med en MST.
# 5) Lösa problemet med den resande säljaren: Vi kan använda en MST för att lösa det resande säljarproblemet som kräver att man besöker varje punkt minst en gång.
Slutsats
Det minsta spännande trädet är delmängden av diagrammet g och denna delmängd har alla kurvorna i diagrammet och den totala kostnaden för kanterna som förbinder topparna är minimal.
Vi diskuterade två algoritmer, dvs Kruskal och Prim, för att hitta det minsta spännande trädet från diagrammet. Tillämpningarna på det spännande trädet förklarades också här i denna handledning.
=> Kolla in de bästa C ++ träningsövningarna här.
Rekommenderad läsning
- Java Reflection Tutorial med exempel
- B Tree och B + Tree Datastruktur i C ++
- Python DateTime-handledning med exempel
- Bugzilla Tutorial: Defect Management Tool Praktisk handledning
- Datastruktur för binärt träd i C ++
- 20+ MongoDB-handledning för nybörjare: Gratis MongoDB-kurs
- MongoDB Sharding Tutorial med exempel
- MongoDB Skapa databashandledning
