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

《實(shí)現(xiàn)深度優(yōu)先搜索與廣度優(yōu)先搜索算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、實(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ù)1班姓名全永春學(xué)號(hào)2011314103指導(dǎo)教師成績?nèi)掌谝?、目的與要求1、通過本實(shí)驗(yàn)，掌握圖，無向圖的基本概念，掌握圖的遍歷。2、掌握圖的深度優(yōu)先搜索（DFS）與廣度優(yōu)先搜索（BFS）算法。二、實(shí)驗(yàn)內(nèi)容1、建立圖的幾種存儲(chǔ)方式2、圖的深度優(yōu)先搜索算法3、圖的廣度優(yōu)先搜索算法三、實(shí)驗(yàn)原理圖的遍歷是圖的算法中一種非常重要的算法，通過建立圖的存儲(chǔ)結(jié)構(gòu)，采用深度優(yōu)先搜索與廣度優(yōu)先搜索算法可以進(jìn)行圖的遍歷。廣度優(yōu)先遍歷與深度優(yōu)先遍歷的區(qū)別在于：廣度優(yōu)先遍歷是以層為順序，將某一層上的所有節(jié)點(diǎn)都搜索到了之后才向

2、下一層搜索；而深度優(yōu)先遍歷是將某一條枝椏上的所有節(jié)點(diǎn)都搜索到了之后，才轉(zhuǎn)向搜索另一條枝椏上的所有節(jié)點(diǎn)。四、實(shí)驗(yàn)步驟1．建立圖的存儲(chǔ)結(jié)構(gòu)。2．輸入圖的基本接點(diǎn)與信息，完成初始化圖的工作。3．完成圖的深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索算法，可以采用菜單形式進(jìn)行顯示與選擇。（可以在鍵盤輸入邊的信息以構(gòu)建一個(gè)無向圖。以（a,b）的形式輸入邊的信息；對此無向圖進(jìn)行深度優(yōu)先搜索，并輸出正確的序列。）#include#include#definemax20typedefintDate;typedefcharInfo;12typedefstructbian//邊的

3、數(shù)據(jù)結(jié)構(gòu){intzhi;//Infoinfo;structbian*N;}bian;typedefstruct//節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu){inti;bian*F;}Vex;typedefstruct//用來作隊(duì)列，棧{inttop;intbutton;inta[100];}S;Ss;Vexv[max+1];//節(jié)點(diǎn)個(gè)數(shù)bian*bu;intn,e;voidcreate()//創(chuàng)建圖{bian*b;inti,v1,v2;voidmemo();printf("請輸入節(jié)點(diǎn)個(gè)數(shù)N，邊數(shù)E");printf("節(jié)點(diǎn)個(gè)數(shù)N");printf("");scanf("%d",&n);12printf("邊

4、數(shù)E");printf("");scanf("%d",&e);printf("請輸入節(jié)點(diǎn)信息");for(i=1;i<=n;i++){scanf("%d",&v[i].i);}for(i=1;i<=n;i++)v[i].F=0;printf("請輸入邊");printf("起點(diǎn)終點(diǎn)");for(i=1;i<=e;i++){printf("");scanf("%d%d",&v1,&v2);b=(bian*)malloc(sizeof(bian));b->zhi=v2;b->N=v[v1].F;v[v1].F=b;b=(bian*)malloc(sizeof(bian));b

5、->zhi=v1;b->N=v[v2].F;v[v2].F=b;12}memo();}intp[max];voidvist(inti){printf("%d",v[i].i);printf("->");}voidaa()//查看表結(jié)構(gòu){voidmemo();inti,j;bian*b;printf("numDAtenextnextnext....");for(i=1;i<=n;i++){printf("%d",i);printf("%d",v[i].i);b=v[i].F;while(b!=0){j=b->zhi;printf("%d",v[j].i);b=b->N;}12print

6、f("");}printf("");memo();}intf(inti)//返回沒有被訪問過的I的節(jié)點(diǎn){intj=0;bu=v[i].F;while(bu!=0){if(p[bu->zhi]==0){j=bu->zhi;break;}bu=bu->N;}returnj;}voiddfst(inti)//深度優(yōu)先搜索{intj,t;if(p[i]==0){vist(i);p[i]=1;s.a[++s.top]=i;}12while(s.top!=0){t=s.a[s.top];j=f(t);if(j!=0)dfst(j);elses.top=s.top-1;}}voidss(){v

7、oidmemo();inti,j;s.top=0;for(i=1;i<=n;i++)p[i]=0;printf("請輸入搜索起點(diǎn)i");scanf("%d",&i);printf("遍歷次序：");for(;i<=n;i++){if(p[i]==0){dfst(i);}12}for(i=1;i<=n;i++){if(p[i]==0)dfst(i);}printf("");memo();}//廣度優(yōu)先搜索fst(inti){i