Depth-First Search and Breadth-First Search | 閱讀的城市貓

2024-11-25

文章推薦指數： 80 %

投票人數：10人

C語言系列: Depth-First Search and Breadth-First Search ... 找List中最後一個link void DFS(int);//以Recursive來實現DFS void BFS(int);//以queue ... 深度優先搜尋法及廣度優先搜尋法的複習及基本介紹。

先介紹本文章所使用的圖形結構為下: 深度優先搜尋法(Depth-FirstSearch) 先拜訪起始點V。

選擇與V相鄰但尚未被拜訪的頂點W。

再以W為起始點。

重複步驟1到3，直到所有頂點皆被訪問過結束。

可以用Stack或Recursive的方式來實現深度優先搜尋法。

以本文張的圖形結構深度優先搜尋會如下圖: 廣度優先搜尋法(Breadth-First Search) 先拜訪起始點V。

拜訪與V相鄰且未被訪問的頂點。

重複步驟1與2，直到所有與V相鄰的頂點皆被訪問後尋找下一層頂點。

可以用queue來實現廣度優先搜尋法。

以本文張的圖形結構廣度優先搜尋會如下圖: 完整程式碼: //DepthFirstSearch(DFS)andBreadthFirstSearch(BFS) #include"pch.h" #include #include #defineMAX100 typedefstructnode_list{ intvertex; structnode_list*list; }Node; Node*adjacentlist[MAX+1];//伴隨List intisvisited[MAX+1],queen[MAX+1],totalnum=0; //isvisited表示此節點是否曾被訪問過 Node*searchlast(Node*);//找List中最後一個link voidDFS(int);//以Recursive來實現DFS voidBFS(int);//以queue來實現BFS voidBuildlist();//初始化及將.dat中的adjacentmatrix轉換成adjacentlist voidShowlist();//顯示adjacentlist intmain(){ Buildlist(); Showlist(); printf("--------------------------------\n"); printf("DepthFirstSearchPath:"); DFS(0); printf("\nBreadthFirstSearchPath:"); BFS(0); } voidBuildlist(){ intconnect=0; Node*last; FILE*fp=fopen("adjacent_matrix.dat","r"); if(fp==NULL){ perror("adjacent_matrix.dat"); exit(0); } fscanf(fp,"%d",&totalnum); for(intindex=0;indexlist=NULL; adjacentlist[index]->vertex=index+1; }//初始化及宣告記憶體空間給adjacentlist的head for(inti=0;ivertex=j+1; last=searchlast(adjacentlist[i]); last->list=node; } } } }//將.dat中的adjacentmatrix，轉換成adjacentlist } voidShowlist(){//顯示adjacentlist Node*ptr; printf("AdjacnetList\n"); printf("--------------------------------\n"); for(intindex=0;indexlist; while(ptr!=NULL){ printf("-->"); printf("V%2d",ptr->vertex); ptr=ptr->list; } printf("\n"); } } voidDFS(intv){//以Recursive來實現DFS Node*ptr; intw; printf("V%d",adjacentlist[v]->vertex);//訪問此頂點 isvisited[v]=1;//記錄已被訪問 ptr=adjacentlist[v]->list;//尋找此頂點的下一個相鄰頂點 do{ w=ptr->vertex-1; if(!isvisited[w]){ DFS(w);//用recursive的方式更深層找未探索過的頂點 } else{ ptr=ptr->list;//尋找頂點w中的下一個相鄰頂點 } }while(ptr!=NULL);//直到頂點w所有的相鄰點都訪問過結束 } voidBFS(intv){//以queue來實現BFS intqufront=0,qurear=1; int*queue=(int*)calloc(MAX+1,sizeof(int)); for(intcnt=0;cntvertex); //直接從起始點0開始訪問 do{ //判斷NULL例外狀況 if(prt==NULL){ prt=adjacentlist[*(queue+qufront)-1]; qufront++;//front } else{ prt=prt->list; } //紀錄 if(prt!=NULL){ if(isvisited[prt->vertex-1]==0){ qurear++;//rear *(queue+qurear)=prt->vertex; printf("V%d",prt->vertex); isvisited[prt->vertex-1]=1; } } }while(qurearlist!=NULL){ node=node->list; } returnnode;//將最後一個node的位址回傳回去 } 執行結果: _______________________________________________我們透過閱讀與實際參與，拼湊出真實世界的面貌，並在反覆的探索及思維中，打破由自我無知與偏見所建立的籓籬。

Breadth-FirstSearchCDepth-FirstSearchLinkedList資料結構遞迴線性佇列回首頁軟體攻城獅，遊走在不同議題的旅者，想成為能點亮黑夜的微光，是喜歡思考、剖析觀察到的現象，並學習新知識體系中思維脈絡的大貓。

座右銘是「先處理情緒，再解決問題」。

本頁段落深度優先搜尋法(Depth-FirstSearch) 廣度優先搜尋法(Breadth-First Search) 完整程式碼: 執行結果: