minimum spanning tree tutorial
Questo tutorial in C ++ spiega cos'è un MST (Minimum Spanning Tree) insieme agli algoritmi di Prim e Kruskal per trovare MST in un grafico e le sue applicazioni:
Uno Spanning tree può essere definito come un sottoinsieme di un grafo, che consiste di tutti i vertici che coprono il minimo possibile dei bordi e non ha un ciclo. Lo spanning tree non può essere disconnesso.
Ogni grafo connesso e non orientato ha almeno uno spanning tree. Un grafo disconnesso non ha uno spanning tree poiché non è possibile includere tutti i vertici.
=> Vedi qui per esplorare l'elenco completo dei tutorial C ++.
Cosa imparerai:
Spanning Tree in C ++
Considera il seguente grafico collegato.
Come mostrato sopra, per il dato Graph connesso contenente 3 vertici, abbiamo tre spanning tree. In generale, se N è il numero di nodi in un grafico, un grafo connesso completo ha massimo NN-2numero di alberi spanning. Quindi nel grafico sopra N = 3, quindi, ha 3(3-2)= 3 alberi spanning.
Di seguito sono elencate alcune delle proprietà dello spanning tree:
- Un grafo connesso può avere più di uno spanning tree.
- Tutti gli spanning tree in un grafico hanno lo stesso numero di nodi e bordi.
- Se rimuoviamo un bordo dallo spanning tree, lo diventerà minimamente connesso e renderà il grafico scollegato.
- D'altra parte, l'aggiunta di un bordo allo spanning tree lo farà al massimo aciclico creando così un ciclo.
- Uno spanning tree non ha un loop o un ciclo.
Cos'è un Minimum Spanning Tree (MST)
Uno spanning tree minimo è quello che contiene il peso minore tra tutti gli altri spanning tree di un grafo ponderato connesso. Può esserci più di uno spanning tree minimo per un grafico.
Esistono due algoritmi più popolari che vengono utilizzati per trovare lo spanning tree minimo in un grafico.
Loro includono:
- Algoritmo di Kruskal
- Algoritmo di Prim
Parliamo di entrambi questi algoritmi!
Algoritmo di Kruskal
L'algoritmo di Kruskal è un algoritmo per trovare l'MST in un grafo connesso.
L'algoritmo di Kruskal trova un sottoinsieme di un grafo G tale che:
- Forma un albero con ogni vertice in esso.
- La somma dei pesi è il minimo tra tutti gli spanning tree che possono essere formati da questo grafico.
La sequenza di passaggi per l'algoritmo di Kruskal è fornita come segue:
- Per prima cosa ordina tutti i bordi dal peso più basso al più alto.
- Prendi il bordo con il peso più basso e aggiungilo allo spanning tree. Se il ciclo viene creato, scartare il bordo.
- Continua ad aggiungere bordi come nel passaggio 1 finché non vengono considerati tutti i vertici.
Pseudocodice per l'algoritmo di Kruskal
Di seguito è riportato lo pseudo-codice per l'algoritmo di Kruskal
Vediamo ora l'illustrazione dell'algoritmo di Kruskal.
Ora scegliamo il bordo con il peso minore che è 2-4.
Quindi, scegli il successivo bordo più corto 2-3.
Quindi scegliamo il bordo successivo con il bordo più corto e questo non crea un ciclo, cioè 0-3
il modo migliore per convertire youtube in mp4
Il passo successivo è scegliere il bordo più corto in modo che non formi un ciclo. Questo è 0-1.
Come possiamo vedere, abbiamo coperto tutti i vertici e qui abbiamo uno spanning tree con un costo minimo.
Successivamente, implementeremo l'algoritmo di Kruskal utilizzando 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 Produzione:
Il Minimum Spanning Tree (MST) secondo l'algoritmo di Kruskal:
Bordo: peso
2-4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Nota che abbiamo usato lo stesso grafico di esempio nel programma che abbiamo usato nell'illustrazione dell'algoritmo di Kruskal sopra. In questa implementazione utilizziamo due vettori; uno per memorizzare il grafico e un altro per memorizzare lo spanning tree minimo. Troviamo ricorsivamente i bordi con il minor peso e li aggiungiamo al vettore MST fino a coprire tutti i vertici.
Algoritmo di Prim
L'algoritmo di Prim è ancora un altro algoritmo per trovare il minimo che copre l'albero di un grafico. A differenza dell'algoritmo di Kruskal che inizia con i bordi del grafico, l'algoritmo di Prim inizia con un vertice. Iniziamo con un vertice e continuiamo ad aggiungere bordi con il minor peso fino a coprire tutti i vertici.
La sequenza dei passaggi per l'algoritmo di Prim è la seguente:
- Scegli un vertice casuale come vertice iniziale e inizializza uno spanning tree minimo.
- Trova i bordi che si connettono ad altri vertici. Trova il bordo con il peso minimo e aggiungilo allo spanning tree.
- Ripetere il passaggio 2 fino a ottenere lo spanning tree.
Pseudocodice per l'algoritmo di Prim
Vediamo ora un'illustrazione per l'algoritmo di Prim.
Per questo, stiamo usando lo stesso grafico di esempio che abbiamo usato nell'illustrazione dell'algoritmo di Kruskal.
Selezioniamo il nodo 2 come vertice casuale.
Successivamente, selezioniamo il bordo con il peso minore tra 2. Scegliamo il bordo 2-4.
Successivamente, scegliamo un altro vertice che non è ancora nello spanning tree. Scegliamo il bordo 2-3.
Ora selezioniamo un bordo con il minor peso dai vertici sopra. Abbiamo il 3-0 che ha il minor peso.
Successivamente, scegliamo un bordo con il peso minore dal vertice 0. Questo è il bordo 0-1.
Dalla figura sopra, vediamo che ora abbiamo coperto tutti i vertici nel grafo e ottenuto uno spanning tree completo con un costo minimo.
Ora implementiamo l'algoritmo di Prim in C ++.
Si noti che anche in questo programma, abbiamo utilizzato il grafico di esempio sopra come input in modo da poter confrontare l'output fornito dal programma insieme all'illustrazione.
Di seguito il programma:
#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; }
Produzione:
Lo Spanning Tree minimo secondo l'algoritmo di Prim:
Bordo: peso
0 - 1: 3
0 - 3: 3
3 - 2: 2
2-4: 1
Applicazioni di Spanning Tree
Alcune delle applicazioni di Minimum Spanning Tree sono le seguenti:
# 1) Configurazione della rete di comunicazione: Quando si desidera impostare una rete di comunicazione utilizzando collegamenti di comunicazione, il costo della creazione di collegamenti di comunicazione tra due punti è meglio determinato utilizzando un MST.
# 2) Analisi dei cluster: Può essere utilizzato per risolvere il problema del clustering K trovando uno spanning tree minimo ed eliminando i bordi k-1 più costosi.
# 3) Disposizione delle reti stradali / ferroviarie: Quando installiamo varie reti stradali o ferroviarie tra o all'interno delle città, il costo del progetto è un fattore molto importante. Possiamo trovare il percorso migliore con un costo minimo utilizzando alberi di copertura minimi.
# 4) Pianificazione delle strutture abitative: Anche servizi come elettricità, acqua, fognature, ecc. Da fornire a un certo numero di case devono essere a un costo ottimale e questo viene fatto utilizzando un MST.
# 5) Risolvere il problema del venditore ambulante: Possiamo usare un MST per risolvere il problema del venditore ambulante che richiede di visitare ogni punto almeno una volta.
Conclusione
Lo spanning tree minimo è il sottoinsieme del grafo g e questo sottoinsieme ha tutti i vertici del grafo e il costo totale dei bordi che collegano i vertici è minimo.
Abbiamo discusso due algoritmi, ovvero Kruskal e Prim, per trovare l'albero di copertura minimo dal grafico. Anche le applicazioni dello spanning tree sono state spiegate qui in questo tutorial.
=> Dai un'occhiata ai migliori tutorial di formazione C ++ qui.
Lettura consigliata
- Tutorial Java Reflection con esempi
- Struttura dati B Tree e B + Tree in C ++
- Tutorial Python DateTime con esempi
- Tutorial Bugzilla: Tutorial pratico dello strumento di gestione dei difetti
- Struttura dei dati dell'albero binario in C ++
- 20+ Tutorial MongoDB per principianti: corso MongoDB gratuito
- Tutorial sullo sharding di MongoDB con esempio
- Tutorial sulla creazione di database di MongoDB