minimum spanning tree tutorial
Acest tutorial C ++ explică ce este un copac minim care se întinde împreună cu algoritmii lui Prim și Kruskal pentru a găsi MST într-un grafic și aplicațiile sale:
Un copac Spanning poate fi definit ca un subset al unui grafic, care constă din toate vârfurile care acoperă marginile minime posibile și nu are un ciclu. Arborele de întindere nu poate fi deconectat.
Fiecare grafic conectat și nedirecționat are cel puțin un arbore care se întinde. Un grafic deconectat nu are un copac întins, deoarece nu este posibil să se includă toate vârfurile.
=> Consultați aici pentru a explora lista completă de tutoriale C ++.
Ce veți învăța:
Arborele care se întinde în C ++
Luați în considerare următorul grafic conectat.
Așa cum se arată mai sus, pentru graficul conectat dat care conține 3 vârfuri, avem trei copaci care se întind. În general, dacă N este numărul de noduri dintr-un grafic, atunci un grafic complet conectat are maxim NN-2numărul copacilor care se întind. Astfel, în graficul de mai sus N = 3, prin urmare, are 3(3-2)= 3 copaci care se întind.
Unele dintre proprietățile arborelui de întindere sunt enumerate mai jos:
- Un grafic conectat poate avea mai mulți copaci.
- Toți copacii care se întind într-un grafic au același număr de noduri și margini.
- Dacă scoatem o margine din arborele întins, atunci aceasta va deveni conectat minim și va face graficul deconectat.
- Pe de altă parte, adăugarea unei margini la arborele întins îl va face maxim aciclice creând astfel o buclă.
- Un copac întins nu are o buclă sau un ciclu.
Ce este un copac minim de întindere (MST)
Un copac minim care se întinde este cel care conține cea mai mică greutate dintre toți ceilalți copaci care se întind dintr-un grafic ponderat conectat. Pentru un grafic poate exista mai mult de un arbore minim de întindere.
Există doi algoritmi cei mai populari care sunt folosiți pentru a găsi arborele minim de întindere într-un grafic.
Ei includ:
- Algoritmul lui Kruskal
- Algoritmul lui Prim
Să discutăm ambii algoritmi!
Algoritmul lui Kruskal
Algoritmul lui Kruskal este un algoritm pentru a găsi MST într-un grafic conectat.
Algoritmul lui Kruskal găsește un subset al unui grafic G astfel încât:
- Formează un copac cu fiecare vârf în el.
- Suma greutăților este minimul dintre toți copacii care se pot întinde din acest grafic.
Secvența de pași pentru algoritmul lui Kruskal este dată după cum urmează:
- Mai întâi sortați toate marginile de la cea mai mică greutate la cea mai mare.
- Luați marginea cu cea mai mică greutate și adăugați-o în arborele care se întinde. Dacă ciclul este creat, aruncați marginea.
- Continuați să adăugați muchii ca la pasul 1 până când sunt luate în considerare toate vârfurile.
Pseudocod pentru algoritmul lui Kruskal
Mai jos este pseudo-codul pentru algoritmul lui Kruskal
Acum, să vedem ilustrația algoritmului lui Kruskal.
Acum alegem muchia cu cea mai mică greutate, care este 2-4.
Apoi, alegeți următoarea margine cea mai scurtă 2-3.
Apoi alegem muchia următoare cu cea mai scurtă muchie și asta nu creează un ciclu adică 0-3
ce instrumente folosesc analiștii de afaceri
Următorul pas este să alegeți cea mai scurtă margine, astfel încât să nu formeze un ciclu. Acesta este 0-1.
După cum putem vedea, am acoperit toate vârfurile și avem un copac care se întinde cu un cost minim aici.
Apoi, vom implementa algoritmul lui Kruskal folosind 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 Ieșire:
Arborele minim de întindere (MST) conform algoritmului lui Kruskal:
Marginea: Greutate
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Rețineți că am folosit același exemplu de grafic în program pe care l-am folosit în ilustrația algoritmului Kruskal de mai sus. În această implementare folosim doi vectori; unul pentru a stoca graficul și altul pentru a stoca arborele minim de întindere. Găsim recursiv marginile cu cea mai mică greutate și le adăugăm la vectorul MST până când toate vârfurile sunt acoperite.
Algoritmul lui Prim
Algoritmul lui Prim este încă un alt algoritm pentru a găsi minimul care acoperă arborele unui grafic. Spre deosebire de algoritmul lui Kruskal care începe cu marginile graficului, algoritmul lui Prim începe cu un vârf. Începem cu un vârf și continuăm să adăugăm margini cu cea mai mică greutate până când toate vârfurile sunt acoperite.
Secvența de pași pentru algoritmul lui Prim este după cum urmează:
- Alegeți un vârf aleatoriu ca vârf de pornire și inițializați un copac minim de întindere.
- Găsiți marginile care se conectează la alte vârfuri. Găsiți marginea cu greutate minimă și adăugați-o în arborele care se întinde.
- Repetați pasul 2 până când se obține arborele care se întinde.
Pseudocod pentru algoritmul lui Prim

Acum, să vedem o ilustrare pentru algoritmul lui Prim.
Pentru aceasta, folosim același exemplu de grafic pe care l-am folosit în Ilustrația algoritmului lui Kruskal.

Să selectăm nodul 2 ca vârf aleatoriu.

Apoi, selectăm muchia cu cea mai mică greutate din 2. Alegem muchia 2-4.

Apoi, alegem un alt vârf care nu se află încă în arborele care se întinde. Alegem muchia 2-3.

Acum, să selectăm o margine cu greutatea minimă din vârfurile de mai sus. Avem muchia 3-0 care are cea mai mică greutate.

Apoi, alegem o margine cu cea mai mică greutate din vârful 0. Aceasta este marginea 0-1.

Din figura de mai sus, vedem că am acoperit acum toate vârfurile din grafic și am obținut un copac complet care se întinde cu un cost minim.
Acum, să implementăm algoritmul lui Prim în C ++.
Rețineți că și în acest program am folosit graficul de mai sus ca intrare, astfel încât să putem compara ieșirea dată de program împreună cu ilustrația.
Programul este prezentat mai jos:
#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; }
Ieșire:
Arborele minim de întindere conform algoritmului Prim:
Marginea: Greutate
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Aplicații ale copacului
Unele dintre aplicațiile copacilor minimi sunt următoarele:
# 1) Configurare rețea de comunicații: Când vrem să configurăm o rețea de comunicații folosind legături de comunicație, atunci costul stabilirii legăturilor de comunicare între două puncte este cel mai bine determinat folosind un MST.
# 2) Analiza clusterului: Poate fi folosit pentru a rezolva problema grupării K prin găsirea unui copac minim și ștergerea celor mai scumpe margini k-1.
# 3) Amenajarea rețelelor rutiere / feroviare: Când stabilim diverse rețele rutiere sau feroviare între sau în interiorul orașelor, costul proiectului este un factor foarte important. Putem găsi cea mai bună cale cu un cost minim, folosind copaci minimi.
# 4) Planificarea facilităților de locuințe: Facilitățile precum electricitatea, apa, canalizarea etc. care trebuie furnizate unui număr de case necesită, de asemenea, să fie la un cost optim și acest lucru se face folosind un MST.
# 5) Rezolvarea problemei vânzătorului călător: Putem folosi un MST pentru a rezolva problema vânzătorului călător care necesită vizita fiecărui punct cel puțin o dată.
Concluzie
Arborele minim de întindere este subsetul graficului g și acest subset are toate vârfurile graficului și costul total al muchiilor care leagă vârfurile este minim.
Am discutat doi algoritmi, adică Kruskal și Prim, pentru a găsi arborele minim care se întinde din grafic. Aplicațiile arborelui întins au fost, de asemenea, explicate aici în acest tutorial.
=> Consultați aici cele mai bune tutoriale de formare C ++.
Lectură recomandată
- Tutorial de reflecție Java cu exemple
- Structura de date B Tree și B + Tree în C ++
- Tutorial Python DateTime cu exemple
- Tutorial Bugzilla: Instrument practic de gestionare a defectelor
- Structura de date a arborelui binar în C ++
- 20+ Tutorial MongoDB pentru începători: curs gratuit MongoDB
- Tutorial MongoDB Sharding cu exemplu
- Tutorial MongoDB Create Database