资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
一、 实验内容: 考虑右边的无向图,设计算法输出从顶点a到顶点i的一条带权路径长度最短的简单路径。分析时间和空间复杂度。实验要求:采用递归或非递归的深度优先或广度优先遍历算法扩展实现。二、 算法思想:构造一个带权无向图,采用深度优先遍历的方法,每走到一个点就用visited做访问过的标记,这样循环递归找到顶点a到i的所有路径,再比较所有路径的长度,找到最短路径。三、 实验过程:#include#include#includeusing namespace std;#define MAX_VEX_NUM 20/最大顶点数vectorallPath; /向量,用来存放所有的顶点a到顶点i的路径vectorall;struct MGraphchar vexsMAX_VEX_NUM;/顶点向量/AdjMatrixint arcsMAX_VEX_NUMMAX_VEX_NUM;/邻接矩阵int vexnum,arcnum;MGraph G;/申明一个无向图的邻接矩阵类型int Locatevex(MGraph G,char v)/图的基本操作,寻找V的位置 int i=0;while(iG.vexnum&v!=G.vexsi) i+;if(iG.vexnum) return i;/查找成功则返回顶点的下标else return -1;int CreateUDG(MGraph&G)/数组邻接矩阵表示法构造无向图 char v1,v2; int weight;/权值 cout请输入图的顶点数和弧数G.vexnumG.arcnum; cout请输入顶点值endl; for(int i=0;iG.vexsi; for(int q=0;qG.vexnum;q+)/初始化邻接矩阵for(int p=0;pG.vexnum;p+) G.arcsqwwp=0;for(int k=0;kG.arcnum;k+)/构造邻接矩阵 cout输入该弧依附的顶点和权值:v1v2weight; int a=Locatevex(G,v1); int b=Locatevex(G,v2); G.arcsab=weight; G.arcsba=G.arcsab; for(int n=0;nG.vexnum;n+)/输出顶点 coutG.vexsn ; coutendl; coutendl;cout该图的邻接矩阵表示为: n;for(int x=0;x=G.vexnum;x+)/输出邻接矩阵 for(int y=0;yG.vexnum;y+) coutG.arcsxy ; coutendl;coutendl;coutendl;return 1;/CreateUDG void Minway(MGraph G,bool*visited,char vexs,int Long,char vb,string path) / if(vexs=vb) /递归结束条件 path=path+ +vexs; allPath.push_back(path); /将路径放入向量中 all.push_back(Long); /将路径长放入对应向量中 cout路径:path长度:Longendl;else path=path+ +vexs; int i=Locatevex(G,vexs); visitedi=true; for(int j=0;jG.vexnum;j+) if(!visitedj)&(G.arcsij!=0) Minway(G,visited,G.vexsj,Long+G.arcsij,vb,path); /递归调用自身 visitedi=false; /退出递归前清除访问记录 void CountMinway(MGraph G) /该函数调用递归部分实现递归 char va, vb; string path; /存放路径 coutvavb; coutendl; int i=Locatevex(G,va); bool visited100; for(int j=0;jG.vexnum;j+) visitedj=false; /初始化访问记录,全部未访问过 visitedi=true; /起点顶点设为访问过 int Long=0; path+=va; for(j=0;jG.vexnum;j+) if(G.arcsij!=0) Long=G.arcsij; Minway (G,visited,G.vexsj,Long,vb,path); /调用递归部分 coutendl; void Minway()/输出最短路径int min=10000;for(int i=0;iallPath.size();i+) if(allimin) min=alli;for(int j=0;jallPath.size();j+) if(allj=min) cout 最短路径:allPathj长度:alljendl;coutendl;void main() CreateUDG(G);/建图 CountMinway(G);/找出所有路径 Minway(); /输出最短路径四、 实验结果:五、 小结:
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号