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

上機(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)容及要求：編寫圖的廣度優(yōu)先遍歷算法。四、概要設(shè)計(jì)：先定義圖的鄰接表數(shù)據(jù)，建立該圖的鄰接表，然后在用子函數(shù)寫出廣度優(yōu)先搜索遍歷的遍歷算法，最后用主函數(shù)調(diào)用它們。 實(shí)現(xiàn)廣度優(yōu)先搜索遍歷可以利用隊(duì)列的原理。利用隊(duì)列先進(jìn)先出的特性，并設(shè)置訪問標(biāo)志實(shí)現(xiàn)連通圖的廣度優(yōu)先搜索遍歷。 廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷，對(duì)于用鄰接表做存儲(chǔ)結(jié)構(gòu)的圖，從某個(gè)給定頂點(diǎn)出發(fā)的圖的遍歷得到的訪問結(jié)點(diǎn)頂點(diǎn)次序，隨建立的鄰接表的不同而可能不同。 將每個(gè)結(jié)點(diǎn)的邊用一個(gè)單邊表鏈接起來組成一個(gè)整體。所有頭結(jié)點(diǎn)可看成一個(gè)一維數(shù)組，即鄰接表所有鏈表中結(jié)點(diǎn)數(shù)目的一半為圖中邊數(shù)。占用的存儲(chǔ)單元數(shù)目為n+2e。 抽象算法描述: （1）訪問頂點(diǎn)i，并將其訪問標(biāo)志置為已被訪問，即visitedi=true。（2）依次訪問與標(biāo)點(diǎn)i有邊相連的所有頂點(diǎn)w1,w2-wt。（3）再按次序訪問與w1,w2-wt有邊相連且未曾訪問過的頂點(diǎn)。（4）依此類推，直到圖中所有頂點(diǎn)都被訪問完。五、代碼：#include #include #define maxsize 1024#define n 8#define e 9typedef char datatype;typedef char vextype;/定義結(jié)構(gòu)體typedef structint datamaxsize;int front,rear;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é)點(diǎn)信息：);for(i=0;in;i+)gai.vertex=getchar();gai.link=NULL;printf(讀入邊（vi,vj）的頂點(diǎn)對(duì)序號(hào)：);for(k=0;kadjvex=j;s-next=gai.link;gai.link=s;s=(edgenode *)malloc(sizeof(edgenode);s-adjvex=i;s-next=gaj.link;gaj.link=s;/置空隊(duì)void 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)%maxsize;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);BFSL(0);六、運(yùn)行界面七、實(shí)