生成树是连接所有顶点的有向无向图子图。图中可以存在许多生成树。每个图上的最小生成树（MST）的权重相同或小于所有其他生成树。权重被分配给生成树的边，总和是分配给每个边的权重。由于 V 是图中的顶点数，因此最小生成树的边数为 (V - 1)，其中 V 是边数。
使用 Kruskal 算法查找最小生成树
在这种情况下，我们被告知要使用贪婪方法。贪心选项是选择权重最小的边。举例来说：该图的最小生成树为 (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
");
int minimumCost = 0;
for (i = 0; i < e; ++i){
printf("%d -- %d == %d
", 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
结论
本教程演示
.........................................................