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

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

2、然后在用子函數(shù)寫(xiě)出廣度優(yōu)先搜索遍歷的遍歷算法，最后用主函數(shù)調(diào)用它們。  實(shí)現(xiàn)廣度優(yōu)先搜索遍歷可以利用隊(duì)列的原理。利用隊(duì)列先進(jìn)先出的特性，并設(shè)置訪問(wèn)標(biāo)志實(shí)現(xiàn)連通圖的廣度優(yōu)先搜索遍歷。  廣度優(yōu)先搜索遍歷類似于樹(shù)的按層次遍歷，對(duì)于用鄰接表做存儲(chǔ)結(jié)構(gòu)的圖，從某個(gè)給定頂點(diǎn)出發(fā)的圖的遍歷得到的訪問(wèn)結(jié)點(diǎn)頂點(diǎn)次序，隨建立的鄰接表的不同而可能不同。  將每個(gè)結(jié)點(diǎn)的邊用一個(gè)單邊表鏈接起來(lái)組成一個(gè)整體。所有頭結(jié)點(diǎn)可看成一個(gè)一維數(shù)組，即鄰接表所有鏈表中結(jié)點(diǎn)數(shù)目的一半為圖中邊數(shù)。占用的存儲(chǔ)單元數(shù)目為n+2e。  抽象算法描述:  （1）訪問(wèn)頂點(diǎn)i，并將其訪問(wèn)標(biāo)志置為已

3、被訪問(wèn)，即visitedi=true。 （2）依次訪問(wèn)與標(biāo)點(diǎn)i有邊相連的所有頂點(diǎn)w1,w2-wt。（3）再按次序訪問(wèn)與w1,w2-wt有邊相連且未曾訪問(wèn)過(guò)的頂點(diǎn)。 （4）依此類推，直到圖中所有頂點(diǎn)都被訪問(wèn)完。五、代碼：#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;/建立無(wú)向圖的鄰接表void CREATADJLIST(vexnode ga)int i,j,k;edgenode *s;printf("讀入樹(shù)的結(jié)點(diǎn)信息：");for(i=0;i<n;i+)gai.

5、vertex=getchar();gai.link=NULL;printf("讀入邊（vi,vj）的頂點(diǎn)對(duì)序號(hào)：");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;/置空隊(duì)voi

6、d SETNULL(sequeue *sq)sq->front=maxsize-1;sq->rear=maxsize-1;/判隊(duì)空int EMPTY(sequeue *sq)if(sq->rear=sq->front)return 1;elsereturn 0;/入隊(duì)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;/出隊(duì)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);