最小生成树-贪心(Kruskal算法(克鲁斯卡尔算法))

问题描述

 设G = (V, E)是一个无向连通带权图，即一个网络。E的每条边(v, w)的权为c[v][w]。

 如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。

 生成树的各边权的总和称为该生成树的耗费。

 在G的所有生成树中，耗费最小的生成树称为G的最小生成树MST(minimum spanning tree) 。

算法思想

在保证无回路的前提下依次选出权重较小的n – 1条边。贪心策略：如果(i, j)是E中尚未被选中的边中权重最小的，并且(i, j)不会与已经选择的边构成回路，于是就选择 (i, j)。

 如何知道(i, j)不会造成回路？

为此初始时将图的n个顶点看成n个孤立连通分支,将所有的边按权由小到大排序, 并依边权递增顺序检查每一条边:若边(i, j) 的两个端点i和j属于同一个连通分支，则选择(i, j) 会造成回路，反之则不会造成回路。            

Kruskal算法的数据结构

数组e[][]表示图的边，e[i][u]、e[i][v]和e[i][w]分别表示边i的两个端点及其权重。函数Sort(e, w)将数组e按权重w从小到大排序。一个连通分支中的顶点表示为一个集合。函数Initialize(n)将每个顶点初始化为一个集合。函数Find(u)给出顶点u所在的集合。函数Union(a, b)给出集合a和集合b的并集。重载算符!=判断集合的不相等。

核心代码

Kruskal(int n, **e) { Sort(e, w); //将边按权重从小到大排序 initialize(n); //初始时每个顶点为一个集合 k = 1; //k累计已选边的数目， j = 1; //j为所选的边在e中的序号 while (k < n) //选择n – 1条边 {a = Find(e[j][u]); b = Find(e[j][v]); //找出第j条边两个端点所在的集合 if (a != b) {t[k++] = j; Union(a, b)} //若不同，第j条边放入树中并合并这两个集合 j++ } //继续考察下一条边 }

例子

给定一个连通带权图如下：           

 首先，在初始状态下，对各顶点赋予不同的标记（用颜色区别），如下图所示：               

 对所有边按照权值的大小进行排序，按照从小到大的顺序进行判断，首先是（1，3），由于顶点 1 和顶点 3 标记不同，所以可以构成生成树的一部分，遍历所有顶点，将与顶点 3 标记相同的全部更改为顶点 1 的标记，如（2）所示：                 其次是（4，6）边，两顶点标记不同，所以可以构成生成树的一部分，更新所有顶点的标记为：                 其次是（2，5）边，两顶点标记不同，可以构成生成树的一部分，更新所有顶点的标记为：                 然后最小的是（3，6）边，两者标记不同，可以连接，遍历所有顶点，将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记：                 继续选择权值最小的边，此时会发现，权值为 5 的边有 3 个，其中（1，4）和（3，4）各自两顶点的标记一样，如果连接会产生回路，所以舍去，而（2，3）标记不一样，可以选择，将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记：               

当选取的边的数量相比与顶点的数量小 1 时，说明最小生成树已经生成。

完整算法

#include<iostream> #include <stdio.h> #include <stdlib.h> using namespace std; typedef struct Edge //定义边集数组元素，v1,v2存顶点，weight存权重。 { int v1; int v2; int weight; }Edge; typedef struct ALGraph //定义图的结构，peak存顶点的数量，edge存边的数量 { //指针p作为边集数组，指针m为作为顶点数组 int peak; int edge; Edge *p; int *m; }ALGraph; //创建图 void CreatALGraph(ALGraph *G) { int i,j; printf("输入图的顶点数量和边的数量："); scanf("%d %d",&G->peak,&G->edge); G->p=(Edge *)malloc(sizeof(Edge)*(G->edge+1)); G->m=(int *)malloc(sizeof(int)*G->peak); for(i=0;i<G->peak;i++) { printf("请输入输入顶点："); scanf("%d",&G->m[i]); } for(i=0;i<G->edge;i++) { printf("请输入(vi-vj)和权重："); scanf("%d %d %d",&G->p[i].v1,&G->p[i].v2,&G->p[i].weight); } for(i=0 ;i<G->edge;i++) //冒泡排序法，权重从小到大存在边集数组中 { for(j=G->edge-1;j>i;j--) { if(G->p[i].weight>G->p[j].weight) { G->p[G->edge]=G->p[i]; G->p[i]=G->p[j]; G->p[j]=G->p[G->edge]; } } } } //通过parent[]找到可连接的边 int Find(int *parent,int g) { while(parent[g]!=0) { g=parent[g]; } return g; } //判断生成树是否完成，完成的标志是生成树的边等于顶点的数量减1 int Finish(ALGraph *G,int *parent) { int i,n=0; for(i=0;i<G->peak;i++) { if(parent[i]) { n++; } } if(n==G->peak-1) { return 1; } return 0; } //找到顶点的下标 int FindPeak(ALGraph *G,int g){ int i; for(i=0;i<G->peak;i++) { if(G->m[i]==g) return i; } return -1; } void MinTree_Kruskal(ALGraph *G) { int i,a,b; int parent[G->peak]; for(i=0;i<G->peak;i++) //初始化parent[] { parent[i]=0; } for(i=0;i<G->edge;i++) { a=Find(parent,FindPeak(G,G->p[i].v1)); b=Find(parent,FindPeak(G,G->p[i].v2)); if(a!=b) //如果a==b则表是a和b在同一颗生成树上，如果a和b连接则为生成环，不符合生成树 { parent[a]=b; printf("%d->%d %d\n",G->p[i].v1,G->p[i].v2,G->p[i].weight); } if(Finish(G,parent)) //完成后返回 { return; } } } int main() { ALGraph *G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G); MinTree_Kruskal(G); return 0; }

测试样例

测试样例是上面例子中的数据，但是注意这里是从0开始的

输入 输入图的顶点数量和边的数量：6 10 请输入输入顶点：0 请输入输入顶点：1 请输入输入顶点：2 请输入输入顶点：3 请输入输入顶点：4 请输入输入顶点：5 请输入(vi-vj)和权重：0 1 6 请输入(vi-vj)和权重：0 2 1 请输入(vi-vj)和权重：0 3 5 请输入(vi-vj)和权重：1 2 5 请输入(vi-vj)和权重：1 4 3 请输入(vi-vj)和权重：2 3 5 请输入(vi-vj)和权重：2 4 6 请输入(vi-vj)和权重：2 5 4 请输入(vi-vj)和权重：3 5 2 请输入(vi-vj)和权重：4 5 6

输出 0->2 1 3->5 2 1->4 3 2->5 4 1->2 5