实验四----图的遍历与应用(广度优先遍历)

实验四 图的遍历与应用一、 实验目的1掌握图的含义；2 掌握用邻接矩阵和邻接表的方法描述图的存储结构；3 理解并掌握深度优先遍历和广度优先遍历的存储结构。二、 实验要求1 认真阅读和掌握本实验的参考程序。2 按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。3 保存程序的运行结果，并结合程序进行分析。三、 实验内容 以下参考程序是按邻接表的方法创建图，然后用深度优先遍历方法遍历图。请认真理解程序，然后实现图的广度优先遍历。广度优先遍历：具体实验的详细代码：#define MaxVerNum 100 /* 最大顶点数为*/#define MAXSIZE 100typedef enum False,True boolean;#include stdio.h#include stdlib.htypedef int DataType;boolean visitedMaxVerNum;typedef struct /*定義一個隊列*/ DataType dataMAXSIZE; int front,rear;SeqQueue,*PSeqQueue;PSeqQueue Init_SeqQueue() /*隊列初始化*/ PSeqQueue Q; Q=(PSeqQueue)malloc(sizeof(SeqQueue); if(Q) Q-front=0; Q-rear=0; return Q;int In_SeqQueue(PSeqQueue Q,DataType x) /*入隊操作*/ if(Q-rear+1)%MAXSIZE=Q-front) printf(隊滿); return -1; else Q-rear=(Q-rear+1)%MAXSIZE; Q-dataQ-rear=x; return 1; int Empty_SeqQueue(PSeqQueue Q) /*判斷隊空*/ if(Q&Q-front=Q-rear) return (1); else return (0);int Out_SeqQueue(PSeqQueue Q,DataType *x) /*出對操作*/ if(Empty_SeqQueue(Q) printf(隊空); return -1; else Q-front=(Q-front+1)%MAXSIZE; *x=Q-dataQ-front; return 1; typedef struct node /* 表结点*/int adjvex;/* 邻接点域,一般是放顶点对应的序号或在表头向量中的下标*/char Info; /*与边(或弧)相关的信息*/struct node * next; /* 指向下一个邻接点的指针域*/ EdgeNode; typedef struct vnode /* 顶点结点*/ char vertex; /* 顶点域*/EdgeNode * firstedge; /* 边表头指针*/ VertexNode; typedef struct VertexNode adjlistMaxVerNum; /* 邻接表*/int n,e; /* 顶点数和边数*/ ALGraph; /* ALGraph是以邻接表方式存储的图类型*/void Visit(DataType w) printf (%d,w);/建立一个无向图的邻接表存储的算法如下：void CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/int i,j,k;/*int N,E;*/EdgeNode *p;printf(请输入顶点数和边数：);scanf(%d %d,&G-n,&G-e); printf(n=%d,e=%dnn,G-n,G-e);getchar();for(i=0;in;i+) /* 建立有n个顶点的顶点表*/printf(请输入第%d个顶点字符信息(共%d个)：,i+1,G-n);scanf(%c,&(G-adjlisti.vertex); /* 读入顶点信息*/getchar();G-adjlisti.firstedge=NULL; /* 顶点的边表头指针设为空*/for(k=0;ke;k+) /* 建立边表*/printf(请输入边对应的顶点序号(共%d个)：,2*G-e);scanf(%d %d,&i,&j);/* 读入边的顶点对应序号*/p=(EdgeNode *)malloc(sizeof(EdgeNode); / 生成新边表结点p p-adjvex=j; /* 邻接点序号为j */p-next=G-adjlisti.firstedge;/* 将结点p插入到顶点Vi的链表头部*/G-adjlisti.firstedge=p; printf(n图已成功创建!对应的邻接表如下：n);for(i=0;in;i+)p=G-adjlisti.firstedge;printf(%c-,G-adjlisti.vertex);while(p!=NULL)printf( %c ,G-adjlistp-adjvex.vertex);p=p-next;printf(n);printf(n); /*CreateALGraph*/int FirstAdjVertex(ALGraph *g,int v)/找图g中与顶点v相邻的第一个顶点 if(g-adjlistv.firstedge!=NULL) return (g-adjlistv.firstedge)-adjvex;else return 0;int NextAdjVertex(ALGraph *g ,int vi,int vj )/找图g中与vi相邻的，相对相邻顶点vj的下一个相邻顶点EdgeNode *p;p=g-adjlistvi.firstedge;while( p!=NULL & p-adjvex!=vj) p=p-next;if(p!=NULL & p-next!=NULL) return p-next-adjvex;else return 0;void BFS(ALGraph *G,int v) /*從v出發按廣度優先遍歷圖G；使用輔助隊列Q和訪問標誌數組visited*/ EdgeNode *p; int u,w; PSeqQueue Q; /*定義一個隊列*/ Q=Init_SeqQueue(); /*置空的隊列Q*/ Visit(v); /*訪問v，注意Visit函數和visited數組的區別*/ visitedv=True; /*把訪問標誌置True*/ In_SeqQueue(Q,v); /*v入隊列*/ while(!Empty_SeqQueue(Q) Out_SeqQueue(Q,&u); /*出隊列*/ for(p=G-adjlistu.firstedge;p;p=p-next) w=p-adjvex; if(!visitedw) Visit(w); visitedw=True; In_SeqQueue(Q,w); /*u的尚未訪問的鄰接頂點w入隊列Q*/ /*BFS*/void BFStraverse(ALGraph G) int v; for(v=0;vG.n;v+) visitedv=False;