クラスカルの最小スパニングツリーアルゴリズム-C++の欲張りアルゴリズム

スパニングツリーは、すべての頂点を接続するリンクされた無向のグラフサブグラフです。多くのスパニングツリーがグラフに存在する可能性があります。各グラフの最小スパニングツリー（MST）は、他のすべてのスパニングツリーと同じかそれ以下です。重みはスパニングツリーのエッジに割り当てられ、合計は各エッジに割り当てられた重みです。 Vはグラフ内の頂点の数であるため、最小全域木には（V-1）のエッジがあります。ここで、Vはエッジの数です。

クラスカルのアルゴリズムを使用して最小全域木を見つける

• すべてのエッジは、重みの降順ではない順序で配置する必要があります。

• 最小のエッジを選択します。サイクルが形成されていない場合、このエッジが含まれます。

• ステップ2は、スパニングツリーに（V-1）エッジができるまで実行する必要があります。

このシナリオでは、欲張り法を使用するように指示されています。貪欲なオプションは、重みが最小のエッジを選択することです。例として：このグラフの最小スパニングツリーは（9-1）=8エッジです。

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

次に、並べ替えに従ってすべてのエッジを選択する必要があります。

エッジ26-27->サイクルが形成されないため含まれています

エッジ28-22->サイクルが形成されないため含まれています

エッジ26-25->サイクルが形成されないため、含まれています。

エッジ20-21->サイクルが形成されないため含まれています

エッジ22-25->サイクルが形成されないため含まれています。

エッジ28-26->サイクルが形成されると破棄されます

エッジ22-23->サイクルが形成されないため含まれています

エッジ27-28->サイクルが形成されると破棄されます

エッジ20-27->サイクルが形成されないため含まれています

エッジ21-22->サイクルが形成されると破棄されます

エッジ23-24->サイクルが形成されないため含まれています

エッジの数は（V-1）なので、アルゴリズムはここで終了します。

例

#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;
}

出力

Following are the edges in the constructed MST
22 -- 23 == 24
20 -- 23 == 25
20 -- 21 == 30
Minimum Cost Spanning tree : 79

結論

このチュートリアルでは、クラスカルの最小スパニングツリーアルゴリズム-欲張り法とC++コードを使用してこの問題を解決する方法を示しました。このコードは、Java、Python、およびその他の言語で作成することもできます。これは、クラスカルの概念によってモデル化されました。このプログラムは、指定されたグラフで最短のスパニングツリーを見つけます。このチュートリアルがお役に立てば幸いです。