数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究克鲁斯卡尔最小生成树算法 - 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 和其他语言编写此代码。它以克鲁斯卡尔的理念为模型。此程序在给定图中找到最短的生成树。希望本教程对您有所帮助。
更新于： 2022-03-07
3K+ 浏览量
广告