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

武汉理工大学《数据结构》课程设计 1 目录 一、问题描述………………………………………………2 二、设计思路………………………………………………2 三、测试用例设计…………………………………………3 四、详细设计………………………………………………3 五、调试分析………………………………………………5 六、心得体会………………………………………………8 七、参考文献………………………………………………10 八、附录……………………………………………………10 九、课程设计评定表………………………………………15 武汉理工大学《数据结构》课程设计 2 一、 问题描述 题 目: 判别无向图中任意两个顶点之间是否存在长度为K 的简单路径。 初始条件： （1） 采用邻接表作为存储结构。 （2） 编写程序判别无向图中任意给定的两个顶点之间是否存在一条长度为k 的简单路径。 （3） 测试用例自己设计。 注释：简单路径，即其顶点序列中不含有重现的顶点 二、设计思路  存储结构设计 1. 采用邻接表作为无向图的存储结构，即顶点序列用一维数组描述，每个顶点所连接的边用单链表存储。 2. 增设一个一维数组，用于存储搜索简单路径时所访问的节点。  主要算法设计 步骤： 1. 创建无向图CreateMGaph(MGraph &G) ① 输入无向图的顶点数、边数。 ② 给各个顶点命名，采用字符型编号。 ③ 输入每条边所连接的两个顶点，即各顶点间的相通性初始化。 ④ 每输入一条边，则判断其合法性：In(SList &L,char a)。 若输入的顶点对中出现了②中没有的新顶点，则提示相应的出错信息，重新输入一条新的边。 2. 打印出邻接表：v oid print(MGraph G) 以每一个顶点为头指针，打印出与该顶点相邻的所有顶点。然后换行，武汉理工大学《数据结构》课程设计 3 顺次打印下面的顶点及其相邻点。 3．搜索任意给出的两个顶点间是否存在长度为K 的简单路径 若搜索成功则返回成功标志，否则返回失败标志：int Search(MGraph G,int x ,int y ,int k)。 三．测试用例设计 1.输入的顶点数：5 2.输入的边数;6 3.各顶点名称：A，B，C，D，E 4.各条边所对应的顶点对：（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 //宏定义，最大...