Kruskal算法的设计和C实现(同名2263)(共7页)

1、实验三 Kruskal算法的设计一、 设计目的. 根据算法设计需要, 掌握连通网的灵活表示方法;. 掌握最小生成树的Kruskal算法;. 基本掌握贪心算法的一般设计方法;. 进一步掌握集合的表示与操作算法的应用.二、 设计内容1 主要数据类型与变量 typedef struct int num; int tag; NODE;typedef struct int cost; int node1; int node2; EDGE;NODE setN; /* 节点集 */EDGE esN; /* 边集*/EDGE stN; /* 最小生成树的边集 */ 2 算法或程序模块 int Find(NOD

2、E *set,int elem)功能: 在数组set中顺序查找元素elem, 使用带压缩规则的查找算法,返回所在子集的根节点索引. int Union( NODE *set,int elem1, int elem2)功能: 应用Find算法首先找到elem1和elem2所在的子集, 然后应用带加权规则的并运算算法合并两个子集. 不成功时, 返回-1; 否则, 返回并集的根节点索引.int InsertSort(EDGE *dat,int n)功能: 用插入分类算法将连通图的边集按成本值的非降次序分类.int Kruskal(EDGE *es, NODE *set, int length, ED

3、GE *st,int num)功能: 对有length条权值大于0的边,最小生成树中有num条边的连通图, 应用Kruskal算法生成最小生成树, 最小生成树的边存储在数组st中.void Output(EDGE *st, int n)功能: 输出最小生成树的各条边.三、 测试结果测试数据和结果1测试数据和结果2附：程序模块的源代码#include#include#define N 100int length;typedef struct int num; int tag; NODE;typedef struct int cost; int node1; int node2; EDGE;NOD

4、E setN; /* 节点集, n为连通网的节点数 */EDGE esN; /* 边集, m为连通网的边数 */EDGE stN; /* 最小生成树的边集 */int InsertSort(EDGE *dat,int n) int i,item,j,m,h; for(i=0;in;i+) item=dati.cost; m=dati.node1; h=dati.node2; if(i=0) j=0; datj.cost=item; else j=i-1; while(item=0) datj+1.cost=datj.cost; datj+1.node1=datj.node1; datj+1.n

5、ode2=datj.node2; j-; datj+1.cost=item; datj+1.node1=m; datj+1.node2=h; printf(权值排序结果(升序)：n); for(i=0;i=0) i=seti.tag; j=elem; while(j!=i) k=setj.tag; setj.tag=i; j=k; return i; int Union( NODE *set,int elem1, int elem2) int m,n,sum; m=Find(set,elem1); n=Find(set,elem2); sum=setm.tag+setn.tag; if(set

6、m.tagsetn.tag) setn.tag=sum; setm.tag=n; else setm.tag=sum; setn.tag=m; int Ququanzhi(EDGE *es,int n) int i,j=0,len;EDGE bN; for(i=0;i0) bj.cost=esi.cost; bj.node1=esi.node1; bj.node2=esi.node2; j+; len=j; printf(n); for(i=0;ilen;i+) esi.cost=bi.cost; esi.node1=bi.node1; esi.node2=bi.node2; printf(n

7、); return len; int Kruskal(EDGE *es, NODE *set, int length, EDGE *st,int num) int i,j,k=1,m,n,mincost=0; st0.cost=es0.cost; st0.node1=es0.node1; st0.node2=es0.node2; m=Find(set,st0.node1); n=Find(set,st0.node2); Union(set,m,n); mincost+=es0.cost; for(i=1;ilength;i+) /*找其他边*/ m=Find(set,esi.node1); n

8、=Find(set,esi.node2); if(m!=n) Union(set,m,n); stk.cost=esi.cost; stk.node1=esi.node1; stk.node2=esi.node2; mincost+=esi.cost; k+; if(k=num) break; printf(n最小权值边和：mincost=%dn,mincost); printf(n最小树的边数：%dnn,k); return k; void Output(EDGE *st, int n) int i; printf(最小生成树的为：nn); for(i=0;in;i+) printf(树边%

9、d :%3d%d=%dn,i+1,sti.node1+1,sti.node2+1,sti.cost); int main() int i,j,k=0,L,temp,len;NODE *p,*q; textbackground(BLUE); textcolor(YELLOW); system( graftabl 935 );/*显示中文必须的代码*/ clrscr(); printf(请输入结点个数：); scanf(%d,&length); for(i=0;ilength;i+) seti.num=i; seti.tag=-1; printf(请输入边的权值，若不相邻则输入-1n); for(i=0;ilength;i+) for(j=i+1;jlength;j+) printf(边：%d%d=,i+1,j+1); scanf(%d,&esk.cost); esk.node1=i; esk.node2=j; k+; temp=k; L=Ququanzhi(es,temp);/*提出权值大于0的边数*/ InsertSort(es,L); /*将权值递增排列*/ printf(n); len=K