《数据结构》实验报告3-龚慧

《《数据结构》实验报告3-龚慧》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》实验报告班级：13南航网络学号:058913221164姓名：龚慧实验名称：实验三图的遍历操作实验时间：2013.7.4.实验地点：流-425、427指导教师：尚鲜连实验目的与要求：分别采用邻接矩阵和邻接表存储结构，完成图的深度优先遍历（DFS）和广度优先遍历（BFS）的操作。搞清楚BFS算法中队列的作用。实验内容：1.以邻接矩阵为存储结构的深度优先搜索遍历算法2.以邻接表为存储结构的深度优先搜索遍历算法3.以邻接矩阵为存储结构的广度优先搜索遍历算法4.以邻接表为存储结构的深度优先搜索遍历算法算法设计（流程图）：算法实现程序（源

2、代码）：（见源程序文件，附在本文后）上机调试情况（调试数据、调试过程中遇到的问题及解决方法）：由于对邻接矩阵和邻接表存储结构两个概念比较模糊，导致不会写算法，经过上网查询资料以后，对两个算法的概念以及步骤有了初步了解。在查阅诸多算法以后，问题得以解决。测试数据和输出结果：附：源代码（注：此处贴上源代码）（1）邻接表表示的深度优先搜索算法 void DFS(ALGraph *G，int i){  //以vi为出发点对邻接表表示的图G进行深度优先搜索 EdgeNode *p； printf("visit vertex：%c"，G->adjlis

3、t[i].vertex)；//访问顶点vi  visited[i]=TRUE； //标记vi已访问 p=G->adjlist[i].firstedge；//取vi边表的头指针 while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex  if (!visited[p->adjvex])//若vi尚未被访问 DFS(G，p->adjvex);//则以Vj为出发点向纵深搜索  p=p->next；//找vi的下一邻接点 }  }//DFS（2）邻接矩阵表示的深度优先搜索算法 void DFSM(MGraph *G，int i) 

4、{ //以vi为出发点对邻接矩阵表示的图G进行DFS搜索，设邻接矩阵是0,l矩阵 int j；    printf("visit vertex：％c"，G->vexs[i])；//访问顶点vi  visited[i]=TRUE；    for(j=0；jn；j++) //依次搜索vi的邻接点    if(G->edges[i][j]==1&&!visited[j])    DFSM(G，j)//(vi，vj)∈E，且vj未访问过，故vj为新出发点 }//DFSM（3）邻接矩阵表示的图的广度优先搜索算法   void BFSM(MGr

5、aph *G，int k)  {//以vk为源点对用邻接矩阵表示的图G进行广度优先搜索    int i，j；   CirQueue Q；   InitQueue(&Q)；  printf("visit vertex：%c"，G->vexs[k])； //访问源点vk    visited[k]=TRUE；   EnQueue(&Q，k)；    while(!QueueEmpty(&Q)){       i=DeQueue(&Q)； //vi出队     for(j=0;jn;j++)//依次搜索vi的邻接点vj         

6、  if(G->edges[i][j]==1&&!visited[j]){//vi未访问               printf("visit vertex：％c"，G->vexs[j])；//访问vi               visited[j]=TRUE；   EnQueue(&Q，j)；//访问过的vi人队                  }      }//endwhile  }//BFSM (4)邻接表表示图的广度优先搜索算法   void BFS(ALGraph*G，int k) {//以vk为源点对用邻接表表示的图G进

7、行广度优先搜索 int i； CirQueue Q； //须将队列定义中DataType改为int EdgeNode *p； InitQueue(&Q)；//队列初始化      //访问源点vk  printf("visit vertex：％e"，G->adjlist[k].vertex)；     visited[k]=TRUE；  EnQueue(&Q，k)；//vk已访问，将其人队。（实际上是将其序号人队）while(!QueueEmpty(&Q)){//队非空则执行         i=DeQueue(&Q)； //相当于vi出队

8、  p=G->adjlist[i].firstedge； //取vi的边表头指针 while(p){//依次搜索vi的邻接点vj(令p->adjvex=j)   if(!visi