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

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

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

2、0(22)三.程序源代码#indude#include#definem6#definen11typedefstruct{inti,t昭chars;}vertice;typedefstruct{intwbtggintweight;}edge;verticev[m];edgee[n];voidinititate();voidsort();voidchuli();intbiaoji(edge*s);voidprint();voidmain(){inititate();sort();chuliQ;pri

3、nt();voidinititate(){inti;printf(“输入图的％d个顶点:n,m);for(i=0;ia;j=s->b;if(v

4、[i].tag==O11v(j].tgg==O){v[i].t^g=1;v[i].t^g=1；s->t^g=1;return1;}return0;}voidprint(){inti,j=0;printf("最小生成树的边为：");for(匸0;inre[i]^e[i].b);j++；}printf(Hn)；}voidsort(){edges;intij;for(i=0;i

5、if(e[i].weight>e(j].weight){s=e[i];e[i]=eg];e[j]=s;}}}}voidchuli(){inti,j=0;edge*s;for(i=0;i<2-3><2-4><4-6><5-6>Pressanykeytocontinue