数据结构课程设计实验报告-无向图、哈密尔顿回路、最短路径.doc

数据结构实验报告实验题目: 数据结构课程设计（无向连通网的问题求解）实验目的：通过本次课程设计，掌握无向连通网的性质，熟悉其关于最短哈密尔顿回路以及最短路径的求解。实验内容：对于具有n(n=10)个顶点的无向连通网，设计一个算法（1）找出网中最短的哈密尔顿回路；（2）找出任意两个顶点之间的最短路径，须经过指定1个或2个顶点。一、需求分析1.本演示程序中，输入的无向连通网为任意给定的，输入时应该给定无向连通网的大小、范围，即顶点数以及边数，而输出有三个问题的求解答案，分别输出其路径及权值大小。2.本演示程序为人机对话，用户可以按照提示进行输入，然后选择需要求解的问题，则有结果输出。3.程序执行的命令包括：（1）构建无向连通网（2）选择求解问题序号（3）第一个为求解最短哈密顿回路（3）第二个为求解任意两点之间的最短路径，须经过指定1个顶点（4）第三个为求解任意两点之间的最短路径，须经过指定2个顶点（5）结束4.测试数据：（1）请输入顶点数和边数(输入格式为:顶点数,边数):11,17(2) 请输入顶点信息(输入格式为:顶点号):0 1 2 3 4 5 6 7 8 9 10(3) 请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:):0,6,50,7,40,4,31,4,11,6,81,3,22,4,62,3,32,10,73,5,85,10,35,9,86,7,17,8,47,9,68,9,29,10,6(4) 请选择操作:如果选择输入为1，结果为：最短哈密尔顿回路为：0-6-7-8-9-5-10-2-3-1-4-0权值为：5+1+4+2+8+3+7+3+2+1+3=39如果选择输入为2，结果为：请输入指定起始点：0请输入指定终点：6请输入路径经过指定的顶点：10输出路径是：0-4-2-10-9-7-6起始点为0终点为6的经过指定点10的最短路径为：29如果选择输入为3，结果为:请输入指定起始点：4请输入指定终点：1请输入路径经过指定的顶点一：8请输入路径经过指定的顶点二：3输出路径是：4-1-3-1-6-7-8-7-6-1起始点为4终点为1的经过指定点一8以及指定点二3的最短路径为：31如果选择输入为0，结果为:结束.二 概要设计为了实现上述操作，无向连通网用邻接矩阵存储结构，解决哈密顿回路问题时应用栈。1. 基本操作：void hamidun(mgraph &g)求解最短哈密尔顿回路int lujing(mgraph g,int v0,int vn,int dist,int prev)求解指定两点之间的最短路径void ShowPath(mgraph g,int v0,int u,int *dist,int *prev)输出所求最短路径所经过的顶点void zhiding1(mgraph g,int v0,int vn,int vx)求解任意两点之间的最短路径，须经过指定1个顶点void zhiding2(mgraph g,int v0,int vn,int vx1,int vx2)求解任意两点之间的最短路径，须经过指定2个顶点2. 本程序包含六个模块：(1)主程序模块（2）求解最短哈密尔顿回路模块（3）求解指定两点之间的最短路径模块（4）输出所求最短路径所经过的顶点模块（5）求解任意两点之间的最短路径，须经过指定1个顶点模块（6）求解任意两点之间的最短路径，须经过指定2个顶点模块（7）模块调用图主程序模块求解任意两点之间的最短路径，须经过指定2个顶点模块求解任意两点之间的最短路径，须经过指定1个顶点模块求解最短哈密尔顿回路模块求解指定两点之间的最短路径模块输出所求最短路径所经过的顶点模块三 详细设计1.元素类型，结点类型和指针类型：/图中的节点数#define M 50/哈密顿回路最长值#define MAX_LENGTH 1024/单边最大值#define MAX_SIDE_LENGTH 30/节点信息结构struct Nodeint level; /位于生成树的第几层int dot; /第几个节点;typedef structint edgeMM;int N,e;int vexsM;mgraph;Node s99;/记忆最短路径Node aShortNodeM;/记忆当前路径Node aNodeM;Node node;2.每个模块的分析：(1)主程序模块int main()int i,j,k,w,v0,vn,vx,vx1,vx2,m;mgraph g;printf(请输入顶点数和边数(输入格式为:顶点数,边数):n);scanf(%d,%d,&(g.N),&(g.e);getchar();printf(请输入顶点信息(输入格式为:顶点号):n);for(i=0;ig.N;i+)scanf(%d,&(g.vexsi);getchar();for(i=0;ig.N;i+)for(j=0;jg.N;j+)g.edgeij=999; /认为999时两顶点之间无边printf(请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:):n);for(k=0;kg.e;k+)scanf(%d,%d,%d,&i,&j,&w);g.edgeij=g.edgeji=w;while(1)printf(*n); printf(t1.求解最短哈密尔顿回路.n); printf(t2.求解任意两个顶点之间的经过指定一顶点的最短路径.n); printf(t3.求解任意两个顶点之间的经过指定两顶点的最短路径.n); printf(t0.结束操作.n); printf(*n); printf(请选择操作:); scanf(%d,&m); switch(m)case 1:printf(最短哈密尔顿回路为:);hamidun(g);break;case 2:printf(*经过指定一点最短路径:*n);printf(请输入指定起始点:n); scanf(%d,&v0); printf(请输入指定终点:n); scanf(%d,&vn); printf(请输入路径经过指定的顶点:n); scanf(%d,&vx); zhiding1(g,v0,vn,vx); printf(n);break;case 3:printf(*经过指定两点最短路径:*n); printf(请输入指定起始点:n); scanf(%d,&v0); printf(请输入指定终点:n); scanf(%d,&vn); printf(请输入路径经过指定的顶点一:n); scanf(%d,&vx1); printf(请输入路径经过指定的顶点二:n); scanf(%d,&vx2); zhiding2(g,v0,vn,vx1,vx2);printf(n);break;case 0:exit(0); default: printf(输出出错！n); getchar(); getchar(); return 0;（2）求解最短哈密尔顿回路模块void hamidun(mgraph &g)int i,j;/记忆最短路径Node aShortNodeM;/记忆当前路径Node aNodeM;for(i=0;i=1)len=len+g.edgeaNodepo-1.dotaNodepo.dot;if(lenlength | po=g.N-1|g.edgeaNodepo-1.dotaNodepo.dot=999)isEnd=true;if(isEnd)/完整回路if(po=g.N-1)len=len+g.edge0aNodeg.N-1.dot;if(lenlength)length=len;/更改当前最短路径for(i=0;i=node.level;i-)len=len-g.edgeaNodei-1.dotaNodei.dot;aNodei.dot=-1;aNodei.level=-1;/更新当前层po=node.level;elsepo+; /下一层/将下一层节点入栈for(i=0;ig.N;i+)/判断下一个压栈的节点在不在当前路径bool isIn=false;for(j=0;jg.N;j+)if(i=aNodej.dot)isIn=true;break;/不在当前路径if(!isIn)node.dot=i;node.level=po;top+;stop=node;for(i=0;i,aShortNodei.dot); printf(%d,aShortNode0.dot); printf(n);printf(权值为:); for(i=1;ig.N;i+)printf(%d+,g.edgeaShortNodei-1.dotaShortNodei.dot);printf(%d=%d,g.edge0aShortNodeg.N-1.dot,length);printf(n);（3）求解指定两点之间的最短路径模块int lujing(mgraph g,int v0,int vn,int dist,int prev)int i; int j; int maxint = 65535;/定义一个最大的数值，作为不相连的两个节点的代价权值 int *s ;/定义具有最短路径的节点子集s s = (int *)malloc(sizeof(int) *g.N); /初始化最小路径代价和前一跳节点值 for (i= 0; i g.N; i+) disti = g.edgev0i; si = 0; if (disti = maxint) previ = 0; else previ = v0; distv0 = 0; sv0 = 1;/源节点作为最初的s子集 for (i = 1; i g.N; i+) int temp = maxint; int u = v0; /加入具有最小代价的邻居节点到s子集 for (j = 1; j =g.N; j+) if (!sj) & (distj temp) u = j; temp = distj; su = 1; /计算加入新的节点后，更新路径使得其产生代价最短 for (j = 1; j =g.N; j+) if (!sj) & (g.edgeuj maxint) int newdist = distu + g.edgeuj; if (newdist =1;j-)printf(%d-,wayj);（5）求解任意两点之间的最短路径，须经过指定1个顶点模块void zhiding1(mgraph g,int v0,int vn,int vx)int s1,s2,distance;int *dist;/最短路径代价 int *prev;/前一跳节点空间dist = (int *)malloc(sizeof(int)*g.N); prev = (int *)malloc(sizeof(int)*g.N);printf(输出路径是:);s1=lujing(g,v0,vx,dist,prev); /计算v0到vx的最短路径ShowPath(g,v0,vx,dist,prev);s2=lujing(g,vx,vn,dist,prev); /计算vx到vn的最短路径ShowPath(g,vx,vn,dist,prev);printf(%d,vn);printf(n);distance=s1+s2; /合起来便是v0到vn的最短路径printf(起始点为%d终点为%d的经过指定点%d的最短路径为:%d,v0,vn,vx,distance);（6）求解任意两点之间的最短路径，须经过指定2个顶点模块void zhiding2(mgraph g,int v0,int vn,int vx1,int vx2)int s11,s12,s13,s21,s22,s23,distance1,distance2,distance;int *dist;/最短路径代价 int *prev;/前一跳节点空间dist = (int *)malloc(sizeof(int)*g.N); prev = (int *)malloc(sizeof(int)*g.N);printf(输出路径是:);s11=lujing(g,v0,vx1,dist,prev);s12=lujing(g,vx1,vx2,dist,prev);s13=lujing(g,vx2,vn,dist,prev);distance1=s11+s12+s13; /计算从v0经vx1经vx2到vn的最短路径s21=lujing(g,v0,vx2,dist,prev);s22=lujing(g,vx2,vx1,dist,prev);s23=lujing(g,vx1,vn,dist,prev);distance2=s21+s22+s23; /计算从v0经vx2经vx1到vn的最短路径if(distance1distance2) /判断两种情况，选择小的输出distance=distance1;s11=lujing(g,v0,vx1,dist,prev);ShowPath(g,v0,vx1,dist,prev); s12=lujing(g,vx1,vx2,dist,prev);ShowPath(g,vx1,vx2,dist,prev); s13=lujing(g,vx2,vn,dist,prev);ShowPath(g,vx2,vn,dist,prev);printf(%d,vn);printf(n);elsedistance=distance2;s21=lujing(g,v0,vx2,dist,prev);ShowPath(g,v0,vx2,dist,prev); s22=lujing(g,vx2,vx1,dist,prev);ShowPath(g,vx2,vx1,dist,prev); s23=lujing(g,vx1,vn,dist,prev);ShowPath(g,vx1,vn,dist,prev);printf(%d,vn);printf(n);printf(起始点为%d终点为%d的经过指定点一%d以及指定点二%d的最短路径为:%d,v0,vn,vx1,vx2,distance);int main()3. 函数调用关系图：Void hamidun()void zhiding2()void zhiding1()void ShowPath()int lujing()4完整的程序：(见源文件).四 使用说明、测试分析及结果1程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：请输入顶点数和边数(输入格式为:顶点数,边数):11,17 请输入顶点信息(输入格式为:顶点号):0 1 2 3 4 5 6 7 8 9 10 请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:):0,6,50,7,40,4,31,4,11,6,81,3,22,4,62,3,32,10,73,5,85,10,35,9,86,7,17,8,47,9,68,9,29,10,62.测试结果：请选择操作:如果选择输入为1，结果为：最短哈密尔顿回路为：0-6-7-8-9-5-10-2-3-1-4-0权值为：5+1+4+2+8+3+7+3+2+1+3=39如果选择输入为2，结果为：请输入指定起始点：0请输入指定终点：6请输入路径经过指定的顶点：10输出路径是：0-4-2-10-9-7-6起始点为0终点为6的经过指定点10的最短路径为：29如果选择输入为3，结果为:请输入指定起始点：4请输入指定终点：1请输入路径经过指定的顶点一：8请输入路径经过指定的顶点二：3输出路径是：4-1-3-1-6-7-8-7-6-1起始点为4终点为1的经过指定点一8以及指定点二3的最短路径为：31如果选择输入为0，结果为:结束.3运行界面构建无向连通网选择1，求解最短哈密尔顿回路选择2，求解任意两点之间的最短路径，须经过指定1个顶点模块选择3. 求解任意两点之间的最短路径，须经过指定2个顶点模块五、实验总结本次课程设计实验耗费时间比较多，需要准备的内容比较多，前期一直在研究算法，为后期的编写程序做好了准备，通过本次课设，对于无向图的最短路径的求解有了很深的体会，尤其是和离散数学的内容联系在一起，加强了学科之间的联系，在本次试验中，由于前期准备充足，在编写过程中没有遇到太大的问题，一些小问题经仔细检查后都得到了解决，通过本次实验，我更熟悉无向图的问题的求解，对于以后学习帮助很大。教师评语：实验成绩：#include#include /图中的节点数#define M 50/哈密顿回路最长值#define MAX_LENGTH 1024/单边最大值#define MAX_SIDE_LENGTH 30/节点信息结构struct Nodeint level; /位于生成树的第几层int dot; /第几个节点;typedef structint edgeMM;int N,e;int vexsM;mgraph;Node s99;int top=-1;void hamidun(mgraph &g)int i,j;/记忆最短路径Node aShortNodeM;/记忆当前路径Node aNodeM;for(i=0;i=1)len=len+g.edgeaNodepo-1.dotaNodepo.dot;if(lenlength | po=g.N-1|g.edgeaNodepo-1.dotaNodepo.dot=999)isEnd=true;if(isEnd)/完整回路if(po=g.N-1)len=len+g.edge0aNodeg.N-1.dot;if(lenlength)length=len;/更改当前最短路径for(i=0;i=node.level;i-)len=len-g.edgeaNodei-1.dotaNodei.dot;aNodei.dot=-1;aNodei.level=-1;/更新当前层po=node.level;elsepo+; /下一层/将下一层节点入栈for(i=0;ig.N;i+)/判断下一个压栈的节点在不在当前路径bool isIn=false;for(j=0;jg.N;j+)if(i=aNodej.dot)isIn=true;break;/不在当前路径if(!isIn)node.dot=i;node.level=po;top+;stop=node;for(i=0;i,aShortNodei.dot); printf(%d,aShortNode0.dot); printf(n);printf(权值为:); for(i=1;ig.N;i+)printf(%d+,g.edgeaShortNodei-1.dotaShortNodei.dot);printf(%d=%d,g.edge0aShortNodeg.N-1.dot,length);printf(n);int lujing(mgraph g,int v0,int vn,int dist,int prev)int i; int j; int maxint = 65535;/定义一个最大的数值，作为不相连的两个节点的代价权值 int *s ;/定义具有最短路径的节点子集s s = (int *)malloc(sizeof(int) *g.N); /初始化最小路径代价和前一跳节点值 for (i= 0; i g.N; i+) disti = g.edgev0i; si = 0; if (disti = maxint) previ = 0; else previ = v0; distv0 = 0; sv0 = 1;/源节点作为最初的s子集 for (i = 1; i g.N; i+) int temp = maxint; int u = v0; /加入具有最小代价的邻居节点到s子集 for (j = 1; j =g.N; j+) if (!sj) & (distj temp) u = j; temp = distj; su = 1; /计算加入新的节点后，更新路径使得其产生代价最短 for (j = 1; j =g.N; j+) if (!sj) & (g.edgeuj maxint) int newdist = distu + g.edgeuj; if (newdist =1;j-)printf(%d-,wayj);/求解任意两个顶点之间的经过指定一顶点的最短路径void zhiding1(mgraph g,int v0,int vn,int vx)int s1,s2,distance;int *dist;/最短路径代价 int *prev;/前一跳节点空间dist = (int *)malloc(sizeof(int)*g.N); prev = (int *)malloc(sizeof(int)*g.N);printf(输出路径是:);s1=lujing(g,v0,vx,dist,prev); /计算v0到vx的最短路径ShowPath(g,v0,vx,dist,prev);s2=lujing(g,vx,vn,dist,prev); /计算vx到vn的最短路径ShowPath(g,vx,vn,dist,prev);printf(%d,vn);printf(n);distance=s1+s2; /合起来便是v0到vn的最短路径printf(起始点为%d终点为%d的经过指定点%d的最短路径为:%d,v0,vn,vx,distance);/求解任意两个顶点之间的经过指定两顶点的最短路径void zhiding2(mgraph g,int v0,int vn,int vx1,int vx2)int s11,s12,s13,s21,s22,s23,distance1,distance2,distance;int *dist;/最短路径代价 int *prev;/前一跳节点空间dist = (int *)malloc(sizeof(int)*g.N); prev = (int *)malloc(sizeof(int)*g.N);printf(输出路径是:);s11=lujing(g,v0,vx1,dist,prev);s12=lujing(g,vx1,vx2,dist,prev);s13=lujing(g,vx2,vn,dist,prev);distance1=s11+s12+s13; /计算从v0经vx1经vx2到vn的最短路径s21=lujing(g,v0,vx2,dist,prev);s22=lujing(g,vx2,vx1,dist,prev);s23=lujing(g,vx1,vn,dist,prev);distance2=s21+s22+s23; /计算从v0经vx2经vx1到vn的最短路径if(distance1distance2) /判断两种情况，选择小的输出distance=distance1;s11=lujing(g,v0,vx1,dist,prev);ShowPath(g,v0,vx1,dist,prev); s12=lujing(g,vx1,vx2,dist,prev);ShowPath(g,vx1,vx2,dist,prev); s13=lujing(g,vx2,vn,dist,prev);ShowPath(g,vx2,vn,dist,prev);printf(%d,vn);printf(n);elsedistance=distance2;s21=lujing(g,v0,vx2,dist,prev);ShowPath(g,v0,vx2,dist,prev); s22=lujing(g,vx2,vx1,dist,prev);ShowPath(g,vx2,vx1,dist,prev); s23=lujing(g,vx1,vn,dist,prev);ShowPath(g,vx1,vn,dist,prev);printf(%d,vn);printf(n);printf(起始点为%d终点为%d的经过指定点一%