最短路径与最小生成树

《最短路径与最小生成树》由会员分享，可在线阅读，更多相关《最短路径与最小生成树（11页珍藏版）》请在装配图网上搜索。

1、精品资料，欢迎大家下载！键入文字数据结构实验报告姓名：邱金梁班级：rJBJava101学号：202107092137指导老师：杨关以上资料仅供参考，如有侵权，留言第一时间删除！时间：2021年6月13日一、最小生成树#include/头文件usingnamespacestd;#defineMAX_VERTEX_NUM20/最大结点数#defineMAX200typedefstructClose/结构体(charadjvex;intlowcost;Close,closeMAX_VERTEX_NUM;typedefstructArcNode(intadjvex;ArcNode*nextarc;in

2、tinfo;ArcNode;typedefstructVNode(chardata;ArcNode*firstarc;VNode,AdjListMAX_VERTEX_NUM;typedefstruct(AdjListverties;intvexnum,arcnum;ALGraph;ALGraphG;/对象GintLocateVek(ALGraph,char);/返回结点位置intminimum(close);/返回最小数voidMinSpanTree_PRIM(ALGraph,char);/最小生成树voidCreate(ALGraph&);/创立邻接表intmain()(chara;inti

3、=1;Create(G);/*for(inti=1;inextarc)coutG.vertiesi.data-adjvex.data=infoendl;*/while(i)(couta;MinSpanTree_PRIM(G,a);couti;return0;intLocateVek(ALGraphG,charu)(inti;for(i=1;i=G.vexnum;i+)if(u=G.vertiesi.data)returni;return-1;intminimum(closem)/返回最小数(inti=0,j,n=200;for(i=1;i=G.vexnum;i+)if(mi.lowcostn&

4、mi.lowcost!=0)(n=mi.lowcost;j=i;returnj;voidMinSpanTree_PRIM(ALGraphG,charu)(intj,k,a;closeclosedge;ArcNode*s,*p,*q;for(j=1;j=MAX_VERTEX_NUM;j+)closedgej.lowcost=MAX;/把所有值都赋为最大k=LocateVek(G,u);for(j=1;jnextarc)if(j=s-adjvex)closedgej.lowcost=s-info;break;closedgek.lowcost=0;cout最小生成树：;/查找并输出最小生成树for

5、(j=1;jG.vexnum;j+)k=minimum(closedge);cout(closedgek.adjvex,G.vertiesk.data);closedgek.lowcost=0;for(inti=1;inextarc)if(p-infoadjvex)closedgei.adjvex=G.vertiesk.data;closedgei.lowcost=p-info;coutendl;cout边及对应权值：=1;j-)if(closedgej.lowcost=0&G.vertiesj.data!=u)cout(closedgej.adjvex,G.vertiesj.datanext

6、arc)if(a-64=q-adjvex)coutinfoendl;voidCreate(ALGraph&G)inti,j,k,x;chara,b;ArcNode*s;coutG.vexnum;coutG.arcnum;cout输入顶点信息：endl;for(i=1;iG.vertiesi.data;G.vertiesi.firstarc=NULL;for(i=1;i=G.arcnum;i+)coutab;cinx;j=a-64;k=b-64;/将字符型转化成整数型s=newArcNode;s-info=x;s-adjvex=k;s-nextarc=G.vertiesj.firstarc;G.

7、vertiesj.firstarc=s;s=newArcNode;s-info=x;s-adjvex=j;s-nextarc=G.vertiesk.firstarc;G.vertiesk.firstarc=s;:、最短路径#include#include#include#includeusingnamespacestd;enumMarkUNVISITED,VISITED;typedefstructDocuNodeintn;Markm;DocuNode;typedefstructDocuintn;DocuNode*Node;int*edge;Docu;MarkgetMark(Docu*D,int

8、i)(returnD-Nodei.m;voidsetMark(Docu*D,intv,Markm)(D-Nodev.m=m;intfirst(Docu*D,intv)(inti;for(i=0;in;i+)if(D-edgevi)!=-1)returni;returni;intnext(Docu*D,intv,intw)(inti;for(i=w+1;in;i+)if(D-edgevi)!=-1)returni;returni;intweight(Docu*D,intv,intw)returnD-edgevw;intminVertex(Docu*D,int*B)inti,v;for(i=0;i

9、n;i+)if(getMark(D,i)=UNVISITED)v=i;break;for(i+;in;i+)if(getMark(D,i)=UNVISITED&(BiBv)&Bi!=-1)|(Bv=-1)v=i;returnv;voidDijkstra(Docu*D,int*B,ints)(inti,v,w;for(i=0;in;i+)(v=minVertex(D,B);if(Bv=-1)return;setMark(D,v,VISITED);for(w=first(D,v);wn;w=next(D,v,w)if(Bw(Bv+weight(D,v,w)|(Bw=-1)Bw=Bv+weight(

10、D,v,w);intmain()(Docu*D;ifstreamfin(Docu.txt);inti,j;D=(Docu*)malloc(sizeof(Docu);finD-n;/从文件中读取节点数D-Node=(DocuNode*)malloc(sizeof(DocuNode);for(i=0;in;i+)D-Nodei.m=UNVISITED;/将所有节点设为未被访问deD-edge=(int*)calloc(1,sizeof(int*)*D-n);if(!D-edge)/假设内存未分配成功couterror;for(i=0;in;i+)(D-edgei=(int*)calloc(1,si

11、zeof(int)*D-n);if(!D-edgei)/假设内存未分配成功couterror;for(i=0;in;i+)for(j=0;jn;j+)finD-edgeij;/从文件中读取边权值intstart,end;cout起点:start;cout终点:end;int*B;B=(int*)malloc(D-n*sizeof(int);for(i=0;in;i+)Bi=D-edgestarti;Dijkstra(D,B,start);coutBend;getch();return0;U5wrAdvDC:UsersAdministriC:UsersAdminis起点二占:qu八、418立d*FMWCEJ格式CO章看CO5-110320-1-1-1-15-1T2一1-11.5-1-1-1-111一1-1-1-1一1