Kruskal の最小スパニング ツリー アルゴリズム - C++ の貪欲なアルゴリズム

スパニング ツリーは、すべての頂点を接続する有向無向グラフのサブグラフです。グラフ内には多数のスパニング ツリーが存在する場合があります。各グラフの最小スパニング ツリー (MST) の重みは、他のすべてのスパニング ツリーと同じかそれより小さくなります。重みはスパニング ツリーのエッジに割り当てられ、合計が各エッジに割り当てられた重みになります。 V はグラフ内の頂点の数であるため、V をエッジの数とすると、最小スパニング ツリーのエッジの数は (V - 1) になります。

Kruskal のアルゴリズムを使用して最小スパニング ツリーを見つける

• すべてのエッジは重みによる非降順で並べ替える必要があります。

• 最小のエッジを選択します。ループが形成されていない場合は、エッジが含まれます。

• ステップ 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

結論

このチュートリアルでは、Kruskal の最小スパニング ツリー アルゴリズム - Greedy メソッドと C コードを使用してこの質問を解決する方法を示します。 。このコードは Java、Python、その他の言語でも記述できます。クラスカルのコンセプトをモデルにしています。このプログラムは、指定されたグラフ内で最短のスパニング ツリーを見つけます。このチュートリアルがお役に立てば幸いです。

以上がKruskal の最小スパニング ツリー アルゴリズム - C++ の貪欲なアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。