Heim > Artikel > Backend-Entwicklung > Kruskals Minimum Spanning Tree-Algorithmus – Greedy-Algorithmus in C++
Ein Spanning Tree ist ein gerichteter ungerichteter Graph-Untergraph, der alle Eckpunkte verbindet. In einem Diagramm können sich viele Spannbäume befinden. Der minimale Spannbaum (MST) in jedem Diagramm hat das gleiche oder ein geringeres Gewicht als alle anderen Spannbäume. Den Kanten des Spannbaums werden Gewichte zugewiesen, und die Summe ist das Gewicht, das jeder Kante zugewiesen wird. Da V die Anzahl der Eckpunkte im Diagramm ist, hat der minimale Spannbaum die Anzahl der Kanten (V – 1), wobei V die Anzahl der Kanten ist.
Alle Kanten sollten in nicht absteigender Reihenfolge nach Gewicht sortiert werden.
Wählen Sie die kleinste Seite. Wird keine Schlaufe gebildet, wird die Kante mit einbezogen.
Schritt 2 sollte durchgeführt werden, bis der Spannbaum (V-1) Kanten hat.
In diesem Fall wird uns gesagt, wir sollten den gierigen Ansatz verwenden. Die gierige Option besteht darin, die Kante mit dem geringsten Gewicht zu wählen. Beispiel: Der minimale Spannbaum dieses Diagramms ist (9-1)= 8 Kanten.
After sorting: Weight Src Dest 21 27 26 22 28 22 22 26 25 24 20 21 24 22 25 26 28 26 27 22 23 27 27 28 28 20 27 28 21 22 29 23 24 30 25 24 31 21 27 34 23 25
Jetzt müssen wir alle Kanten basierend auf der Sortierung auswählen.
enthält Kante 26-27->, da keine Schleife gebildet wird
Kante enthält 28-22->, da keine Schleife gebildet wird
enthält Kante 26-25->, da keine Schleife gebildet wird.
Kante 20-21-> ist enthalten, da keine Schleife gebildet wird.
Kante 22-25-> ist enthalten, da keine Schleife gebildet wird.
Kante 28-26-> wegen Schleifenbildung verworfen
Kante 22-23-> > enthalten, da keine Schleife gebildet wurde
Kante 27-28-> wegen Schleifenbildung verworfen
Kante 20 -27-> enthalten weil keine Schleife gebildet wird endet hier.
Beispiel
#include <stdio.h> #include <stdlib.h> #include <string.h> struct Edge { int src, dest, weight; }; struct Graph { int V, E; struct Edge* edge; }; struct Graph* createGraph(int V, int E){ struct Graph* graph = (struct Graph*)(malloc(sizeof(struct Graph))); graph->V = V; graph->E = E; graph->edge = (struct Edge*)malloc(sizeof( struct Edge)*E); return graph; } struct subset { int parent; int rank; }; int find(struct subset subsets[], int i){ if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } void Union(struct subset subsets[], int x, int y){ int xroot = find(subsets, x); int yroot = find(subsets, y); if (subsets[xroot].rank < subsets[yroot].rank) subsets[xroot].parent = yroot; else if (subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot; else{ subsets[yroot].parent = xroot; subsets[xroot].rank++; } } int myComp(const void* a, const void* b){ struct Edge* a1 = (struct Edge*)a; struct Edge* b1 = (struct Edge*)b; return a1->weight > b1->weight; } void KruskalMST(struct Graph* graph){ int V = graph->V; struct Edge result[V]; int e = 0; int i = 0; qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp); struct subset* subsets = (struct subset*)malloc(V * sizeof(struct subset)); for (int v = 0; v < V; ++v) { subsets[v].parent = v; subsets[v].rank = 0; } while (e < V - 1 && i < graph->E) { struct Edge next_edge = graph->edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); if (x != y) { result[e++] = next_edge; Union(subsets, x, y); } } printf("Following are the edges in the constructed MST\n"); int minimumCost = 0; for (i = 0; i < e; ++i){ printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight); minimumCost += result[i].weight; } printf("Minimum Cost Spanning tree : %d",minimumCost); return; } int main(){ /* Let us create the following weighted graph 30 0--------1 | \ | 26| 25\ |15 | \ | 22--------23 24 */ int V = 24; int E = 25; struct Graph* graph = createGraph(V, E); graph->edge[0].src = 20; graph->edge[0].dest = 21; graph->edge[0].weight = 30; graph->edge[1].src = 20; graph->edge[1].dest = 22; graph->edge[1].weight = 26; graph->edge[2].src = 20; graph->edge[2].dest = 23; graph->edge[2].weight = 25; graph->edge[3].src = 21; graph->edge[3].dest = 23; graph->edge[3].weight = 35; graph->edge[4].src = 22; graph->edge[4].dest = 23; graph->edge[4].weight = 24; KruskalMST(graph); return 0; }
Ausgabe
Following are the edges in the constructed MST 22 -- 23 == 24 20 -- 23 == 25 20 -- 21 == 30 Minimum Cost Spanning tree : 79
Fazit
Das obige ist der detaillierte Inhalt vonKruskals Minimum Spanning Tree-Algorithmus – Greedy-Algorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!