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

上機(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)實(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)境:Windows8。1MicrosoftVisualc++6。0實(shí)驗(yàn)內(nèi)容及要求:編寫(xiě)圖的廣度優(yōu)先遍歷算法。四、概要設(shè)計(jì)：先定義圖的鄰接表數(shù)據(jù)，建立該圖的鄰接表,然后在用子函數(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)志置為已被訪問(wèn)，即visited［i］=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〉＃definemaxsize1024#definen8#definee9typedefchardatatype;typedefcharvextype;//定義結(jié)構(gòu)體typedefstruct｛intdata［maxsize］；intfront，rear;｝sequeue;//定義結(jié)構(gòu)體typedefstructnode｛datatypeadjvex；structnode*next；}edgenode;//定義結(jié)構(gòu)體typedefstruct{vextypevertex;edgenode*link；}vexnode;sequeue＊Q；vexnodega［n］；intvisited［n］;sequeue＊sq;//建立無(wú)向圖的鄰接表voidCREATADJLIST（vexnodega[]）｛inti，j,k；edgenode*s;printf（"讀入樹(shù)的結(jié)點(diǎn)信息："）;for（i=0;i<n;i++)｛ga［i］。vertex=getchar（）；ga［i］.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=ga[i］.link；ga[i］.link=s;s=(edgenode＊)malloc（sizeof（edgenode）)；s->adjvex=i；s->next=ga［j]。link；ga［j］.link=s；｝｝//置空隊(duì)voidSETNULL（sequeue＊sq)｛sq->front=maxsize—1；sq—〉rear=maxsize—1；｝//判隊(duì)空intEMPTY(sequeue＊sq）{if(sq-〉rear==sq-〉front）return1；elsereturn0;}//入隊(duì)intENQUEUE(sequeue＊sq,datatypex)｛if（sq—〉front==(sq—〉rear+1）％maxsize）{printf（”queueisfull"）；returnNULL；}else｛sq—>rear=(sq-〉rear+1)％maxsize；sq—〉data［sq->rear］=x；return1;｝}//出隊(duì)datatypeDEQUEUE(sequeue＊sq）｛if（EMPTY(sq））｛printf（"queueisempty”）；returnNULL；｝else｛sq->front=（sq—〉front+1)％maxsize；return（sq-〉data［sq—〉front]）；｝}//廣度優(yōu)先遍歷voidBFSL（intk）{inti;edgenode*p；Q=(sequeue＊）malloc（sizeof（sequeue））;SETNULL(Q）;printf(”%c\n”，ga［k］.vertex）；visited［k］=1；ENQUEUE（Q，k）；while(!EMPTY(Q））｛i=DEQUEUE(Q）；p=ga[i］。link；while（p!=NULL）{if（!visited[p—>adjvex]）{printf（"%c\n"，ga[p—〉adjvex].vertex）；visited[p—〉adjvex］=1；ENQUEUE（Q，p-〉adjvex)；｝p=p-〉next;｝}｝voidmain（）｛CREATADJLIST（ga）;BFSL（0）；}六、