资源描述：
《判别无向图中任意两个顶点之间是否存在长度为K的简单路径。.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、武汉理工大学《数据结构》课程设计目录一、问题描述………………………………………………2二、设计思路………………………………………………2三、测试用例设计…………………………………………3四、详细设计………………………………………………3五、调试分析………………………………………………5六、心得体会………………………………………………8七、参考文献………………………………………………10八、附录……………………………………………………10九、课程设计评定表………………………………………1514武汉理工大学《数据结构》课
2、程设计一、问题描述题目:判别无向图中任意两个顶点之间是否存在长度为K的简单路径。初始条件：（1）采用邻接表作为存储结构。（2）编写程序判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径。（3）测试用例自己设计。注释：简单路径，即其顶点序列中不含有重现的顶点二、设计思路l存储结构设计1.采用邻接表作为无向图的存储结构，即顶点序列用一维数组描述，每个顶点所连接的边用单链表存储。2.增设一个一维数组，用于存储搜索简单路径时所访问的节点。l主要算法设计步骤：1.创建无向图CreateMGaph(MGraph&G
3、)①输入无向图的顶点数、边数。②给各个顶点命名，采用字符型编号。③输入每条边所连接的两个顶点，即各顶点间的相通性初始化。④每输入一条边，则判断其合法性：In(SList&L,chara)。若输入的顶点对中出现了②中没有的新顶点，则提示相应的出错信息，重新输入一条新的边。2.打印出邻接表：voidprint(MGraphG)以每一个顶点14武汉理工大学《数据结构》课程设计为头指针，打印出与该顶点相邻的所有顶点。然后换行，顺次打印下面的顶点及其相邻点。3．搜索任意给出的两个顶点间是否存在长度为K的简单路径若搜索成功则返回
4、成功标志，否则返回失败标志：intSearch(MGraphG,intx,inty,intk)。三．测试用例设计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邻接表的存储表示#defineMAX_VERTEX_NUM20//宏定义，最大顶点数typedefstructArcNode{//边表结点intadjv
5、ex;structArcNode*nextarc;}ArcNode;typedefstructVNode{//头结点chardata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intn,e;}MGraph;//无向图14武汉理工大学《数据结构》课程设计4.1.2标记访问过的顶点数组intvisited[MAX_VERTEX_NUM];//访问标志函数4.1.3存储已访问过的顶点的数组intpath[MAX
6、_VERTEX_NUM];4.2主要函数声明4.2.1创建无向图voidCreateMGaph(MGraph&G)4.2.2寻找各个顶点的位置charGetValue(MGraphG,inti)4.2.3判断新输入的顶点是否在图中intIsIn(MGraphG,charm)4.2.4返回顶点的值charGetValue(MGraphG,inti)4.2.5打印出邻接表voidprint(MGraphG)4.2.6查找两顶点m，n之间是否存在长度为k的简单路径intSearch(MGraphG,intx,inty,in
7、tk,intvisited[],intpath[],intd)4.3主程序intmain(){cout<<"--------------创建无向图------------"<>m>>n；
8、14武汉理工大学《数据结构》课程设计cout<<"请输入想寻找的简单路径的长度：";cin>>k;Search(G,x,y,k,visited,path,-1)；return0;}五、调试分析5.1程序的运行与调试5.1.1设计程序所应考虑的因素该程序所要执行的操作是比较简单的，但细到微处却有很多要考虑的因素，如果不面面俱到，考虑全面，则会使运
