Kruskal 的最小生成树算法——C++ 中的贪心算法

  • Z时代
  • 2024-01-10
  • 分类：综合

生成树是连接所有顶点的链接和无向图子图。图中可以存在许多生成树。每个图上的最小生成树 (MST) 与所有其他生成树的权重相同或更少。权重分配给生成树的边，总和是分配给每条边的权重。由于 V 是图中的顶点数，因此最小生成树的边数为 (V - 1)，其中 V 是边数。

使用 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 的最小生成树算法-贪婪方法和 C++ 代码来解决这个问题。我们也可以用 java、python 和其他语言编写此代码。它以克鲁斯卡尔的概念为模型。该程序在给定图中找到最短的生成树。我们希望本教程对您有所帮助。

以上是 Kruskal 的最小生成树算法——C++ 中的贪心算法 的全部内容， 来源链接： utcz.com/z/363480.html

回到顶部