既然思路你都懂，我就直接贴程序咯！
如下源代码来自CSDN大神分享
源代码仅网页端可见！
#include
#define MAXSIZE 30
#define MAXCOST 32767
typedef struct
{
int u;//边的起始顶点
int v;//边的起始终点
int w;//边的权值
}Edge;
void Bubblesort(Edge R[], int e)//冒泡排序，对数组R中的e条边按权值递增排序
{
Edge temp;
int i, j, swap;
for (i = 0; i {
swap = 0;
for (j = 0; j if (R[j].w>R[j + 1].w)
{
temp = R[j]; R[j] = R[j + 1]; R[j + 1] = temp;//交换R[j]和R[j+1]
swap = 1;//置有交换标志
}
if (swap == 0) break;//本趟比较中未出现交换则结束排序
}
}
void Kruskal(int gm[][6], int n)//在顶点为n的连接图中构造最小的生成树，gm为连通网的邻接矩阵
{
int i, j, u1, v1, sn1, sn2, k;
int vest[MAXSIZE];//数组vest用于判断两顶点之间是否连通
Edge E[MAXSIZE];//MAXSIZE为可存放边数的最大常量值
k = 0;
for (i = 0; i for (j = 0; j if (i {
E[k].u = i;
E[k].v = j;
E[k].w = gm[i][j];
k++;
}
Bubblesort(E, k);//采用冒泡排序对数组E中的k条边按权值递增排序
for (i = 0; i vest[i] = i;//给每个顶点置不同连通分量编号，即初始时有n个连通分量
k = 1;//k表示当前构造生成树的第n条边，初始值为1
j = 0;//j为数组E中元素的下标，初值为0
while (k {
u1 = E[j].u; v1 = E[j].v;//取一条边的头尾顶点
sn1 = vest[u1];
sn2 = vest[v1];//分别得到这两个顶点所属的集合编号
if (sn1 != sn2)//两顶点分属于不同集合则该边为最小生成树的一条边
{
printf("Edge:(%d,%d),Wight:%d\n", u1, v1, E[j].w);
k++;//生成的边数增1
for (i = 0; i if (vest[i] == sn2)//集合编号为sn2的第i号边其边号改为sn1
vest[i] = sn1;
}
j++;//扫描下一条边
}
}
void main()
{
int g[6][6] = { { 100,6,1,5,100,100 },{ 6,100,5,100,3,100 },{ 1,5,100,5,6,4 },
{ 5,100,5,100,100,2 },{ 100,3,6,100,100,6 },{ 100,100,4,2,6,100 } };
Kruskal(g, 6);//生成最小生成树
getchar();
}
运行如下图所示：
