数据结构实验六图

《数据结构实验六图》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验六图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先搜索方法3、理解图的应用方法二、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include#defineN20#defineTRUE1#defineFALSE0intvisited[N];typedefstruct/*队列的定义*/{intdata[N];intfront,rear;}queue;typedefstruct/*图的邻接矩阵*/{intvexnum,arcnum;charvexs[N];intarcs[

2、N][N];}graph;voidcreateGraph(graph*g);/*建立一个无向图的邻接矩阵*/voiddfs(inti,graph*g);/*从第i个顶点出发深度优先搜索*/voidtdfs(graph*g);/*深度优先搜索整个图*/voidbfs(intk,graph*g);/*从第k个顶点广度优先搜索*/voidtbfs(graph*g);/*广度优先搜索整个图*/voidinit_visit();/*初始化访问标识数组*/voidcreateGraph(graph*g)/*建立一个无向图的邻接矩阵*/{inti,j;cha

3、rv;g->vexnum=0;g->arcnum=0;i=0;printf("输入顶点序列(以#结束)：");while((v=getchar())!='#'){g->vexs[i]=v;/*读入顶点信息*/i++;}g->vexnum=i;/*顶点数目*/for(i=0;ivexnum;i++)/*邻接矩阵初始化*/for(j=0;jvexnum;j++)g->arcs[i][j]=0;printf("输入边的信息：");scanf("%d,%d",&i,&j);/*读入边i,j*/while(i!=-1)/*读入i,

4、j为－1时结束*/{g->arcs[i][j]=1;g->arcs[j][i]=1;scanf("%d,%d",&i,&j);}}voiddfs(inti,graph*g)/*从第i个顶点出发深度优先搜索*/{intj;printf("%c",g->vexs[i]);visited[i]=TRUE;for(j=0;jvexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j]))dfs(j,g);}voidtdfs(graph*g)/*深度优先搜索整个图*/{inti;printf("从顶点%C开始深

5、度优先搜索序列：",g->vexs[0]);for(i=0;ivexnum;i++)if(visited[i]!=TRUE)dfs(i,g);}voidbfs(intk,graph*g)/*从第k个顶点广度优先搜索*/{inti,j;queueqlist,*q;q=&qlist;q->rear=0;q->front=0;printf("%c",g->vexs[k]);visited[k]=TRUE;q->data[q->rear]=k;q->rear=(q->rear+1)%N;while(q->rear!=q->front){i=q-

6、>data[q->front];q->front=(q->front+1)%N;for(j=0;jvexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j])){printf("%c",g->vexs[j]);visited[j]=TRUE;q->data[q->rear]=j;q->rear=(q->rear+1)%N;}}}voidtbfs(graph*g)/*广度优先搜索整个图*/{inti;printf("从顶点%C开始广度优先搜索序列：",g->vexs[0]);for(i=0;i

7、vexnum;i++)if(visited[i]!=TRUE)bfs(i,g);}voidinit_visit()/*初始化访问标识数组*/{inti;for(i=0;i

8、();tdfs(&ga);init_visit();tbfs(&ga);return0;}§根据右图的结构验证实验，输入：ABCDEFGH#0,10,