文档介绍：kruskal 算法百科名片 Kruskal 算法每次选择 n-1 条边, 所使用的贪婪准则是: 从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。 Kruskal 算法分 e 步,其中 e 是网络中边的数目。按耗费递增的顺序来考虑这 e 条边,每次考虑一条边。当考虑某条边时,若将其加入到已选边的集合中会出现环路,则将其抛弃,否则,将它选入。目录[ 隐藏] Kruskal 算法 1. 普里姆算法( prim 算法) Kruskal 算法 1. 普里姆算法( prim 算法) [ 编辑本段] Kruskal 算法算法定义克鲁斯卡尔算法假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网, 则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后, 从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图, 也就是说, 将这两个顶点分别所在的两棵树合成一棵树; 反之, 若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有 n-1 条边为止。举例描述初始时没有任何边被选择。边(1,6) 是最先选入的边, 它被加入到欲构建的生成树中, 得到图 13-12c。下一步选择边(3,4) 并将其加入树中( 如图 1 3-12d 所示)。然后考虑边(2,7 ,将它加入树中并不会产生环路,于是便得到图 13-12e 。下一步考虑边( 2,3 )并将其加入树中(如图 13-12f所示)。在其余还未考虑的边中,(7,4) 具有最小耗费, 因此先考虑它, 将它加入正在创建的树中会产生环路,所以将其丢弃。此后将边( 5,4 )加入树中,得到的树如图 13-12g 所示。下一步考虑边( 7,5 ),由于会产生环路,将其丢弃。最后考虑边( 6,5 )并将其加入树中,产生了一棵生成树,其耗费为 99 。图 1-13给出了 Kruskal 算法的伪代码。 C 代码实现/* Copyright (c) 2002, 2006 by ctu_85 All Rights Reserved. */ /*I am sorry to say that the situation of unconnected graph is not conc erned */ #include "" #define maxver 10 #define maxright 100 int G[maxver][maxver],record=0,touched[maxver][maxver]; int circle=0; int FindCircle(int,int,int,int); int main() { int path[maxver][2],used[maxver][maxver]; int i,j,k,t,min=maxright,exsit=0; int v1,v2,num,temp,status=0; restart: printf("Please enter the numb