资源描述：
《实验四----图的遍历与应用(广度优先遍历).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验四图的遍历与应用一、实验目的1．掌握图的含义；2．掌握用邻接矩阵和邻接表的方法描述图的存储结构；3．理解并掌握深度优先遍历和广度优先遍历的存储结构。二、实验要求1．认真阅读和掌握本实验的参考程序。2．按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。3．保存程序的运行结果，并结合程序进行分析。三、实验内容以下参考程序是按邻接表的方法创建图，然后用深度优先遍历方法遍历图。请认真理解程序，然后实现图的广度优先遍历。广度优先遍历：具体实验的详细代码：#defineMaxVerNum100/*最大顶点数为*/#defineMAXSIZE100type
2、defenum{False,True}boolean;#include"stdio.h"#include"stdlib.h"typedefintDataType;booleanvisited[MaxVerNum];typedefstruct/*定義一個隊列*/{DataTypedata[MAXSIZE];intfront,rear;}SeqQueue,*PSeqQueue;PSeqQueueInit_SeqQueue()/*隊列初始化*/{PSeqQueueQ;Q=(PSeqQueue)malloc(sizeof(SeqQueue));if(Q){Q->f
3、ront=0;Q->rear=0;}returnQ;}intIn_SeqQueue(PSeqQueueQ,DataTypex)/*入隊操作*/{if((Q->rear+1)%MAXSIZE==Q->front){printf("隊滿");return-1;}else{Q->rear=(Q->rear+1)%MAXSIZE;Q->data[Q->rear]=x;return1;}}intEmpty_SeqQueue(PSeqQueueQ)/*判斷隊空*/{if(Q&&Q->front==Q->rear)return(1);elsereturn(0);}int
4、Out_SeqQueue(PSeqQueueQ,DataType*x)/*出對操作*/{if(Empty_SeqQueue(Q)){printf("隊空");return-1;}else{Q->front=(Q->front+1)%MAXSIZE;*x=Q->data[Q->front];return1;}}typedefstructnode/*表结点*/{intadjvex;/*邻接点域,一般是放顶点对应的序号或在表头向量中的下标*/charInfo;/*与边(或弧)相关的信息*/structnode*next;/*指向下一个邻接点的指针域*/}Edge
5、Node;typedefstructvnode/*顶点结点*/{charvertex;/*顶点域*/EdgeNode*firstedge;/*边表头指针*/}VertexNode;typedefstruct{VertexNodeadjlist[MaxVerNum];/*邻接表*/intn,e;/*顶点数和边数*/}ALGraph;/*ALGraph是以邻接表方式存储的图类型*/voidVisit(DataTypew){printf("%d",w);}//建立一个无向图的邻接表存储的算法如下：voidCreateALGraph(ALGraph*G)/*建立有
6、向图的邻接表存储*/{inti,j,k;/*intN,E;*/EdgeNode*p;printf("请输入顶点数和边数：");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].fir
7、stedge=NULL;/*顶点的边表头指针设为空*/}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的链表头部*/G->adjlist[i].fi
8、rstedge=p;}printf("图已成功创建!对应的邻接
