一、 克鲁斯卡尔(Kruskal)算法

　　typedef struct {
　　　VertexType vex1;
　　　VertexType vex2;
　　　VRType weight;
　　}EdgeType;
　　typedef ElemType EdgeType;
　　typedef struct { 　　　　　　　　// 有向网的定义
　　　VertexType vexs[MAX_VERTEX_NUM]; 　// 顶点信息
　　　EdgeType edge[MAX_EDGE_NUM]; 　　　// 边的信息
　　　int vexnum,arcnum;　　　　　　　　// 图中顶点的数目和边的数目
　　}ELGraph;
　		   　
　
　　由于克鲁斯卡尔算法是依权值从小到大依次考察每条边，则在本章7.2节中讨论的各种图的表示方法在此都不适用。由此需对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个"有序表"。		  
  算法 7.8
　　void MiniSpanTree_Kruskal(ELGraph G, SqList& MSTree)
　{
　　// G.edge 中依权值从小到大存放有向网中各边，按克鲁斯卡尔
　　// 算法求得生成树的边存放在顺序表 MSTree 中
　　MFSet F;
　　InitSet(F, G.vexnum);　　　　　　　　　// 将森林F初始化为n棵树的集合
　　InitList(MSTree, G.vexnum);　　　　　　// 初始化生成树为空树
　　i=0; k=1;
　　while( k<G.vexnum ) {
　　　e = G.edge[i];　　　　　　　　　　　// 取第 i 条权值最小的边		  
　　以顺序表MSTree返回生成树上各条边。		  
  　　　r1 = fix_mfset(F, LocateVex(e.vex1));
　　　r2 = fix_mfset(F, LocateVex(e.vex2)); // 返回两个顶点所在树的树根
　　　if (r1 != r2) { 　　　　　　　　　　// 选定生成树上第k条边
　　　　if (ListInsert(MSTree, k, e)) k++;　// 插入生成树
　　　　mix_mfset(F, r1, r2);　　　　　　　// 将两棵树归并为一棵树
　　　} // if
　　　i++; 　　　　　　　　　　　　　　　// 继续考察下一条权值最小边
　　} // while
　　DestroySet(F);
　} // MiniSpanTree_Kruskal		   　　函数 fix_mfset 返回边的顶点所在树的树根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。



　　如果不考虑建立图的存储结构所需时间，则克鲁斯卡尔算法的时间复杂度为O (e)。