圖的遍歷：廣度優(yōu)先遍歷

• 思維導(dǎo)圖：
• 廣度優(yōu)先遍歷的原理：
• 廣度優(yōu)先遍歷的代碼實(shí)現(xiàn)：
• 廣度優(yōu)先遍歷的性能分析：
• 無權(quán)圖單源最短路徑問題：
• 廣度優(yōu)先生成樹：

思維導(dǎo)圖：

廣度優(yōu)先遍歷的原理：

類似與樹的層次遍歷

1、先入隊(duì)一個(gè)節(jié)點(diǎn) 2、然后入隊(duì)與該節(jié)點(diǎn)相鄰的且未被訪問過的節(jié)點(diǎn)，然后出隊(duì)該節(jié)點(diǎn) 3、重復(fù)2過程直到所有的節(jié)點(diǎn)均被訪問

ps：
實(shí)現(xiàn)方法是用一個(gè)標(biāo)記數(shù)組加隊(duì)列完成的，標(biāo)記數(shù)組的作用是標(biāo)記節(jié)點(diǎn)是否被訪問過

PS:
當(dāng)采用鄰接數(shù)組存儲時(shí)，由于鄰接矩陣唯一，所以廣度優(yōu)先遍歷序列也唯一。
當(dāng)采用鄰接表存儲時(shí)，由于邊表序列不唯一，所以廣度優(yōu)先遍歷序列也不唯一。

廣度優(yōu)先遍歷的代碼實(shí)現(xiàn)：

//visited是訪問標(biāo)記數(shù)組//處理非連通圖的情況 bool BFSTraverse(Graph G){for(int i=0;i<G.vexnum;++i)visited[i] = false;InitQueue(Q);for(int i=0;i<G.vexnum;++i){if(!visited[i])BFS(G,i);} }void BFS(Graph G,int v){visit(v); //訪問v頂點(diǎn) visited[v] = True; //修改該頂點(diǎn)對應(yīng)數(shù)組的值為true EnQueue(Q,v); //入隊(duì) while(!isEmpty(Q)){ //不空還有未遍歷到的節(jié)點(diǎn) DeQueue(Q,v); //出隊(duì)v for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) //找到所有符合條件的鄰接節(jié)點(diǎn) if(!visited[w]){ //w是否被訪問 visit[w]; //訪問 visited[w] = true; //修改該頂點(diǎn)對應(yīng)數(shù)組的值為trueEnQueue(Q,w); //入隊(duì) }} } bool BFSTraverse(Graph G，int v){for(int i=0;i<G.vexnum;++i)visited[i] = false;InitQueue(Q);for(int i=0;i<G.vexnum;++i){if(!visited[i])visit(v); //訪問v頂點(diǎn) visited[v] = True; //修改該頂點(diǎn)對應(yīng)數(shù)組的值為true EnQueue(Q,v); //入隊(duì) while(!isEmpty(Q)){ //不空還有未遍歷到的節(jié)點(diǎn) DeQueue(Q,v); //出隊(duì)v for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) //找到所有符合條件的鄰接節(jié)點(diǎn) if(!visited[w]){ //w是否被訪問 visit[w]; //訪問 visited[w] = true; //修改該頂點(diǎn)對應(yīng)數(shù)組的值為trueEnQueue(Q,w); //入隊(duì) }}} }

廣度優(yōu)先遍歷的性能分析：

無權(quán)圖單源最短路徑問題：

ps：
無權(quán)圖：無權(quán)值或權(quán)值相等
單源：從一個(gè)頂點(diǎn)出發(fā)
最短路徑：廣度優(yōu)先遍歷

void BFS_Distance(Graph G，int v){for(int i=0;i<G.vexnum;++i)d[i] = MAX;visited[v] = true;d[v] = 0;EnQueue(Q,v);while(!isEmpty(Q)){ //不空還有未遍歷到的節(jié)點(diǎn) DeQueue(Q,v); //出隊(duì)v for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) //找到所有符合條件的鄰接節(jié)點(diǎn) if(!visited[w]){ //w是否被訪問 visited[w] = true; //修改該頂點(diǎn)對應(yīng)數(shù)組的值為trued[w] = d[v] + 1;EnQueue(Q,w); //入隊(duì) }} }

廣度優(yōu)先生成樹：

ps： 節(jié)點(diǎn)5是由節(jié)點(diǎn)2訪問的，而不是節(jié)點(diǎn)4訪問的，所有沒有4到5的邊

總結(jié)

以上是生活随笔為你收集整理的数据结构之图的遍历：广度优先遍历（BFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。