图的应用——深度优先遍历和广度优先遍历

《图的应用——深度优先遍历和广度优先遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、华北水利水电大学数据结构实验报告2013～2014学年第二学期2013级计算机科学与技术（专升本）专业班级：学号：姓名：实验四图的应用一、实验题目：图的应用——深度优先／广度优先搜索遍历二、实验内容：很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。要求：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。（注：学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接矩阵实现）提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入

2、的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。三、程序源代码：#include#include#include#defineMAX_VERTEX_NUM20typedefstructArcCell{intadj;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;}MGraph;typedefstructQue

3、ue{char*front;char*rear;}Queue;boolvisited[MAX_VERTEX_NUM]={false};voidInitQueue(Queue&Q){//初始化队列Q.front=Q.rear=(char*)malloc(MAX_VERTEX_NUM*sizeof(char));if(!Q.front)exit(0);}voidEnQueue(Queue&Q,charv){//入队列*Q.rear=v;Q.rear++;第4页共4页}voidDeQueue(Queue&Q,char&u){//出队列u=*Q.front;Q.front++;}boo

4、lQueueEmpty(QueueQ){//判定队列是否为空if(Q.rear-Q.front)returnfalse;returntrue;}intLocateVex(MGraphG,charv){//找出顶点v在图G中的位置并返回for(inti=0;i

5、数printf("开始输入顶点的值");getchar();for(i=0;i

6、;scanf("%c%c",&v1,&v2);getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);//确定顶点v1，v2在图G中的位置G.arcs[i][j].adj=1;G.arcs[j][i]=G.arcs[i][j];}return1;}intFirstAdjVex(MGraphG,intv){//for(inti=0;i

7、w+1;i=0;w=NextA