资源描述：
《实验五 图的创建与遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验五图的创建与遍历.一、实验目的1．掌握图的含义；2．掌握用邻接矩阵和邻接表的方法描述图的存储结构；3．理解并掌握深度优先遍历和广度优先遍历的存储结构。二、实验要求1．认真阅读和掌握本实验的参考程序。2．按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。3．保存程序的运行结果，并结合程序进行分析。三、实验内容以下参考程序是按邻接表的方法创建图，然后用深度优先遍历方法遍历图。请认真理解程序，然后实现图的广度优先遍历。参考程序:#defineMaxVerNum100/*最大顶点数为*/t
2、ypedefenum{False,True}boolean;#include"stdio.h"#include"stdlib.h"booleanvisited[MaxVerNum];typedefstructnode/*表结点*/{intadjvex;/*邻接点域,一般是放顶点对应的序号或在表头向量中的下标*/charInfo;/*与边(或弧)相关的信息*/structnode*next;/*指向下一个邻接点的指针域*/}EdgeNode;typedefstructvnode/*顶点结点*/{c
3、harvertex;/*顶点域*/EdgeNode*firstedge;/*边表头指针*/}VertexNode;typedefstruct{VertexNodeadjlist[MaxVerNum];/*邻接表*/intn,e;/*顶点数和边数*/}ALGraph;/*ALGraph是以邻接表方式存储的图类型*///建立一个无向图的邻接表存储的算法如下：voidCreateALGraph(ALGraph*G)/*建立有向图的邻接表存储*/{inti,j,k;intN,E;EdgeNode*p;p
4、rintf("请输入顶点数和边数：");scanf("%d%d",&G->n,&G->e);printf("n=%d,e=%d",G->n,G->e);getchar();for(i=0;in;i++)/*建立有n个顶点的顶点表*/{printf("请输入第%d个顶点字符信息(共%d个)：",i+1,G->n);scanf("%c",&(G->adjlist[i].vertex));/*读入顶点信息*/getchar();G->adjlist[i].firstedge=NULL;
5、/*顶点的边表头指针设为空*/}for(k=0;k<2*G->e;k++)/*建立边表*/{printf("请输入边对应的顶点序号(共%d个)：",2*G->e);scanf("%d%d",&i,&j);/*读入边的顶点对应序号*/p=(EdgeNode*)malloc(sizeof(EdgeNode));//生成新边表结点pp->adjvex=j;/*邻接点序号为j*/p->next=G->adjlist[i].firstedge;/*将结点p插入到顶点Vi的链表头
6、部*/G->adjlist[i].firstedge=p;}printf("图已成功创建!对应的邻接表如下：");for(i=0;in;i++){p=G->adjlist[i].firstedge;printf("%c->",G->adjlist[i].vertex);while(p!=NULL){printf("[%c]",G->adjlist[p->adjvex].vertex);p=p->next;}printf("");}printf("");}/*CreateA
7、LGraph*/intFirstAdjVertex(ALGraph*g,intv)//找图g中与顶点v相邻的第一个顶点{if(g->adjlist[v].firstedge!=NULL)return(g->adjlist[v].firstedge)->adjvex;elsereturn0;}intNextAdjVertex(ALGraph*g,intvi,intvj)//找图g中与vi相邻的，相对相邻顶点vj的下一个相邻顶点{EdgeNode*p;p=g->adjlist[vi].firsted
8、ge;while(p!=NULL&&p->adjvex!=vj)p=p->next;if(p!=NULL&&p->next!=NULL)returnp->next->adjvex;elsereturn0;}voidDFS(ALGraph*G,intv)/*从第v个顶点出发深度优先遍历图G*/{intw;printf("%c",G->adjlist[v].vertex);visited[v]=True;/*访问第v个顶点，并把访问标志置True*/for(w=FirstAdjVertex(G,v)
