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.

Finden Sie den minimalen Spannbaum mit dem Kruskal-Algorithmus

• 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

Dieses Tutorial zeigt, wie man dieses Problem mit Kruskals Minimum Spanning Tree-Algorithmus – Greedy-Methode und C++-Code löst. Wir können diesen Code auch in Java, Python und anderen Sprachen schreiben. Es ist dem Konzept von Kruskal nachempfunden. Dieses Programm findet den kürzesten Spannbaum in einem bestimmten Diagramm. Wir hoffen, dass Sie dieses Tutorial hilfreich fanden.

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!