minimum spanning tree tutorial
Aquest tutorial de C ++ explica què és un arbre d’extensió mínim (MST) juntament amb els algorismes de Prim i Kruskal per trobar MST en un gràfic i les seves aplicacions:
Un arbre que abasta es pot definir com un subconjunt d'un gràfic, que consta de tots els vèrtexs que cobreixen les vores mínimes possibles i no té un cicle. No es pot desconnectar l'arbre que abasta.
Tots els gràfics connectats i no dirigits tenen almenys un arbre que abasta. Un gràfic desconnectat no té un arbre que abasta, ja que no és possible incloure tots els vèrtexs.
=> Vegeu aquí per explorar la llista completa de tutorials de C ++.
Què aprendreu:
Arbre que abasta a C ++
Penseu en el següent gràfic connectat.
Com es mostra més amunt, per al gràfic connectat que conté 3 vèrtexs, tenim tres arbres que abasten. En general, si N és el nombre de nodes d'un gràfic, llavors un gràfic complet connectat té N màximN-2nombre d'arbres que abasten. Per tant, al gràfic anterior N = 3, en té 3(3-2)= 3 arbres que abasten.
A continuació s’enumeren algunes de les propietats de l’arbre que abasta:
- Un gràfic connectat pot tenir més d’un arbres.
- Tots els arbres que abasten un gràfic tenen el mateix nombre de nodes i arestes.
- Si traiem una vora de l'arbre que s'estén, es convertirà en mínimament connectat i farà que el gràfic estigui desconnectat.
- D’altra banda, si afegiu una vora a l’arbre que abasta, el convertireu màximament acíclica creant així un bucle.
- Un arbre que abasta no té un bucle ni un cicle.
Què és un arbre d'extensió mínim (MST)
Un arbre d’extensió mínim és el que conté menys pes entre tots els altres arbres d’extensió d’un gràfic ponderat connectat. Hi pot haver més d’un arbre d’extensió mínim per a un gràfic.
Hi ha dos algoritmes més populars que s’utilitzen per trobar l’arbre d’extensió mínim en un gràfic.
Inclouen:
- L’algorisme de Kruskal
- L’algorisme de Prim
Analitzem aquests dos algorismes.
Algorisme de Kruskal
L’algorisme de Kruskal és un algorisme per trobar l’MST en un gràfic connectat.
L’algorisme de Kruskal troba un subconjunt d’un gràfic G tal que:
- Forma un arbre amb tots els vèrtexs.
- La suma dels pesos és la mínima entre tots els arbres que es poden formar a partir d’aquest gràfic.
La seqüència de passos de l'algorisme de Kruskal es dóna de la següent manera:
- Primer ordeneu totes les vores del pes més baix al més alt.
- Agafeu la vora amb el pes més baix i afegiu-la a l'arbre que abasta. Si es crea el cicle, descarta la vora.
- Seguiu afegint arestes com al pas 1 fins que es considerin tots els vèrtexs.
Pseudocodi per a l’algorisme de Kruskal
A continuació es mostra el pseudocodi de l’algorisme de Kruskal
Ara vegem la il·lustració de l'algorisme de Kruskal.
Ara escollim la vora amb el menor pes, que és 2-4.
A continuació, trieu la vora 2-3 més curta següent.
A continuació, escollim la vora següent amb la vora més curta i això no crea un cicle, és a dir, 0-3
millor utilitat del sistema per a Windows 10
El següent pas és triar l’aresta més curta perquè no formi un cicle. Això és 0-1.
Com podem veure, hem cobert tots els vèrtexs i tenim un arbre que abasta amb un cost mínim aquí.
A continuació, implementarem l’algorisme de Kruskal mitjançant 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 Sortida:
L’arbre mínim d’extensió (MST) d’acord amb l’algorisme de Kruskal:
Vora: pes
A 2 - 4: 1
2 - 3: 2
0-1: 3
0-3: 3
Tingueu en compte que hem utilitzat el mateix gràfic d’exemple al programa que a la il·lustració de l’algoritme de Kruskal anterior. En aquesta implementació fem ús de dos vectors; un per emmagatzemar gràfics i un altre per emmagatzemar l’arbre d’extensió mínima Recursivament trobem les vores amb el menor pes i les afegim al vector MST fins que es cobreixin tots els vèrtexs.
L’algorisme de Prim
L’algorisme de Prim és un algorisme més per trobar el mínim que abasta l’arbre d’un gràfic. A diferència de l’algorisme de Kruskal que comença amb les vores del gràfic, l’algorisme de Prim comença amb un vèrtex. Comencem per un vèrtex i seguim afegint arestes amb el mínim pes fins que es cobreixen tots els vèrtexs.
La seqüència de passos de l'algorisme de Prim és la següent:
- Trieu un vèrtex aleatori com a vèrtex inicial i inicialitzeu un arbre d’extensió mínim.
- Cerqueu les vores que connecten amb altres vèrtexs. Cerqueu la vora amb el pes mínim i afegiu-la a l'arbre que abasta.
- Repetiu el pas 2 fins que s’obtingui l’arbre que abasta.
Pseudocodi per a l’algorisme de Prim
Ara vegem una il·lustració de l’algorisme de Prim.
Per a això, fem servir el mateix gràfic d’exemple que vam fer servir a la Il·lustració de l’algorisme de Kruskal.
Seleccionem el node 2 com a vèrtex aleatori.
A continuació, seleccionem la vora amb el menor pes de 2. Escollim la vora 2-4.
A continuació, escollim un altre vèrtex que encara no es troba a l'arbre que abasta. Triem l’aresta 2-3.
Ara seleccionem una vora amb menys pes dels vèrtexs anteriors. Tenim l’avantatge 3-0 que té menys pes.
A continuació, escollim una vora amb el menor pes del vèrtex 0. Aquesta és la vora 0-1.
A partir de la figura anterior, veiem que ara hem cobert tots els vèrtexs del gràfic i hem obtingut un arbre complet amb un cost mínim.
Ara implementem l’algorisme de Prim a C ++.
Tingueu en compte que també en aquest programa hem utilitzat el gràfic d’exemple anterior com a entrada per poder comparar la sortida donada pel programa juntament amb la il·lustració.
El programa es presenta a continuació:
#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; } Sortida:
L’arbre d’extensió mínim segons l’algorisme de Prim:
Vora: pes
0-1: 3
0-3: 3
3-2: 2
A 2 - 4: 1
Aplicacions de l'arbre que abasta
Algunes de les aplicacions dels arbres d’extensió mínima són les següents:
# 1) Configuració de la xarxa de comunicacions: Quan volem configurar una xarxa de comunicació mitjançant enllaços de comunicació, el cost d’establir enllaços de comunicació entre dos punts es determina millor mitjançant un MST.
# 2) Anàlisi de clústers: Es pot utilitzar per resoldre el problema de l’agrupació K trobant un arbre d’extensió mínim i eliminant les vores més cares del k-1.
# 3) Disseny de xarxes de carreteres / ferrocarrils: Quan establim diverses xarxes de carreteres o ferrocarrils entre ciutats o dins d’elles, el cost del projecte és un factor molt important. Podem trobar el millor camí amb un cost mínim amb arbres mínims.
# 4) Planificació d’instal·lacions d’habitatge: Les instal·lacions com electricitat, aigua, clavegueram, etc. que es proporcionen a diverses cases també requereixen un cost òptim i això es fa mitjançant un MST.
# 5) Solució del problema del venedor ambulant: Podem utilitzar un MST per resoldre el problema del venedor ambulant que requereix visitar cada punt almenys una vegada.
Conclusió
L’arbre d’extensió mínim és el subconjunt del gràfic g i aquest subconjunt té tots els vèrtexs del gràfic i el cost total de les vores que connecten els vèrtexs és mínim.
Vam discutir dos algorismes, és a dir, el de Kruskal i el de Prim, per trobar l’arbre d’extensió mínim del gràfic. Les aplicacions de l'arbre que abasta també es van explicar aquí en aquest tutorial.
=> Consulteu aquí els millors tutorials de formació en C ++.
Lectura recomanada
- Tutorial de reflexió de Java amb exemples
- Estructura de dades d’arbre B i arbre B + en C ++
- Tutorial de Python DateTime amb exemples
- Tutorial Bugzilla: Tutorial pràctic de l'eina de gestió de defectes
- Estructura de dades de l'arbre binari en C ++
- 20+ Tutorial de MongoDB per a principiants: curs gratuït de MongoDB
- Tutorial de MongoDB Sharding amb exemple
- Tutorial de creació de bases de dades de MongoDB
