廣度優(yōu)先遍歷(鄰接表)

1、 上機實驗報告 學 院： 計算機與信息技術(shù)學院專 業(yè)： 計算機科學與技術(shù)(師范）課程名稱： 數(shù)據(jù)結(jié)構(gòu)實驗題目：廣度優(yōu)先遍歷（鄰接表）班級序號： 師范1班學 號： 201421012731 學生姓名： 鄧雪指導(dǎo)教師： 楊紅穎完成時間： 2015年12月25號1、 實驗?zāi)康模?掌握圖的基本概念和鄰接表存儲結(jié)構(gòu)。 2掌握圖的鄰接表存儲結(jié)構(gòu)的算法實現(xiàn)。  3掌握圖在鄰接表存儲結(jié)構(gòu)上遍歷算法的實現(xiàn)。二、實驗環(huán)境： Windows 8.1 Microsoft Visual c+ 6.02、 實驗內(nèi)容及要求：編寫圖的廣度優(yōu)先遍歷算法。四、概要設(shè)計：先定義圖的鄰接表數(shù)據(jù)，建立該圖的鄰接表，

2、然后在用子函數(shù)寫出廣度優(yōu)先搜索遍歷的遍歷算法，最后用主函數(shù)調(diào)用它們。  實現(xiàn)廣度優(yōu)先搜索遍歷可以利用隊列的原理。利用隊列先進先出的特性，并設(shè)置訪問標志實現(xiàn)連通圖的廣度優(yōu)先搜索遍歷。  廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷，對于用鄰接表做存儲結(jié)構(gòu)的圖，從某個給定頂點出發(fā)的圖的遍歷得到的訪問結(jié)點頂點次序，隨建立的鄰接表的不同而可能不同。  將每個結(jié)點的邊用一個單邊表鏈接起來組成一個整體。所有頭結(jié)點可看成一個一維數(shù)組，即鄰接表所有鏈表中結(jié)點數(shù)目的一半為圖中邊數(shù)。占用的存儲單元數(shù)目為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;/定義結(jié)構(gòu)體typedef structint datamaxsize;int front,r

4、ear;sequeue;/定義結(jié)構(gòu)體typedef struct nodedatatype adjvex;struct node *next;edgenode;/定義結(jié)構(gòu)體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("讀入樹的結(jié)點信息：");for(i=0;i<n;i+)gai.

5、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;/置空隊voi

6、d 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)%m

7、axsize;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);/廣度優(yōu)先遍歷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);