minimum spanning tree tutorial
Tento výukový program C ++ vysvetľuje, čo je minimálny rozpätie stromu (MST) spolu s algoritmami Prim a Kruskal na vyhľadanie MST v grafe a jeho aplikácie:
Spanning tree možno definovať ako podmnožinu grafu, ktorý sa skladá zo všetkých vrcholov pokrývajúcich minimálne možné hrany a nemá cyklus. Rozpätný strom nie je možné odpojiť.
Každý prepojený a neusmernený graf má najmenej jeden spanning tree. Odpojený graf nemá kostru, pretože nie je možné zahrnúť všetky vrcholy.
=> Ak chcete preskúmať celý zoznam výukových programov C ++, prečítajte si tu.
Čo sa dozviete:
Spanning Tree v C ++
Zvážte nasledujúci pripojený graf.
Ako je uvedené vyššie, pre daný pripojený Graf obsahujúci 3 vrcholy máme tri rozložené stromy. Všeobecne platí, že ak N je počet uzlov v grafe, potom má úplný pripojený graf maximum NN-2počet spanningových stromov. Vo vyššie uvedenom grafe teda N = 3, má teda 3(3-2)= 3 kleniace sa stromy.
Niektoré z vlastností spanning tree sú uvedené nižšie:
- Pripojený graf môže mať viac ako jeden spanning trees.
- Všetky stromy v grafe majú rovnaký počet uzlov a hrán.
- Ak odstránime jednu hranu z kostry, stane sa minimálne spojené a spôsobí odpojenie grafu.
- Na druhej strane, pridanie jedného okraja k spanningovému stromu to urobí maximálne acyklický čím sa vytvorí slučka.
- Rozponový strom nemá slučku ani cyklus.
Čo je minimálny rozpätie stromu (MST)
Minimálny spanning tree je ten, ktorý obsahuje najmenšiu váhu zo všetkých ostatných spanning stromu pripojeného váženého grafu. Pre graf môže existovať viac ako jeden minimálny spanning tree.
Existujú dva najobľúbenejšie algoritmy, ktoré sa používajú na vyhľadanie minimálneho rozsahu v grafe.
Zahŕňajú:
- Kruskalov algoritmus
- Primov algoritmus
Poďme diskutovať o oboch týchto algoritmoch!
Kruskalov algoritmus
Kruskalov algoritmus je algoritmus na vyhľadanie MST v pripojenom grafe.
Kruskalov algoritmus nájde podmnožinu grafu G tak, že:
- Tvorí strom s každým vrcholom.
- Súčet váh je minimálny medzi všetkými spanningovými stromami, ktoré je možné vytvoriť z tohto grafu.
Postupnosť krokov Kruskalovho algoritmu je uvedená nasledovne:
- Najskôr roztriedte všetky hrany od najnižšej po najvyššiu hmotnosť.
- Choďte na hranu s najmenšou hmotnosťou a pridajte ju do kostry. Ak je cyklus vytvorený, okraj zahoďte.
- Stále pridávajte hrany ako v kroku 1, kým sa nezohľadnia všetky vrcholy.
Pseudokód pre Kruskalov algoritmus
Ďalej je uvedený pseudokód Kruskalovho algoritmu
Teraz sa pozrime na ilustráciu Kruskalovho algoritmu.
Teraz vyberieme hranu s najmenšou hmotnosťou, ktorá je 2-4.
Ďalej vyberte nasledujúcu najkratšiu hranu 2 - 3.
Potom zvolíme ďalšiu hranu s najkratšou hranou, ktorá nevytvára cyklus, tj. 0-3
implementácia dijkstraovho algoritmu v jave
Ďalším krokom je výber najkratšej hrany, aby netvorila cyklus. Toto je 0: 1.
Ako vidíme, pokryli sme všetky vrcholy a máme tu spankový strom s minimálnymi nákladmi.
Ďalej implementujeme Kruskalov algoritmus pomocou 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 Výkon:
Minimum Spanning Tree (MST) podľa Kruskalovho algoritmu:
Hrana: Hmotnosť
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Upozorňujeme, že v programe sme použili rovnaký vzorový graf, aký sme použili pri ilustrácii Kruskalovho algoritmu vyššie. V tejto implementácii využívame dva vektory; jeden na uloženie grafu a druhý na uloženie minimálneho rozsahu stromu. Rekurzívne nájdeme hrany s najmenšou váhou a pridáme ich do vektora MST, kým nebudú pokryté všetky vrcholy.
Primov algoritmus
Primov algoritmus je ďalším algoritmom na vyhľadanie minima, ktoré sa nachádza v strome grafu. Na rozdiel od Kruskalovho algoritmu, ktorý začína okrajmi grafu, Primov algoritmus začína vrcholom. Začíname s jedným vrcholom a neprestávame pridávať hrany s najmenšou hmotnosťou, kým nie sú zakryté všetky vrcholy.
Postupnosť krokov pre Primov algoritmus je nasledovná:
- Vyberte náhodný vrchol ako začiatočný vrchol a inicializujte minimálny rozsah stromu.
- Nájdite hrany, ktoré sa pripájajú k iným vrcholom. Nájdite hranu s minimálnou hmotnosťou a pridajte ju do kostry.
- Opakujte krok 2, kým sa nezíska kostrový strom.
Pseudokód pre Primov algoritmus
Teraz sa pozrime na ilustráciu Primovho algoritmu.
Na tento účel používame rovnaký príkladný graf, ktorý sme použili v ilustrácii Kruskalovho algoritmu.
Vyberme uzol 2 ako náhodný vrchol.
Ďalej vyberieme hranu s najmenšou hmotnosťou z 2. Vyberieme hranu 2-4.
Ďalej vyberieme ďalší vrchol, ktorý sa ešte nenachádza v spanning tree. Vyberieme okraj 2-3.
Teraz z vyššie uvedených vrcholov vyberte hranu s najmenšou hmotnosťou. Máme hranu 3: 0, ktorá má najmenšiu váhu.
Ďalej vyberieme hranu s najmenšou váhou z vrcholu 0. Toto je hrana 0-1.
Z vyššie uvedeného obrázku vidíme, že sme teraz pokryli všetky vrcholy v grafe a získali sme kompletný spanning strom s minimálnymi nákladmi.
Teraz implementujme Primov algoritmus v C ++.
Všimnite si, že aj v tomto programe sme ako vstup použili vyššie uvedený príkladový graf, aby sme mohli porovnať výstup poskytnutý programom spolu s ilustráciou.
Program je uvedený nižšie:
#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; }
Výkon:
Minimum Spanning Tree podľa Algoritmu Prim:
Hrana: Hmotnosť
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Aplikácie Spanning Tree
Niektoré z aplikácií minimálneho rozpätia stromov sú tieto:
# 1) Nastavenie komunikačnej siete: Keď chceme zriadiť komunikačnú sieť pomocou komunikačných spojení, potom sa náklady na nastavenie komunikačných spojení medzi dvoma bodmi najlepšie určia pomocou MST.
# 2) Klastrová analýza: Môže sa použiť na vyriešenie problému s klastrovaním K nájdením minimálneho rozsahu stromu a odstránením najdrahších hrán k-1.
# 3) Rozloženie cestných a železničných sietí: Keď položíme rôzne cestné alebo železničné siete medzi mestami alebo v rámci nich, náklady na projekt sú veľmi dôležitým faktorom. Môžeme nájsť najlepšiu cestu s minimálnymi nákladmi pomocou minimálnych spanningových stromov.
# 4) Plánovanie bytových zariadení: Zariadenia ako elektrina, voda, kanalizácia atď., Ktoré majú byť poskytované viacerým domom, si tiež musia vyžadovať optimálnu cenu, a to pomocou MST.
# 5) Riešenie problému s cestujúcim predavačom: Pomocou MST môžeme vyriešiť problém obchodného cestujúceho, ktorý vyžaduje navštíviť každý bod aspoň raz.
Záver
Minimálny rozpätie stromu je podmnožinou grafu g a táto podmnožina má všetky vrcholy grafu a celkové náklady na hrany spájajúce vrcholy sú minimálne.
Diskutovali sme o dvoch algoritmoch, tj. Kruskalovom a Primovom, aby sme z grafu našli minimálny strom rozsahu. V tomto tutoriále sú tu vysvetlené aj aplikácie kostry.
=> Vyskúšajte tu najlepšie výukové programy pre C ++.
Odporúčané čítanie
- Výukový program Java Reflection s príkladmi
- Dátová štruktúra stromu B a stromu B + v C ++
- Výukový program pre Python DateTime s príkladmi
- Výukový program Bugzilla: Výukový program pre nástroj na správu chýb
- Štruktúra dát binárneho stromu v C ++
- 20+ výučba MongoDB pre začiatočníkov: bezplatný kurz MongoDB
- Výukový program zdieľania MongoDB s príkladom
- Výukový program na vytvorenie databázy MongoDB