minimum spanning tree tutorial
Ovaj vodič za C ++ objašnjava što je minimalno rasponično stablo (MST) zajedno s Primovim i Kruskalovim algoritmima za pronalaženje MST-a u grafikonu i njegove primjene:
Rasprostranjeno stablo može se definirati kao podskup grafa koji se sastoji od svih vrhova koji pokrivaju minimalno moguće rubove i nema ciklus. Rasprostiruće se stablo ne može odspojiti.
Svaki povezani i neusmjereni graf ima barem jedno rasponsko stablo. Nepovezani graf nema rasponsko stablo jer nije moguće uključiti sve vrhove.
=> Pogledajte ovdje kako biste istražili cjeloviti popis vodiča za C ++.
Što ćete naučiti:
Rasprostranjeno stablo u C ++
Razmotrimo sljedeći povezani graf.
Kao što je gore prikazano, za zadani povezani Graf koji sadrži 3 vrha imamo tri raspona. Općenito, ako je N broj čvorova u grafu, tada cjeloviti povezani graf ima maksimum NN-2broj rasprostranjenih stabala. Dakle, u gornjem grafikonu N = 3, dakle, ima 3(3-2)= 3 rasprostranjena stabla.
U nastavku su navedena neka svojstva rastućeg stabla:
- Povezani graf može imati više od jednog raspona stabala.
- Sva rasprostranjena stabla u grafu imaju jednak broj čvorova i bridova.
- Ako uklonimo jedan rub s rastegnutog stabla, tada će postati minimalno povezani i učinit će da graf bude odspojen.
- S druge strane, dodavanjem jednog ruba na rasprostranjeno stablo napravit će se maksimalno aciklički čime se stvara petlja.
- Rasprostranjeno stablo nema petlju ili ciklus.
Što je minimalno rastezno drvo (MST)
Minimalno rastezno stablo je ono koje sadrži najmanju težinu među svim ostalim rastegljivim stablima povezanog ponderiranog grafa. Za graf može postojati više od jednog minimalnog raspona.
Dva su najpopularnija algoritma koja se koriste za pronalaženje minimalnog raspona u grafu.
Oni uključuju:
- Kruskalov algoritam
- Primov algoritam
Razgovarajmo o oba algoritma!
Kruskalov algoritam
Kruskalov algoritam je algoritam za pronalaženje MST-a u povezanom grafu.
Kruskalov algoritam pronalazi podskup grafa G takav da:
- Tvori stablo sa svakim vrhom u sebi.
- Zbroj težina je najmanji među svim rasprostranjenim stablima koja se mogu oblikovati iz ovog grafa.
Slijed koraka za Kruskalov algoritam dan je kako slijedi:
- Prvo sortirajte sve rubove od najmanje težine do najviše.
- Uzmite rub s najmanjom težinom i dodajte ga na rastegnuto stablo. Ako je ciklus stvoren, odbacite rub.
- Nastavite dodavati rubove kao u koraku 1 dok se ne uzmu u obzir svi vrhovi.
Pseudokod za Kruskalov algoritam
Dolje je dan pseudo-kôd za Kruskalov algoritam
Sada da vidimo ilustraciju Kruskalovog algoritma.
Sada odabiremo rub s najmanjom težinom, a to je 2-4.
Zatim odaberite sljedeći najkraći rub 2-3.
Tada biramo sljedeći rub s najkraćim rubom i to ne stvara ciklus, tj. 0-3
Sljedeći je korak odabrati najkraći rub tako da ne tvori ciklus. Ovo je 0-1.
Kao što vidimo, pokrili smo sve vrhove i ovdje imamo rastegnuto stablo s minimalnim troškovima.
Dalje ćemo implementirati Kruskalov algoritam koristeći 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 Izlaz:
Minimalno rastezno drvo (MST) prema Kruskalovom algoritmu:
Rub: Težina
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Imajte na umu da smo u programu koristili isti primjer grafa kao i na gornjoj ilustraciji Kruskalovog algoritma. U ovoj provedbi koristimo dva vektora; jedan za pohranu grafa, a drugi za spremanje minimalnog raspona stabla. Rekurzivno pronalazimo rubove s najmanjom težinom i dodajemo ih MST vektoru dok nisu pokriveni svi vrhovi.
Primov algoritam
Primov algoritam je još jedan algoritam za pronalaženje minimuma koji obuhvaća stablo grafa. Za razliku od Kruskalovog algoritma koji započinje rubovima grafa, Primov algoritam započinje vrhom. Počinjemo s jednim vrhom i nastavljamo dodavati bridove s najmanjom težinom dok svi vrhovi ne budu pokriveni.
Slijed koraka za Primov algoritam je sljedeći:
- Odaberite slučajni vrh kao početni vrh i inicijalizirajte minimalno rasponično stablo.
- Pronađite rubove koji se povezuju s drugim vrhovima. Pronađite rub s minimalnom težinom i dodajte ga na rastegnuto stablo.
- Ponavljajte korak 2 dok se ne dobije rastuće stablo.
Pseudokod za Primov algoritam
Sada da vidimo ilustraciju Priminog algoritma.
Za to koristimo isti primjer grafa koji smo koristili u Ilustraciji Kruskalovog algoritma.
Odaberemo čvor 2 kao slučajni vrh.
Zatim odabiremo rub s najmanjom težinom od 2. Odabiremo rub 2-4.
Dalje, biramo drugi vrh koji još nije u rasponu stabla. Odabiremo rub 2-3.
Odaberite sada rub s najmanjom težinom iz gornjih vrhova. Imamo rub 3-0 koji ima najmanju težinu.
Dalje, odabiremo rub s najmanjom težinom iz vrha 0. To je rub 0-1.
Iz gornje slike vidimo da smo sada pokrili sve vrhove na grafikonu i dobili cjelovito rasponično stablo s minimalnim troškovima.
Sada ćemo implementirati Primov algoritam u C ++.
Imajte na umu da smo i u ovom programu gornji primjer grafa koristili kao ulaz kako bismo mogli usporediti izlaz koji daje program zajedno sa ilustracijom.
Program je dan u nastavku:
#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; } Izlaz:
rješavanje teških situacija na poslu
Minimalno stablo raspona prema Primovom algoritmu:
Rub: Težina
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Primjene rasprostranjenog stabla
Neke od primjena drveća s minimalnim rasponom su sljedeće:
# 1) Postavljanje komunikacijske mreže: Kada želimo uspostaviti komunikacijsku mrežu pomoću komunikacijskih veza, tada se trošak postavljanja komunikacijskih veza između dviju točaka najbolje određuje pomoću MST-a.
# 2) Analiza klastera: Može se koristiti za rješavanje problema K-klasteriranja pronalaženjem minimalnog raspona i brisanjem k-1 najskupljih rubova.
# 3) Postavljanje cestovnih / željezničkih mreža: Kada postavljamo razne cestovne ili željezničke mreže između ili unutar gradova, trošak projekta je vrlo važan čimbenik. Najbolju stazu s minimalnim troškovima možemo pronaći koristeći minimalno rastegnuta stabla.
# 4) Planiranje stambenih objekata: Objekti poput električne energije, vode, kanalizacije itd. Koji se moraju osigurati za brojne kuće također trebaju imati optimalne troškove, a to se radi pomoću MST-a.
# 5) Rješavanje problema putujućeg trgovca: Pomoću MST-a možemo riješiti problem trgovačkog putnika koji zahtijeva posjećivanje svake točke barem jednom.
Zaključak
Minimalno obuhvaćajuće stablo je podskup grafa g i ovaj podskup ima sve vrhove grafa, a ukupni trošak bridova koji povezuju vrhove je minimalan.
Raspravljali smo o dva algoritma, tj. Kruskalovom i Primovom, kako bismo pronašli minimalno rasponično stablo iz grafa. Ovdje su u ovom vodiču također objašnjene primjene rastegnutog stabla.
=> Ovdje pogledajte najbolje tutorijale za C ++.
Preporučena literatura
- Java Vodič za refleksiju s primjerima
- Struktura podataka stabla B i stabla B + u C ++
- Python DateTime Vodič s primjerima
- Vodič za Bugzilla: Praktični vodič za alat za upravljanje nedostacima
- Struktura podataka binarnog stabla u C ++
- 20+ MongoDB lekcija za početnike: besplatni tečaj MongoDB
- MongoDB Vodič za sjenčanje s primjerom
- MongoDB Vodič za izradu baze podataka
