實(shí)現(xiàn)深度優(yōu)先搜索與廣度優(yōu)先搜索算法

/實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)項(xiàng)目實(shí)現(xiàn)深度優(yōu)先搜索與廣度優(yōu)先搜索算法專業(yè)班級(jí)計(jì)算機(jī)科學(xué)與技術(shù)１班姓名全永春學(xué)號(hào)２0１1３14103指導(dǎo)教師成績(jī)?nèi)掌谝?、目的與要求１、通過(guò)本實(shí)驗(yàn)，掌握?qǐng)D，無(wú)向圖的基本概念，掌握?qǐng)D的遍歷。2、掌握?qǐng)D的深度優(yōu)先搜索(ＤFＳ）與廣度優(yōu)先搜索(ＢFS)算法。二、實(shí)驗(yàn)內(nèi)容1、建立圖的幾種存儲(chǔ)方式2、圖的深度優(yōu)先搜索算法3、圖的廣度優(yōu)先搜索算法三、實(shí)驗(yàn)原理圖的遍歷是圖的算法中一種非常重要的算法，通過(guò)建立圖的存儲(chǔ)結(jié)構(gòu)，采用深度優(yōu)先搜索與廣度優(yōu)先搜索算法可以進(jìn)行圖的遍歷。廣度優(yōu)先遍歷與深度優(yōu)先遍歷的區(qū)別在于:廣度優(yōu)先遍歷是以層為順序,將某一層上的所有節(jié)點(diǎn)都搜索到了之后才向下一層搜索;而深度優(yōu)先遍歷是將某一條枝椏上的所有節(jié)點(diǎn)都搜索到了之后,才轉(zhuǎn)向搜索另一條枝椏上的所有節(jié)點(diǎn)。四、實(shí)驗(yàn)步驟1.建立圖的存儲(chǔ)結(jié)構(gòu).2.輸入圖的基本接點(diǎn)與信息，完成初始化圖的工作.3。完成圖的深度優(yōu)先搜索(DＦS）和廣度優(yōu)先搜索算法，可以采用菜單形式進(jìn)行顯示與選擇。（可以在鍵盤輸入邊的信息以構(gòu)建一個(gè)無(wú)向圖。以（ａ，b）的形式輸入邊的信息；對(duì)此無(wú)向圖進(jìn)行深度優(yōu)先搜索，并輸出正確的序列。)? ＃inclｕde〈ｓｔdio．h>#include〈mａllｏc．h>#dｅfineｍax２0tyｐedefintDate；tyｐedefcharInfo；tyｐedefstruｃtbiａｎ//邊的數(shù)據(jù)結(jié)構(gòu)｛?ｉｎｔzhi；?//Iｎfoinｆo;?structbｉan＊N；｝bian；tyｐｅdeｆstrｕｃt//節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu){?ｉnｔｉ; ｂian＊F；｝Ｖeｘ;ｔypedｅfｓｔrｕcｔ//用來(lái)作隊(duì)列，棧｛ ｉntｔoｐ； ｉnｔbuttｏn；?inta[１00];｝Ｓ；Ｓｓ;Ｖexv［ｍaｘ＋1］；//節(jié)點(diǎn)個(gè)數(shù)biaｎ＊ｂｕ；iｎｔｎ，e；voiｄcrｅａt(yī)e()／/創(chuàng)建圖{biaｎ＊b； inti,ｖ1,v2；?ｖoidmemo()；?ｐｒinｔｆ(＂請(qǐng)輸入節(jié)點(diǎn)個(gè)數(shù)N，邊數(shù)Ｅ\n＂）； pｒinｔf（”節(jié)點(diǎn)個(gè)數(shù)N＼n"）； pｒｉnｔf(”")；?scanf("%d”,&n）;?pｒiｎtf("邊數(shù)E\n”)；?ｐrｉnｔｆ（”＂）; scanf(”％d＂，&ｅ）;?pｒiｎtｆ（＂請(qǐng)輸入節(jié)點(diǎn)信息\n＂)； fｏr（i=1；i<＝n；i+＋)?｛ ???scanｆ（＂％d"，＆v［i].i）;??｝ for(i=1；i〈=n;i+＋） ?v[i］.Ｆ=0；?prｉntf(”請(qǐng)輸入邊\n"）; printｆ（＂起點(diǎn)終點(diǎn)\ｎ＂）；?fｏr（ｉ=1;i〈＝e;i＋+） {??printf（"＂);?ｓcanf（”%d％d＂，&ｖ1，&v2）;? ｂ=(biａn＊）malloｃ(sizeof（ｂｉaｎ））； ｂ—〉ｚhi=v2； ｂ—>N=ｖ［v1］。Ｆ； v[v1]．Ｆ=b;??ｂ=（bian＊)malloc（sizeof（bian）)； b－>ｚhi=v1； b－＞N=v［v2]。F; v［v2］.F=ｂ；??} ｍｅmo()；｝intp[ｍａｘ］；ｖｏｉdvｉst（inti）｛ priｎｔｆ（"%d”，v［i].i）；?ｐrintf(”—>”）；｝voidａa()/／查看表結(jié)構(gòu)｛ voidmemo（）；?iｎtｉ,ｊ;bian＊b;?printｆ（"nuｍDAteｎextneｘtnｅxt。..．\ｎ”）; fｏｒ（i=１;i<＝n;i+＋）?｛ ｐｒiｎtf（”%ｄ＂，i);? ? ?pｒintｆ（"%d”,v[ｉ］。ｉ)；?? b=ｖ［i］．F； while（b!=０） ?{? ?j=b->zhi;? ?ｐrintｆ（"％ｄ＂，v［j]。ｉ）; ?b=b->N；??｝ ?prinｔf(”＼ｎ")； }? ｐriｎtf(”＼n”)； ｍemo（）；｝inｔf（ｉnti）//返回沒有被訪問(wèn)過(guò)的I的節(jié)點(diǎn){?intｊ=0；?bｕ＝v[i］．F； whｉｌe（bｕ?。剑? ｛??if（p［bu－＞zhi]=＝0） {j=bu－>zhi;breａｋ；｝bu=bu－＞N； }?retｕrｎj；｝voiddfst(ｉntｉ)/／深度優(yōu)先搜索{ iｎtｊ，t； if(p［i]=＝0） {?vist(i)；p[i］=1； s。a［+＋s。top］＝i； }whｉlｅ（ｓ．toｐ?。?)?｛ t=ｓ．a(chǎn)［s.top］;? ?j＝f（ｔ)；???ｉf（j！=0） ? dfst（j)；? eｌses。ｔｏp=s.tｏp-1； ? ? }?}voidss()｛?voidmemｏ（）; ｉｎti，j; s．ｔop=０；?for(i＝1；i＜=ｎ;ｉ+＋） p[i]=０； ｐriｎtf("請(qǐng)輸入搜索起點(diǎn)i\n”); scanf(”%d”，＆i)；?pｒintｆ(＂遍歷次序：＂);?ｆor（；i<=ｎ;i++） ｛ ?if(p［i］==０） ?｛ ? dｆst（i）；?? ??｝??? ??} for(i=1；ｉ〈＝n;i++）?｛ if（ｐ[i]==0）??? dｆｓt(i);? ??} ｐｒｉｎtf(＂\n”)； ?mｅmo（)；}／/廣度優(yōu)先搜索fst(inti){iｎｔj；ｉf（ｐ［i］==0){?visｔ（i);ｐ[i]=1;ｓ。ａ[s.top+＋]＝ｉ；}? ?while(ｂu！=0) ｛ ???j=bu—＞zｈi;? ?bu=ｂｕ-〉N； ?? if（p［ｊ］==０) ?? fst（j）；?? ?? ? ｝}voidwfst（）｛ voｉｄmemｏ(）;?intj，i； s。buｔton=s。top=0；?ｆoｒ(i=1;i<=n；i++)?p［ｉ]=０;?pｒinｔf（"請(qǐng)輸入搜索起點(diǎn)i\n")； ｓcａnf（”％d＂,＆i);?printｆ（”遍歷次序：”）； for（；i〈＝n；i++） ?if（p[i］＝=0) ?｛??? ｂu=v［i］．F; fst（ｉ）; ?? ?? ｗhile（ｓ.bｕtｔon！=s．ｔop）???｛ ? ｊ=s．a(chǎn)［ｓ．buｔton］;? j＝ｆ（j)；??iｆ(j〉0)?? fｓt(j）;? eｌsｅ ??ｓ。butｔon=ｓ．ｂutｔon+1； ?}? ｝ for(i=1；i〈=n；ｉ++)? iｆ(p[i］==0) ?{ ? bu＝v[i]。F;??? fst(i）;????? ?? ??while（s.bｕtton!=s.top） ? ｛????j=s.a[ｓ。bｕtｔon］；??j=f(ｊ）; if（j〉0） fsｔ(ｊ)；??eｌse ??s.ｂｕtton=ｓ．button＋1; ?}? ｝ ? prｉntf(”\n”）;??memｏ（);}voiｄmemｏ（）/／菜單顯示｛?inti;?printf(”1.創(chuàng)建無(wú)向圖２。深度優(yōu)先搜索3.廣度優(yōu)先搜索4。查看鄰接表邏輯結(jié)構(gòu)５．退出\n”）；printf（＂請(qǐng)輸入相應(yīng)數(shù)字選擇所需操作\n＂）；scanｆ(＂%d＂,＆i）；switcｈ(i）｛caｓe１:ｃreaｔｅ(）；bｒｅak；cａｓe2:ss(）；ｂｒeａｋ；case３:ｗfｓt（);bｒeaｋ;case4：aａ（）;breaｋ;cａｓe5：eｘiｔ(1);breaｋ;｝}voidmaｉn(）｛mｅmo（）；｝? 五、運(yùn)行結(jié)果六、實(shí)驗(yàn)體會(huì)這堂Huｆfman編碼以及解碼的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課讓我對(duì)數(shù)據(jù)結(jié)構(gòu)的整體學(xué)習(xí)有了進(jìn)一步的了解,剛開始的時(shí)候稍微有點(diǎn)迷茫，但是