?
算法描述：
Kruskal算法是按权值递增的次序来构造最小生成树的方法。
假设G(V,E)最一个具有n个顶点的连通网，顶点集V={v1,v2,....,vn}。设所求的最小生成树为T={U,TE},其中U是T的顶点集，TE是Ｔ的边集，U和TE的初始值为空集。Kruskal算法的基本思想如下：将最小生成树初始化为T=(V,TE),仅包含 G的全部顶点，不包含G的任一条边，此时，T由n 个连通分量组成，每个分量只有一个顶点；将图中G中的边按权值从小到大排序，选择代价最小了一条边，若该边所依附的顶点分属于T中的不同的连通分量，则将此边加入到TE中，否则，舍弃此边而选择下一条代价最小的边。依次类推，直至TE中包含n-1条边（即T中所有的顶点都在同一连通分量上）为止。
?
算法实现：
设置一个edge数组存储连通网中所有的边，为了便于选择当前权值最小的边，需要将edge中的边按权值从小到大进行排列。
而在连通分量的合并上，可以采用集合的合并方法，对于有n个顶点的连通网，设置一个数组father[0...n-1]，其初始值为-1,表示n个顶点在不同的连通分量上。然后，依次扫描edge数组中的每一条边，并查找相关联的两个顶点所属的连通分量，假设vf1和vf2为两个顶点的所在树的根节点的序号，若vf1不等于vf2，则表明这条边的两个顶点不属于同一个连通分量，则将这条边作为最小生成树的边并输出，然后合并它们所属的两个连通分量。
?
算法代码：
?
int findFather(int father[],int v){
int t = v;
while(father[t] != -1)
t = father[t];
return t;
}
/* *
*Kruskal算法求最小生成树
* */
void Kruskal_MG(MGraph MG,Edge edge[]){
int father[MAX_VEX_NUM];
int i,count,vf1,vf2;
// 初始化father数组
for(i = 0;i < MAX_VEX_NUM;i++){
father[i] = -1;
}
i = 0;
count = 0; // 统计加入最小生树中的边数
// 遍历任意两个结点之间的边
while(i < MG.arcnum && count < MG.arcnum){
vf1 = findFather(father,edge[i].start);
vf2 = findFather(father,edge[i].end);
// 如果这两个节点不属于同一个连通分量，则加入同一个连通分量
if (vf1 != vf2){
father[vf2] = vf1;
count++;
printf(%c,%c,%d
,MG.vexs[edge[i].start],MG.vexs[edge[i].end],edge[i].cost);
}
i++;
}
}
其中，函数findFather的作用就是找指定节点所属的连通分量，在这里也就是找其所在树的根节点在数组中的序号。
?
?
算法说明：
对于带权图G中e条边的权值的排序方法可以有多种，这里采用的是最简单的冒泡排序法，时间复杂度为O(n^2)。而判断新选择的边的两个顶点是否在同一个连通分量中，这个问题等价于一个在最多有n 个顶点的生成树中遍历寻找新选择的边的两个节点是否存在的问题，所以此算法的复杂度最坏情况下是O(n^2)。
注意：一般来讲，Prim算法的时间复杂度为O(n^2),因此适合于稠密图，而Kruskal算法需要对e条边进行排序，最快的情况下复杂度为O(elog2e)，因此对于稀疏图，采用Kruskal算法比较合适。
?
完整代码：
?
/*
* =====================================================================================
*
* Filename: Kruskal.c
*
* Description: 最小生成树之Kruskal算法
*
* Version: 1.0
* Created: 2015年05月06日 21时25分12秒
* Revision: none
* Compiler: gcc
*
* Author: jesson20121020 (), 997287955@qq.com
* Organization:
*
* =====================================================================================
*/
#include
#include
#define MAX_VEX_NUM 50 #define MAX_ARC_NUM 100 #define UN_REACH 1000 typedef char VertexType; typedef enum { DG, UDG } GraphType; typedef struct { VertexType vexs[MAX_VEX_NUM]; int arcs[MAX_VEX_NUM][MAX_VEX_NUM]; int vexnum, arcnum; GraphType type; } MGraph; /** * 根据名称得到指定顶点在顶点集合中的下标 * vex 顶点 * return 如果找到，则返回下标，否则，返回０ */ int getIndexOfVexs(char vex, MGraph *MG) { int i; for (i = 1; i <= MG->vexnum; i++) { if (MG->vexs[i] == vex) { return i; } } return 0; } /** * 创建邻接矩阵 */ void create_MG(MGraph *MG) { int i, j, k,weight; int v1, v2, type; char c1, c2; printf(Please input graph type DG(0) or UDG(1) :); scanf(%d, &type); if (type == 0) MG->type = DG; else if (type == 1) MG->type = UDG; else { printf(Please input correct graph type DG(0) or UDG(1)!); return; } printf(Please input vexmun : ); scanf(%d, &MG->vexnum); printf(Please input arcnum : ); scanf(%d, &MG->arcnum); getchar(); for (i = 1; i <= MG->vexnum; i++) { printf(Please input %dth vex(char):, i); scanf(%c, &MG->vexs[i]); getchar(); } //初始化邻接矩阵 for (i = 1; i <= MG->vexnum; i++) { for (j = 1; j <= MG->vexnum; j++) { if(i == j) MG->arcs[i][j] = 0; else MG->arcs[i][j] = UN_REACH; } } //输入边的信息，建立邻接矩阵 for (k = 1; k <= MG->arcnum; k++) { printf(Please input %dth arc v1(char) v2(char) weight(int): , k); scanf(%c %c %d, &c1, &c2,&weight); v1 = getIndexOfVexs(c1, MG); v2 = getIndexOfVexs(c2, MG); if (MG->type == 1) MG->arcs[v1][v2] = MG->arcs[v2][v1] = weight; else MG->arcs[v1][v2] = weight; getchar(); } } /** * 打印邻接矩阵和顶点信息 */ void print_MG(MGraph MG) { int i, j; if(MG.type == DG){ printf(Graph type: Direct graph ); } else{ printf(Graph type: Undirect graph ); } printf(Graph vertex number: %d ,MG.vexnum); printf(Graph arc number: %d ,MG.arcnum); printf(Ve