离散数学大作业――编程实现最小生成树.doc

《离散数学大作业――编程实现最小生成树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学大作业——编程实现最小生成树学院：电子工程学院班级：学号：姓名：杨青锋一、最小生成树　概念：设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v,w]。所有生成树G’上各边权的总和最小的生成树称为G的最小生成树。二、prim算法（贪心思想）设图G=（V，E），其生成树的顶点集合为U。1.把v0放入U。2.在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。3.把2找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行2其算法的时间复杂度为O

2、(n^2)三、程序源代码#include#include#definem6#definen11typedefstruct{inti,tag;chars;}vertice;typedefstruct{inta,b,tag;intweight;}edge;verticev[m];edgee[n];voidinititate();voidsort();voidchuli();intbiaoji(edge*s);voidprint();voidmain(){inititate();

3、sort();chuli();print();}voidinititate(){inti;printf("输入图的%d个顶点:",m);for(i=0;i

4、ge*s){inti,j;i=s->a;j=s->b;if(v[i].tag==0

5、

6、v[j].tag==0){v[i].tag=1;v[i].tag=1;s->tag=1;return1;}return0;}voidprint(){inti,j=0;printf("最小生成树的边为：");for(i=0;i",e[i].a,e[i].b);j++;}printf("");}voidsort(){edges

7、;inti,j;for(i=0;ie[j].weight){s=e[i];e[i]=e[j];e[j]=s;}}}}voidchuli(){inti,j=0;edge*s;for(i=0;i

8、边为：<1-2><2-3><2-4><4-6><5-6>Pressanykeytocontinue