判别无向图中任意两个顶点之间是否存在长度为K的简单路径

1、精选优质文档-倾情为你奉上目录一、问题描述2二、设计思路2三、测试用例设计3四、详细设计3五、调试分析5六、心得体会8七、参考文献10八、附录10九、课程设计评定表15一、 问题描述题 目: 判别无向图中任意两个顶点之间是否存在长度为K的简单路径。初始条件：（1） 采用邻接表作为存储结构。（2） 编写程序判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径。 （3） 测试用例自己设计。注释：简单路径，即其顶点序列中不含有重现的顶点二、设计思路l 存储结构设计1. 采用邻接表作为无向图的存储结构，即顶点序列用一维数组描述，每个顶点所连接的边用单链表存储。2. 增设一个一维数组，用于存

2、储搜索简单路径时所访问的节点。l 主要算法设计步骤：1. 创建无向图CreateMGaph(MGraph &G) 输入无向图的顶点数、边数。 给各个顶点命名，采用字符型编号。 输入每条边所连接的两个顶点，即各顶点间的相通性初始化。 每输入一条边，则判断其合法性：In(SList &L,char a)。若输入的顶点对中出现了中没有的新顶点，则提示相应的出错信息，重新输入一条新的边。2. 打印出邻接表：void print(MGraph G) 以每一个顶点为头指针，打印出与该顶点相邻的所有顶点。然后换行，顺次打印下面的顶点及其相邻点。3搜索任意给出的两个顶点间是否存在长度为K的简单

3、路径若搜索成功则返回成功标志，否则返回失败标志：int Search(MGraph G,int x,int y,int k)。三测试用例设计1.输入的顶点数：52.输入的边数;63.各顶点名称：A，B，C，D，E4.各条边所对应的顶点对：（A，D）（A，E）（D，E）（D，B）（C，B）（C，E）5.输入要寻找的顶点对及其简单路径长度分别为：（A，D），4四、详细设计4.1 存储结构说明4.1.1邻接表的存储表示#define MAX_VERTEX_NUM 20 /宏定义，最大顶点数typedef struct ArcNode /边表结点int adjvex; struct ArcNode *

4、nextarc;ArcNode;typedef struct VNode /头结点char data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef structAdjList vertices; int n,e; MGraph; /无向图4.1.2 标记访问过的顶点数组int visitedMAX_VERTEX_NUM; /访问标志函数4.1.3 存储已访问过的顶点的数组int pathMAX_VERTEX_NUM;4.2 主要函数声明4.2.1 创建无向图void CreateMGaph(MGraph &G)4.2.

5、2 寻找各个顶点的位置char GetValue(MGraph G,int i)4.2.3 判断新输入的顶点是否在图中int IsIn(MGraph G,char m)4.2.4 返回顶点的值char GetValue(MGraph G,int i)4.2.5 打印出邻接表 void print(MGraph G)4.2.6 查找两顶点m，n之间是否存在长度为k的简单路径 int Search(MGraph G,int x,int y,int k,int visited,int path,int d)4.3 主程序 int main()cout<<"-创建无向图-&quo

6、t;<<endl<<endl; CreateMGaph(G); cout<<"-打印邻接表-"<<endl<<endl; print(G); cout<<"-寻找长度为K的简单路径-"<<endl<<endl; cout<<"寻找路径的两个顶点：" cin>>m>>n； cout<<"请输入想寻找的简单路径的长度：" cin>>k; Search(G,x,y,k

7、,visited,path,-1)； return 0;五、调试分析5.1 程序的运行与调试5.1.1 设计程序所应考虑的因素该程序所要执行的操作是比较简单的，但细到微处却有很多要考虑的因素，如果不面面俱到，考虑全面，则会使运行过程过于简单，程序的功能不够完美。比如在输入顶点序列的时候，如果先前输入的点序列中已经存在当前读入的点，则要有相应的冲突提示；在输入边的条数时，若边的条数操过了无向图所应有的最大值，则也要提示出错信息，重新输入边数；在生成边的时候，若出现了顶点序列中没有的新顶点，则提示出错，并返回重新输入合法的边；在搜索路径时，搜索成功要输出相应的路径顶点序列，搜索失败时要给出出错信息

8、。5.1.2 程序的调试 在程序执行过程中，主要出现的问题如下：1. 由于程序中所需要的变量很多，则导致有些漏定义或定义重复，造成程序执行出错。如error C2065: 'i' : undeclared identifier。2. 对于循环语句continue,break的用法还不是很熟练，造成死循环或者无法执行语句。3. 函数的类型定义与返回值不匹配，导致出错。如主函数定义为void型，而却有返回值return 0，则提示出错信息main' : void' function returning a value。4. 定义数组时要预先给出存储空间大小，否则无法

9、生成数组。如定义int visited，出错error LNK2001: unresolved external symbol "int * visited" (?visited3PAHA)。5. 对于循环操作，如while，for，要给出跳出循环的控制条件，否则会出现死循环而导致运行刷屏。6. 对于条件语句，要中和考虑到所有可能情况，否则会导致执行时彼错输此，明显逻辑错误，不真实。以上错误，经过仔细的检查与调试后，最终得到了正确的输出。5.1.3 程序的运行结果程序调试完成后，点击按钮运行，结果如下图所示：按照【测试用例】依次输入信息，得到如下图所示的运行结果：5.2 算

10、法时间复杂度分析1创建无向图的时间复杂度（CreateMGaph(MGraph &G)）：O（e） 该算法对每条边执行一次输入操作，故其算法的时间复杂度为O（e），其中e为边的数目。2. 打印邻接表的时间复杂度（print(MGraph G)）：O （n）该算法对每个顶点都输出与之相邻的所有顶点，故其时间复杂度为O （n），n为顶点个数。3. 判断两个顶点之间是否存在路径长度为K的时间复杂度（ Search(MGraph G,int x,int y,int k,int visited,int path,int d)）：O（1）该算法的执行次数直接由路径长度K控制，故其时间复杂度为常量。

11、5.3 算法的现态与优化设想5.3.1 算法的现态1. 对输入的边数有控制条件，不允许其超过最大边数。2. 在初始化边和选择操作边时，若顶点对中出现了顶点序列中没有的新顶点，则给出相应提示。3. 对于搜索成功，能够顺次输出所走路径；对于搜索失败，也能提示相应操作。4. 对于所走路径，顺利将其转化为顶点名称的形式输出，简单明了。5.3.2 算法的优化设想虽然当前采用的算法其基本功能都能很好的实现，但仍存在一些不足，有待进一步的改进与优化，主要设想如下：1. 增设函数，使其能够对点进行增加和删除操作。2. 增设函数，使其能够对边进行增加和删除操作。3. 对于搜索不成功的顶点对，能够返回他们之间各种

12、所存在路径长度的顶点序列。4. 对于初始化边操作，若输入的顶点对已经存在，则应给与提示，令其重新输入。六、心得体会数据结构是一门设计性相当强的科目，它需要把算法思想转变为源程序代码上机调试,把理论知识变为实践能力，可以说，学好了数据结构，就掌握了编程的基本思想与求解一个实际问题的具体思路了。从第一堂课开始，杜老师就为我们阐述了它的重要性。刚开始的几周学习中，真的压力好大，由于数据结构的教学思想与传统的科目的课本所传授的思路截然不同，所以思路转变要花费我们好长一段时间来适应。它对我们来说具有一定的难度，然而它又是其它编程语言的一门基础学科，所以我要努力来学好。对于课程中所要求的每一个实验，我都尽

13、量自己独立完成，自己实在做不出来的再去向同学请教，把每一个实验都弄懂。 刚拿到课程设计题目的时候觉得没多大难度，就是求无向图中任意两顶点见是否存在长度为K的简单路径。于是就没在意，想想就是把书上的存储结构写上来，再加上一个搜寻路径的函数就结束了。当拿起题目，开始着手做的时候，才发现要考虑的因素实在是太多了，搜索函数要用递归，输入的顶点的重复与否需要判断，输入的边是否有效也需要判断，如何进行整型地址与顶点名称间的转化，当新增一条边或新增一个顶点的时候图的变化，等等。于是，一下子，脑子混了，思路乱了，不知从何下手，写出来的函数基本都有错误，有些调试了好多遍也无法正常运行，真的好让人郁闷。于是向别人

14、请教，经过与同学的悉心讨论，费了九牛二之力后，终于调试成功了。 而且，在调试过程中，由于C+里检查错误都是用英文来显示出来的，有些出错信息不知道是什么意思，很难理解，耗费了一些时间。这都是平时做实验的次数少了的缘故，所以以后要自觉的给自己找些小算法来自己尝试着写写了。值得指出的是，经过这次课程设计，现在已经可以读懂很多错误在英文里的提示了，而且编程思想得到了很大提高，此次课程设计基本上是凭自己的能力独立完成的，思路很清晰，在编程的过程中不断的发现不足，再一步步的改进与完善。 总的来说，很感谢此次课程设计的安排，它让我进一步加深了对算法的了解与设计，编程能力与独立解决问题的能力也有所提升，收获颇

15、丰。通过这次的课程设计，现在真正的明白了一些代码的应用，每个程序都有一些共同点，比如通用的结构，相似的格式，要学会融会贯通，举一反三。只要努力去学习，就会灵活的去应用它。在以后的学习中，我会多花时间在实验上的，因为只有自己真正动手实践了、操作了，编程的能力与算法设计的能力才会发生质的转变。我会努力的！ 七、参考文献数据结构（C语言版）严蔚敏、吴伟民 清华大学出版社 .数据结构习题集（C语言版） 严蔚敏、吴伟民、米宁 清华大学出版社 .C+程序设计教程 闵联营、何克右 武汉理工大学出版社.数据结构习题与解析（第2版） 李春葆 清华大学出版社八、附录附录一（源程序代码清单）：#include<

16、;iostream.h>#include<stdio.h> #include<stdlib.h> /图的邻接表存储表示#define MAX_VERTEX_NUM 20 /最大顶点数typedef struct ArcNode /边表结点int adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针ArcNode;typedef struct VNode /头结点char data; /节点名字 ArcNode *firstarc; /指向第一条依附该节点的弧的指针VNode,AdjListMAX_VERTEX

17、_NUM; typedef structAdjList vertices; int n,e; /图的当前顶点数和弧数MGraph; /无向图 int pathMAX_VERTEX_NUM; /存储访问过的顶点 int visitedMAX_VERTEX_NUM; /访问标志函数 int LocateVex(MGraph G, char v) /返回字符v在图中的位置 int i;for(i=0;i<G.n;i+)if(G.verticesi.data=v) return i;break;return -1; char GetValue(MGraph G,int i) /得到顶点Vi re

18、turn (i>=0 && i<G.n) ? G.verticesi.data : NULL; int IsIn(MGraph G,char m) /判断字符m是否在图中 int p; for(p=0;p<G.n;p+)if(G.verticesp.data=m)return p;return -1;void CreateMGaph(MGraph &G) /创建无向图 int i,k; char m,n; ArcNode *s;cout<<"请输入无向图的顶点数n（n<=20）和弧数e（e<n*（n-1）/2）：&qu

19、ot;<<endl;cin>>G.n>>G.e;while(G.n>20)cout<<"您输入的顶点数大于20，请重新输入！"<<endl;cin>>G.n>>G.e;while(G.e>(G.n-1)*G.n/2)cout<<"您输入的边数大于"<<(G.n-1)*G.n/2<<"，请重新输入边数！"<<endl;cin>>G.e;cout<<"您输入的合法

20、顶点数和边数为："<<G.n<<" ， "<<G.e<<endl; cout<<"请输入各顶点的名称："<<endl; for(i=0;i<G.n;i+) /建立顶点表cin>>G.verticesi.data; /读入顶点信息 G.verticesi.firstarc=NULL; /初始化为空表cout<<"请输入各条边所连接的顶点信息："<<endl; for(k=0;k<G.e;k+) /建立边表co

21、ut<<"请输入第"<<k+1<<"条边："cin>>m>>n;/读入该条边所连接的两个顶点（m，n）int p,q;p=IsIn(G,m);q=IsIn(G,n);while(p=-1|q=-1) cout<<"该条边不合法，请重新输入！"<<endl;cin>>m>>n; p=IsIn(G,m); q=IsIn(G,n);int a,b;a=LocateVex(G, m);b=LocateVex(G, n);s=(ArcNo

22、de*)malloc(sizeof(ArcNode); /生成边表结点s->adjvex=a; s->nextarc= G.verticesb.firstarc; G.verticesb.firstarc=s; /将顶点m插入到顶点n之后 s=(ArcNode*)malloc(sizeof(ArcNode); s->adjvex=b;s->nextarc= G.verticesa.firstarc; G.verticesa.firstarc=s; /将顶点n插入到顶点m之后cout<<endl;void print(MGraph G) /打印邻接表 int

23、i,j; ArcNode *p; for(i=0;i< G.n;i+) cout<<G.verticesi.data<<" " p=G.verticesi.firstarc; while(p!=NULL) j=p->adjvex; cout<<G.verticesj.data<<" " p=p->nextarc; cout<<endl;int Search(MGraph G,int x,int y,int k,int visited,int path,int d) /k是要判断

24、的长度，x,y为给定的两个点的地址，G为无向图； int n,i; ArcNode *p; visitedx=1; d+; pathd=x; if(x=y && d=k) return 1; p=G.verticesx.firstarc; while(p !=NULL) n=p->adjvex ; if(visitedn=0) if(i=Search(G,n,y,k,visited,path,d)=1) return i; p=p->nextarc ; visitedx=0; d-; return 0;int main() for( int i=0;i<MAX_VERTEX_NUM;i+) /