1、精選優質文檔-傾情為你奉上 上機實驗報告 學 院： 計算機與信息技術學院專 業： 計算機科學與技術(師范）課程名稱： 數據結構實驗題目：廣度優先遍歷（鄰接表）班級序號： 師范1班學 號： 1 學生姓名： 鄧雪指導教師： 楊紅穎完成時間： 2015年12月25號1、 實驗目的：1掌握圖的基本概念和鄰接表存儲結構。 2掌握圖的鄰接表存儲結構的算法實現。  3掌握圖在鄰接表存儲結構上遍歷算法的實現。二、實驗環境： Windows 8.1 Microsoft Visual c+ 6.02、 實驗內容及要求：編寫圖的廣度優先遍歷算法。四、概要設計：先定義圖的鄰接表數據，建立該圖的鄰接

2、表，然后在用子函數寫出廣度優先搜索遍歷的遍歷算法，最后用主函數調用它們。  實現廣度優先搜索遍歷可以利用隊列的原理。利用隊列先進先出的特性，并設置訪問標志實現連通圖的廣度優先搜索遍歷。  廣度優先搜索遍歷類似于樹的按層次遍歷，對于用鄰接表做存儲結構的圖，從某個給定頂點出發的圖的遍歷得到的訪問結點頂點次序，隨建立的鄰接表的不同而可能不同。  將每個結點的邊用一個單邊表鏈接起來組成一個整體。所有頭結點可看成一個一維數組，即鄰接表所有鏈表中結點數目的一半為圖中邊數。占用的存儲單元數目為n+2e。  抽象算法描述:  （1）訪問頂點i，并將其訪問標志置

3、為已被訪問，即visitedi=true。 （2）依次訪問與標點i有邊相連的所有頂點w1,w2-wt。（3）再按次序訪問與w1,w2-wt有邊相連且未曾訪問過的頂點。 （4）依此類推，直到圖中所有頂點都被訪問完。五、代碼：#include <stdio.h>#include <stdlib.h>#define maxsize 1024#define n 8#define e 9typedef char datatype;typedef char vextype;/定義結構體typedef structint datamaxsize;int front

4、,rear;sequeue;/定義結構體typedef struct nodedatatype adjvex;struct node *next;edgenode;/定義結構體typedef structvextype vertex; edgenode *link;vexnode;sequeue *Q;vexnode gan;int visitedn;sequeue *sq;/建立無向圖的鄰接表void CREATADJLIST(vexnode ga)int i,j,k;edgenode *s;printf("讀入樹的結點信息：");for(i=0;i<n;i+)ga

5、i.vertex=getchar();gai.link=NULL;printf("讀入邊（vi,vj）的頂點對序號：");for(k=0;k<e;k+)scanf("%d%d",&i,&j);s=(edgenode *)malloc(sizeof(edgenode);s->adjvex=j;s->next=gai.link;gai.link=s;s=(edgenode *)malloc(sizeof(edgenode);s->adjvex=i;s->next=gaj.link;gaj.link=s;/置空隊v

6、oid SETNULL(sequeue *sq)sq->front=maxsize-1;sq->rear=maxsize-1;/判隊空int EMPTY(sequeue *sq)if(sq->rear=sq->front)return 1;elsereturn 0;/入隊int ENQUEUE(sequeue *sq,datatype x)if(sq->front=(sq->rear+1)%maxsize)printf("queue is full");return NULL;elsesq->rear=(sq->rear+1)

7、%maxsize;sq->datasq->rear=x;return 1;/出隊datatype DEQUEUE(sequeue *sq)if(EMPTY(sq)printf("queue is empty");return NULL;elsesq->front=(sq->front+1)%maxsize;return (sq->datasq->front);/廣度優先遍歷void BFSL(int k)int i;edgenode *p;Q=(sequeue *)malloc(sizeof(sequeue);SETNULL(Q);printf("%cn",gak.vertex);visitedk=1;ENQUEUE(Q,k);while(!EMPTY(Q)i=DEQUEUE(Q);p=gai.link;while(p!=NULL)if(!visitedp->adjvex)printf("%cn",gap->adjvex.vertex);visitedp->adjvex=1;ENQUEUE(Q,p->adjvex);p=p->next;void main()CREATADJLIST(ga);BFSL(0);