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

《数据结构与算法专题实验报告2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构论文 最短路径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]

2、范围内，在这个范围内，程序继续向下执行，否则返回重新输入；输出邻接矩阵的实质是输出n维数组，我用两重循环来实现；深度优先遍历我采用迪杰特斯拉算法，不过要在此算法中间加一个判断，所有的结点是否都已经遍历过，如果是就退出，如果不是，则按顺序从序号小的开始向大的寻找，找到一个没有遍历过的结点继续调用深度优先遍历算法；广度优先遍历我采用了非递归算法，其实质和深度优先遍历算法相同；在主函数中直接调用CreatGraph(G)，DispMatrix(G)，DepthDisp(G,v)，WidthDisp(G)函数即可。4算法描述：step1:设置无向图最多的顶点数//这个

3、设置为了更好的输出邻接矩阵；step2:定义无向图的数据结构；step3:实现生成无向图函数CreatGraph(G)a.输入顶点数n，判断它是否在允许的范围内，不在则返回重新输入；b.输入无向图的边数G.arcnum，判断它是否在允许的范围内，不在则返回重新输入；c.输入边，for语句(k=1toG.arcnum){输入两顶点v,w，判断v!=w&0

4、环实现输出无向图的邻接矩阵；step5:实现深度优先遍历的递归算法函数DepthDisp(Graph&G,intv)a.从v开始遍历，设置计数器num=0，并置顶点v已访问；b.for语句（i=1toG.vexnum）判断G.arcs[v][i]!=0&&visited[i]==0，如果是递归调用深度优先遍历的递归算法函数DepthDisp(G,i)，如果不是则退出；c.用for和if语句判断是否所有的顶点都已经遍历完，ifnum

5、算法函数DepthDisp(G,i)；step6:实现广度优先遍历的非递归算法函数WidthDisp(Graph&G)a.输入广度优先遍历的出发点m,判断0

6、hDisp(G)函数即可；5程序流程图：1．创建无向图函数的流程图如下：2．深度优先遍历函数实现的流程图如下：3．实现广度优先遍历的流程图如下：6源程序//二,不带权值的无向图的遍历:#include#defineMAXV20//定义顶点的最大个数structGraph//定义无向图的数据结构{intvexs[MAXV];intarcs[MAXV][MAXV];intvexnum,arcnum;};staticintvisited[MAXV];voidCreatGraph(Graph&G)//实现创建无向图的函数{inti,j,k,v,

7、w;cout<<"请输入顶点数：";cin>>G.vexnum;while(G.vexnum>MAXV){cout<<"图的顶点数超限，请重新输入：";//纠错功能cin>>G.vexnum;}cout<<"请输入边数：";cin>>G.arcnum;while(G.arcnum>G.vexnum*(G.vexnum-1)/2)//V个顶点最多V(V-1)/2个顶点{cout<<"图的边数超限，请重新输入：";cin>>G.arcnum;}for(i=0;i<=G.vexnum;i++)for(j=0;j<=G.vexnum;j++)G.arcs[i][j]=

8、0;for(k=1;k<=G.arcn