发布时间 : 星期三 文章数据结构与算法专题实验报告 - 图文更新完毕开始阅读
else if (s>=0&&s
cost[s][e =cost[e][s]=len; // 实现无向图的操作
i++; } else
cout<<\边值错误，请重新输入!\} }
void shortdjs() //寻找最短路径的算法函数的实现 {
int s[MAX];
int mindis,dis,i,j,v0=0,u; for(i=0;i dist[i]=cost[v0][i]; path[i].pnode[0]=v0; path[i].num=0; s[i]=0; } s[v0]=1; for(i=1;i mindis=up; for (j=1;j if(s[j]==0&&dist[j] { u=j; mindis=dist[j]; } s[u]=1; //当s[u]=1时表示权值为无穷大 for (j=1;j dis=dist[u]+cost[u][j]; if(dist[j]>dis) { dist[j]=dis; path[j].num++; path[j].pnode[path[j].num]=u; } } path[i].num++; path[i].pnode[path[i].num]=i; } } void dispath() // 输出最短路径 { int i,j; cout< cout< cout<<\ if(dist[i] cout< cout<<\for (j=0;j cout<<\} } void main () //主函数 { creatgraph(); //直接调用三个函数就行 shortdjs(); dispath(); } 返回 第4题 最短路径 1 题目： 创建一个具有n（n≥1）个顶点的无向图的邻接矩阵，并对其按照“深 度优先搜索”和“广度优先搜索”方法进行遍历。 2 目标： 1.编写C程序予以实现。 2.程序要求能输入图的顶点数、边数以及边的关系，并自动生成邻接矩阵。 3.结果输出邻接矩阵和遍历的路径。 4.熟悉无向图的两种遍历算法。 3 设计思想： 1． 考虑用一个n维数组来存放无向图，若两个结点之间有边，则n维数组对应下标的那个元素值为1，否则为0； 2． 在输入图的顶点数和边数时我充分考虑了边界条件，顶点数G.vexnum在[0，MAXV]范围内，边数在[0，G.vexnum*(G.vexnum-1)/2]范围内，在这个 范围内，程序继续向下执行，否则返回重新输入； 3． 4． 输出邻接矩阵的实质是输出 n维数组，我用两重循环来实现； 深度优先遍历我采用迪杰特斯拉算法，不过要在此算法中间加一个判断，所有的结点是否都已经遍历过，如果是就退出，如果不是，则按顺序从序号小的开始向大的寻找，找到一个没有遍历过的结点继续调用深度优先遍历算法； 5． 6． 广度优先遍历我采用了非递归算法，其实质和深度优先遍历算法相同； 在主函数中直接调用 CreatGraph(G)， DispMatrix(G) ， DepthDisp(G,v) ，WidthDisp(G)函数即可。 4 算法描述： step1:设置无向图最多的顶点数// 这个设置为了更好的输出邻接矩阵； step2: 定义无向图的数据结构； step3:实现生成无向图函数CreatGraph(G) a. 输入顶点数n，判断它是否在允许的范围内，不在则返回重新输入； b. 输入无向图的边数G.arcnum，判断它是否在允许的范围内，不在则返回重新输 入 ； c. 输入边，for语句(k=1 to G.arcnum){ 输入两顶点v,w，判断v!=w & 0 step4:实现输出邻接矩阵函数 DispMatrix(Graph &G) ， 双重for循环实 现输出无向图的邻接矩阵； step5:实现深度优先遍历的递归算法函数DepthDisp(Graph &G,int v) a. 从v开始遍历，设置计数器num=0 ，并置顶点v已访问； b. for语句（i=1 to G.vexnum）判断 G.arcs[v][i]!=0&&visited[i]==0， 如果是递归调用深度优先遍历的递归算法函数DepthDisp(G, i)，如果不是则退出； c. 用for和if 语句判断是否所有的顶点都已经遍历完，