圖的廣度優(yōu)先遍歷
1.樹的廣度優(yōu)先遍歷
這樣一個圖中，是如何實現(xiàn)廣度優(yōu)先遍歷的呢，首先，從1遍歷完成之后，在去遍歷2,3,4，最后遍歷5 ，6 , 7? , 8。這也就是為什么叫做廣度優(yōu)先遍歷，是一層一層的往廣的遍歷
不存在“回路”，搜索相鄰的結(jié)點時，不可能搜到已經(jīng)訪問過的結(jié)點
樹的廣度優(yōu)先遍歷（層序遍歷)
①若樹非空，則根節(jié)點入隊
②若隊列非空，隊頭元素出隊并訪問，同時將該元素的孩子依次入隊③重復(fù)②直到隊列為空
2.圖的廣度優(yōu)先遍歷
圖的廣度優(yōu)先和樹的廣度優(yōu)先還是非常相似的，首先我們假設(shè)我們從?2?號結(jié)點開始，然后廣度優(yōu)先遍歷 1 ,? 6 （這里面1和6的順序無所謂，但是還是為了保持一定的順序，一般從小的開始）然后1的話再遍歷就是5 ， 6再找相鄰的就是 3 和 7 ，于是訪問的就是 5 ，3? ，7 。在找到下一層就是 4 ，8 。
廣度優(yōu)先遍歷(Breadth-First-Search, BFS)要點:
1．找到與一個頂點相鄰的所有頂點·
2、標(biāo)記哪些頂點被訪問過
3．需要一個輔助隊列
FirstNeighbor(G,x):求圖G中頂點x的第一個鄰接點，若有則返回頂點號。若x沒有鄰接點或圖中不存在x，則返回-1。
NextNeighbor(G,x,y)︰假設(shè)圖G中頂點y是頂點x的一個鄰接點，返回除y之外頂點x的下一個鄰接點的頂點號，若y是x的最后一個鄰接點，則返回-1。
?
代碼
bool visited [MAX_VERTEX_NUM];/訪問標(biāo)記數(shù)組
//廣度優(yōu)先遍歷
void BFS( Graph G,int v){//從頂點v出發(fā)，廣度優(yōu)先遍歷圖G
visit(v); //訪問初始頂點v
visited [v]=TRUE; //對v做已訪問標(biāo)記
Enqueue(Q,v); //頂點v入隊列Q
while( !isEmpty(Q) ){
DeQueue(Q, v); //頂點v出隊列
for(w=FirstNeighbor(G,v ) ;w>= ; w=NextNeighbor(G,v,w))
//檢測v所有鄰接點
if( !visited [w] )//w為v的尚未訪問的鄰接頂點
{
visit(w);//訪問頂點w
visited [w]=TRUE;//對w做已訪問標(biāo)記
EnQueue(Q,w);//頂點w入隊列
}
}
按照上面的例子，首先
我們先遍歷到 2 ，2 放到隊列，如果隊列不空，把 1 和 6 放到隊尾，然后 1號出隊，和 1號鄰的為
5和 2 ，由于 2被visit了所以訪問未被訪問的結(jié)點5,5號結(jié)點入隊，都訪問完了，看六號結(jié)點，六號結(jié)點出隊。6號結(jié)點相鄰的且未被訪問的是3 ， 7 。visit 3 和 7 并且都放在隊尾，然后看3 ，和3相鄰的且未被訪問的是4 號，訪問4號結(jié)點，讓4 號結(jié)點入隊，最后，3號出隊，看7號結(jié)點，與7號結(jié)點相鄰的且未被訪問的是8號結(jié)點。最后所有結(jié)點都被訪問。
?
?
?文章來源：http://www.zghlxwxcb.cn/news/detail-783742.html
3.算法存在的問題和解決方案
前面介紹的都是連通圖，如果是非連通圖，那么上面算法就實現(xiàn)不了。我們可以直接從0號結(jié)點開始，遍歷所有結(jié)點查看是否有未被訪問的結(jié)點，找到第一個值為false的結(jié)點。從這個結(jié)點出發(fā)調(diào)用BFS。
?
代碼
bool visited [MAX_VERTEX_NUM] ; //訪問標(biāo)記數(shù)組
void BFSTraverse(Graph G){ //對圖G進行廣度優(yōu)先遍歷
for( i=0; i<G.vexnum;++i)
visited[i]=FALSE; //訪問標(biāo)記數(shù)組初始化
InitQueue(Q); //初始化輔助隊列Q
for( i=0; i<G.vexnum;++i) //從0號頂點開始遍歷
if( !visited[i]) //對每個連通分量調(diào)用一次BFS
BFS(G,i); // vi未訪問過，從vi開始BFS
}
bool visited [MAX_VERTEX_NUM];/訪問標(biāo)記數(shù)組
//廣度優(yōu)先遍歷
void BFS( Graph G,int v){//從頂點v出發(fā)，廣度優(yōu)先遍歷圖G
visit(v); //訪問初始頂點v
visited [v]=TRUE; //對v做已訪問標(biāo)記
Enqueue(Q,v); //頂點v入隊列Q
while( !isEmpty(Q) ){
DeQueue(Q, v); //頂點v出隊列
for(w=FirstNeighbor(G,v ) ;w>= ; w=NextNeighbor(G,v,w))
//檢測v所有鄰接點
if( !visited [w] )//w為v的尚未訪問的鄰接頂點
{
visit(w);//訪問頂點w
visited [w]=TRUE;//對w做已訪問標(biāo)記
EnQueue(Q,w);//頂點w入隊列
}
}
?
4.知識回顧與總結(jié)
?
?
圖的深度優(yōu)先遍歷
1.樹的深度優(yōu)先遍歷
樹的深度優(yōu)先遍歷有點類似于先根遍歷
首先遍歷 1 2 5 6 3? 4 7 8 ，它的遍歷更趨向于先深層的遍歷樹。
?
2.圖的深度優(yōu)先遍歷
首先我們可以先看一下2，和2相鄰的是1號結(jié)點和6號結(jié)點。和2相鄰的第一個結(jié)點是1，所以先訪問1，1號結(jié)點未被訪問。和1號結(jié)點相鄰的為2 號和5號，但是2號被訪問過了，所以看5號結(jié)點。和5號結(jié)點相鄰的結(jié)點點都被訪問過。這個頂點的DFS調(diào)用完，返回到1號接點調(diào)用層，但是1號節(jié)點調(diào)用都被調(diào)用完了，那么就可以返回2號結(jié)點調(diào)用層，2號結(jié)點身邊的結(jié)點未被訪問。即是6號結(jié)點。和6號結(jié)點相近的且未被訪問的是 3和 7號結(jié)點，先訪問3號結(jié)點，下一個應(yīng)該被訪問的是4號結(jié)點，和4號相鄰的且未被訪問的是7號結(jié)點，最后8號結(jié)點未被訪問，訪問一下8號結(jié)點。
?
代碼
bool visited [MAX_VERTEX_NUM] ;//訪問標(biāo)記數(shù)組
void DFS(Graph G,int v){ //從頂點v出發(fā)，深度優(yōu)先遍歷圖G
visit(v ); //訪問頂點v
visited [v]=TRUE; //設(shè)已訪問標(biāo)記
for( w=FirstNeighbor(G,v) ;w>=0 ; w=NextNeighor(G,v,w) )
if( !visited [w] ){ //w為u的尚未訪問的鄰接頂點
DFS(G,w) ;
}
?
3.算法存在的問題和解決方案
與廣度優(yōu)先算法一樣，如果存在非連通圖，那么同樣的，我們可以直接從0號結(jié)點開始，遍歷所有結(jié)點查看是否有未被訪問的結(jié)點，找到第一個值為false的結(jié)點。從這個結(jié)點出發(fā)調(diào)用BFS。
最終代碼
bool visited [MAX_VERTEX_NUM];//訪問標(biāo)記數(shù)組
void DFSTraverse(Graph G){ //對圖G進行深度優(yōu)先遍歷
for( v=0; v<G.vexnum;++v)
visited[v]=FALSE; //初始化已訪問標(biāo)記數(shù)據(jù)
for( v=0 ; v<G.vexnum; ++v) //本代碼中是從v=0開始遍歷
if( !visited[v])
DFS(G,v);
}
bool visited [MAX_VERTEX_NUM] ;//訪問標(biāo)記數(shù)組
void DFS(Graph G,int v){ //從頂點v出發(fā)，深度優(yōu)先遍歷圖G
visit(v ); //訪問頂點v
visited [v]=TRUE; //設(shè)已訪問標(biāo)記
for( w=FirstNeighbor(G,v) ;w>=0 ; w=NextNeighor(G,v,w) )
if( !visited [w] ){ //w為u的尚未訪問的鄰接頂點
DFS(G,w) ;
}
4.知識回顧與總結(jié)
?
文章來源地址http://www.zghlxwxcb.cn/news/detail-783742.html
到了這里，關(guān)于圖的二種遍歷-廣度優(yōu)先遍歷和深度優(yōu)先遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
