首页 > 后端开发 > C++ > 正文

Kruskal的最小生成树算法-贪婪算法在C++中

PHPz
发布: 2023-08-28 15:05:07
转载
1198 人浏览过

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

使用 Kruskal 算法查找最小生成树

  • 所有边应按权重非降序排列。

  • 选择最小的边。如果未形成环,则包含该边。

  • 应执行步骤 2,直到生成树具有 (V-1) 条边。

在这种情况下,我们被告知要使用贪婪方法。贪心选项是选择权重最小的边。举例来说:该图的最小生成树为 (9-1)= 8 条边。

Kruskal的最小生成树算法-贪婪算法在C++中

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++中的详细内容。更多信息请关注PHP中文网其他相关文章!

来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!