数据结构与算法专题实验报告2

数据结构论文  最短路径1 题目： 创建一个具有n（n≥1）个顶点的无向图的邻接矩阵，并对其按照“深度优先搜索”和“广度优先搜索”方法进行遍历。2 目标： 1.编写C程序予以实现。2.

数据结构论文 最短路径 1 题目： 创建一个具有n（n≥1）个顶点的无向图的邻接矩阵，并对其按 照“深度优先搜索”和“广度优先搜索”方法进行遍历。 2 目标： 1.编写C程序予以实现。 2.程序要求能输入图的顶点数、边数以及边的关系，并自动生成邻接矩阵。 3.结果输出邻接矩阵和遍历的路径。 4.熟悉无向图的两种遍历算法。 3 设计思想： 考虑用一个n维数组来存放无向图，若两个结点之间有边，则n维数组对 应下标的那个元素值为1，否则为0； 在输入图的顶点数和边数时我充分考虑了边界条件，顶点数G.vexnum在 [0，MAXV]范围内，边数在[0，G.vexnum*(G.vexnum-1)/2]范围内，在这个范围 内，程序继续向下执行，否则返回重新输入； 输出邻接矩阵的实质是输出n维数组，我用两重循环来实现； 深度优先遍历我采用迪杰特斯拉算法，不过要在此算法中间加一个判断， 所有的结点是否都已经遍历过，如果是就退出，如果不是，则按顺序从序号小的 开始向大的寻找，找到一个没有遍历过的结点继续调用深度优先遍历算法； 广度优先遍历我采用了非递归算法，其实质和深度优先遍历算法相同； 在主函数中直接调用CreatGraph(G)，DispMatrix(G)，DepthDisp(G,v) ，WidthDisp(G)函数即可。 4 算法描述： step1 :设置无向图最多的顶点数//这个设置为了更好的输出邻接矩阵； step2: 定义无向图的数据结构；