版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、/*分别利用prim算法和kruskal算法实现求图的最小生成树*/#include#include#define MaxVertexNum 12#define MaxEdgeNum 20#define MaxValue 1000typedef int Vertextype;typedef int adjmatrixMaxVertexNumMaxVertexNum;typedef Vertextype vexlistMaxVertexNum;int visitedMaxVertexNum=0;struct edgeElemint fromvex;int endvex;int weight;ty
2、pedef struct edgeElem edgesetMaxVertexNum;void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)int i,j,k,w;printf(输入%d个顶点数据,n);for(i=0;in;i+) scanf(%d,&GVi);for(i=0;in;i+) for(j=0;jn;j+) if(i=j) GAij=0; else GAij=MaxValue;printf(输入%d条无向带权边,e);for(k=0;ke;k+)scanf(%d%d%d,&i,&j,&w);GAij=GAji=w;void
3、 Creat_edgeset(vexlist GV,edgeset GE,int n,int e)int i,j,k,w;printf(输入%d个顶点数据,n);for(i=0;in;i+) scanf(%d,&GVi);printf(输入%d条无向带权边,e);for(k=0;ke;k+) scanf(%d%d%d,&i,&j,&w); GEk.fromvex=i; GEk.endvex=j; GEk.weight=w;void output_edgeset(edgeset GE,int e)int k;for(k=0;ke;k+)printf(%d %d %d,GEk.fromvex,GE
4、k.endvex,GEk.weight);printf(n);void prim(adjmatrix GA,edgeset CT,int a,int n)int i,j,t,k,w,min,m;struct edgeElem x;for(i=0;in;i+)if(ia) CTi-1.fromvex=a; CTi-1.endvex=i; CTi-1.weight=GAai; for(k=1;kn;k+) min=MaxValue; m=k-1; for(j=k-1;jn-1;j+) if(CTj.weightmin)min=CTj.weight;m=j; x=CTk-1;CTk-1=CTm;CT
5、m=x; j=CTk-1.endvex; for(i=k;in-1;i+)t=CTi.endvex;w=GAjt; if(wCTi.weight) CTi.weight=w; CTi.fromvex=j; void kruskal(edgeset GE,edgeset C,int n) int i,j,k,d; int m1,m2; adjmatrix s;for(i=0;in;i+) for(j=0;jn;j+) if(i=j) sij=1;else sij=0; k=1;d=0;while(kn) for(i=0;in;i+) if(siGEd.fromvex=1) m1=i; if(si
6、GEd.endvex=1) m2=i;if(m1!=m2)Ck-1=GEd;k+;for(j=0;jn;j+)sm1j=sm1j|sm2j;sm2j=0;d+;void main()int n,e;vexlist GV;adjmatrix GA;edgeset GE,C;printf(输入图的顶点数和边数:);scanf(%d%d,&n,&e);Creat_adjmatrix( GV, GA, n, e);printf(利用prim算法从0点出发求图的最小生成树:n);prim(GA,GE,0,n);output_edgeset( GE, n-1);printf(输入图的顶点数和边数:);sc
7、anf(%d%d,&n,&e);Creat_edgeset( GV,GE,n, e);printf(利用kruskal算法从0点出发求图的最小生成树:n);kruskal( GE, C, n);output_edgeset( C, n-1);最小生成树(prim算法和kruskal算法)收藏 最小生成树(prim算法)用最小生成树的解决的经典问题:若要在n个城市间建设通信网路,给出任意两个城市的距离和每米通信网路的造价,问怎样设计网络可以使网路的造价最小。在n个点中间最多可以有n(n-1)/2条无向边存在,最多可以有n(n-1)个有向边存在。只要n-1边就可以将n个点连接成一个生成树。Prim
8、算法:自己感觉很像缔结斯特拉算法。步骤:1. 随便找一个点,设置为已使用。2. 找已使用点和未使用点之间所有连线中最短的一条,然后将这条连线中未使用的点列入已使用。3. 如此反复1,2直到说有的点变成已使用点。/map中存储着全图,n(n+1)条线的情况.num表示点的个数,treemap是生成的树void prim(int mapN,int num,int treemapN)/treemap初始化为0. bool *used=new boolnum;/用来判断该点是否已经用过 int count=num;/用来计数 int point=0;/用来代表即将加入的点的上一个点 int willu
9、se=0;/用来代表即将加入的点 int mindage;/用来代表当前的最小路程 /初始化used used0=true; for(int m=1;mnum;m+) usedm=false; while(count-) .mindage=; for(int i=0;inum;i+) . for(int j=0;jnum;j+) . if(usedj)/find a used point . for(int k=0;knum;k+) . if(!usedk&mapjkmindage)/find unused point . point=j;willuse=k;mindage=mapjk; tr
10、eemappointwilluse=treemapwillusepoint=1;/将point到willuse这两个点联通 usedwilluse=1;/将willuse加入已用集合. kruskal算法:步骤:1. 将每一个点看成一个连通分量,在连通分量间找最短的边,然后连到一起,那么在图中就有n-1个连通分量了。2. 在现在的连通分量的情况下找任意两个连通分量间最短的边中最短的边,将这两个连通分量连到一起,这样往复知道所有的点在同一个联通分量中就可得到最小生成树。代码如下:void kruskal(int mapN,int num,int treemapN)/treemap初始化为0. i
11、nt *flag=new intnum;/用来判断连个点是不是在同一个连通分量里 int count=num-1;/用来为边计数要n-1条边 int mindis,number1,number2,from,to;/中间变量 for(int i=0;inum;i+) flagi=i+1;/将每个点的划分成一个连通分量 while(count-) . mindis=;/用来记录当前最小的边 for(int j=0;jnum;j+) . for(int g=0;gnum;g+) . if(j=g) continue; /当两个点不在同一个连通分量中并且他们的边比较小时. else if(flagj!
12、=flagg&mapjgflagg?flagj:flagg); number2=(flaggflagj?flagj:flagg); from=j; to=g; treemapfromto=treemaptofrom=1; /为1即连通 for(int m=0;mnum;m+) . if(flagm=number2) flagm=number1; 测试用语句:#include using namespace std;#define N 6/语句插入位子.int main(). int map66=. .100,6,1,5,100,100, .6,100,5,100,3,100, .1,5,100,5,6,4, .5,100,5,100,100,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年航空业人才需求与职业成长报告
- 2026年珠宝首饰行业报告:消费升级与市场细分分析
- 2026年社群运营策略与企微工具优化报告
- 2026年生产性服务业创新发展报告
- 2026年大数据行业应用报告及市场增长趋势研究
- 2026年珠宝首饰行业消费者需求变化与市场前景报告001
- 2026年个护家电行业产业链分析报告
- 2026年电子商务行业成本控制与盈利能力分析报告
- 2026年汽车4S店连锁加盟模式分析报告
- 2026年能源行业智能安防与运维一体化发展报告
- 广西广电网络公司招聘笔试题库2026
- 低空经济与管理专业无人机行业就业
- 检测机构盲样管理制度(3篇)
- 机动车检测站质量手册2026版-符合CNAS认可准则
- 病区卫生间使用管理制度
- 2025年大学(应用语言学)社会语言学期末试题及答案
- 2025广东揭阳揭东农商银行小微金融部人才招聘(公共基础知识)测试题附答案解析
- 肾动脉栓塞介入术
- 人教版(2024)七年级上册美术第四单元《情境交融-舞台美术设计》教案(2课)
- 军队职工抚恤管理办法
- GB/T 39542.3-2025技术制图活动铅笔第3部分:黑铅芯HB铅芯弯曲强度
评论
0/150
提交评论