资源描述：
《实验四 图的实现及遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验四图的实现及遍历题目：（1）采用邻接矩阵作为图的存储结构，完成有向图和无向图的DFS和BFS操作；（2）采用邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。班级：0421001姓名：杨欢学号：2010211971完成日期：2011.12.3一、需求分析掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。实验要求：1、分析、理解程序。2、调试程序。设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优
2、先遍历）的操作。二、概要设计1，分析理解，调试程序2，设计一个无向图G，如右图所示3，设计一个有向图K，如右下图所示4，分别对无向图G和有向图K进行邻接矩阵存储和邻接链表存储，再分别进行深度优先遍历和广度优先遍历。V6V4V5V7V2V3V1V0Vo图K的示例附加程序代码邻接矩阵作为存储结构的程序示例#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定义最大顶点数typedefstruct{charvexs[MaxVertexNum];//顶点表intedges[MaxVertexNum][M
3、axVertexNum];//邻接矩阵，可看作边表intn,e;//图中的顶点数n和边数e}MGraph;//用邻接矩阵表示的图的类型//=========建立邻接矩阵=======voidCreatMGraph(MGraph*G){inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);//输入顶点数和边数scanf("%c",&a);printf("InputVertexstring:");for(i=0;in;i++){scanf("
4、%c",&a);G->vexs[i]=a;//读入顶点信息，建立顶点表}for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=0;//初始化邻接矩阵printf("Inputedges,CreatAdjacencyMatrix");for(k=0;ke;k++){//读入e条边，建立邻接矩阵scanf("%d%d",&i,&j);//输入边（Vi，Vj）的顶点序号G->edges[i][j]=1;G->edges[j][i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句}}//=
5、========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(MGraph*G,inti){//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵intj;printf("%c",G->vexs[i]);//访问顶点Vivisited[i]=TRUE;//置已访问标志for(j=0;jn;j++)//依次搜索Vi的邻接点if(G->edges[
6、i][j]==1&&!visited[j])DFSM(G,j);//（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点}voidDFS(MGraph*G){inti;for(i=0;in;i++)visited[i]=FALSE;//标志向量初始化for(i=0;in;i++)if(!visited[i])//Vi未访问过DFSM(G,i);//以Vi为源点开始DFS搜索}//===========BFS：广度优先遍历=======voidBFS(MGraph*G,intk){//以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索inti,j
7、,f=0,r=0;intcq[MaxVertexNum];//定义队列for(i=0;in;i++)visited[i]=FALSE;//标志向量初始化for(i=0;in;i++)cq[i]=-1;//队列初始化printf("%c",G->vexs[k]);//访问源点Vkvisited[k]=TRUE;cq[r]=k;//Vk已访问，将其入队。注意，实际上是将其序号入队while(cq[f]!=-1){//队非空则执行i=cq[f];f=f+1;//Vf出队for(j=0;jn;j++)//依次Vi的邻接点Vjif(G->edge
8、s[i][j]==1&&!visite
