22图的遍历
圖的遍歷
?
圖的遍歷：搜索屬于圖的基本運(yùn)算。樹的先序遍歷和按層遍歷的推廣。圖的遍歷也稱搜索，主要有：
先深搜索（depth-first search）——深度優(yōu)先搜索——dfs搜索
先廣搜索（breadth-first search）——廣度優(yōu)先搜索——bfs搜索
?
遍歷目的——完成圖運(yùn)算（求子圖或路徑）：生成樹，連通分量，無向圖的雙連通分量，有向圖的強(qiáng)連通分量，有向圖頂點(diǎn)的拓?fù)渑判?#xff0c;判斷有向圖是否有回路，求解迷宮問題。
搜索應(yīng)用：找出圖的生成樹、圖的連通分量等。
?
1.先深搜索：
按一定的規(guī)律沿著圖中的邊訪問每個(gè)頂點(diǎn)恰一次的運(yùn)算稱為對圖的遍歷（和二叉樹遍歷相仿）。
其實(shí)就是利用遞歸的思想。比如先訪問A結(jié)點(diǎn)，而A結(jié)點(diǎn)與B相連，就訪問B結(jié)點(diǎn)，若B與D相連，就接著訪問D結(jié)點(diǎn)。。。。。。
?
先深搜索算法
（1）原始描述形式
步驟1）將圖G中所有頂點(diǎn)作“未訪問過”標(biāo)記。
步驟2）任選某個(gè)未訪問過的頂點(diǎn)v作搜索起點(diǎn)。
步驟3）訪問v。
步驟4）選擇v的每一個(gè)未訪問過的鄰接點(diǎn)w作起點(diǎn)，遞歸的搜索圖G。
步驟5）若所有頂點(diǎn)均已訪問過，則搜索結(jié)束；否則，轉(zhuǎn)步驟2。
?
描述形式:
分成主控函數(shù)和遞歸的搜索函數(shù)
主控函數(shù)
步驟1）將圖中每個(gè)頂點(diǎn)置未訪問標(biāo)記；
步驟2）檢查每個(gè)頂點(diǎn)v，如果v未訪問過，則dfs(v)；遞歸的搜索函數(shù)dfs(v)
步驟3）訪問v，并對v作“已訪問”標(biāo)記；
步驟4）檢查v的每個(gè)鄰接點(diǎn)w，如果w未訪問過，則調(diào)用dfs(w)；
步驟5）返回上一次調(diào)用點(diǎn)；
?
示例：
?
?
?
對無向圖搜索的特點(diǎn)：
1）若連通，搜索路線構(gòu)成先深生成樹。
2）引起遞歸的邊：樹邊（tree edge）和回邊，或余邊（back edge）將E劃分成樹邊集T和回邊集B? 。
?
3）若步驟2和4中，如有多個(gè)頂點(diǎn)可選，可任選其一搜索路線不唯一，生成樹不唯一。
4）若不連通圖，產(chǎn)生先深生成森林。
5）不同的子生成樹之間不可能有回邊相連。
6）祖先的先深號必小于子孫的先深號，對子孫的搜索先終止，而對祖先的搜索后終止。
?
對有向圖搜索的特點(diǎn)：
1）若強(qiáng)連通，可得到先深生成樹。
2）非強(qiáng)連通，也不一定不能到先深生成樹。
3）可將邊集E劃分成：樹邊T、回邊B、向前邊F和交叉邊C 。
注意以下幾個(gè)術(shù)語：
樹邊：引起遞歸調(diào)用的邊。
回邊：由子孫射向祖先的邊。
?
向前邊F（forward edges）：由祖先射向子孫的邊。
交叉邊C（cross edges）：無祖孫關(guān)系頂點(diǎn)之間的邊。
4）先訪問的頂點(diǎn)（先深號小）在上、在左，后訪問的頂點(diǎn)在下、在右交叉邊：由右射向左，而不會由左射向右。
5）樹邊和向前邊：小號射向大號。
回邊和交叉邊：大號射向小號。
?
?
?
?
先深搜索的實(shí)現(xiàn)：
由主控函數(shù)和遞歸搜索函數(shù)dfs兩部分共同完成
圖的存儲形式：鄰接表。
頂點(diǎn)結(jié)點(diǎn)含有訪問否標(biāo)志域mark。
未訪問點(diǎn)，mark值為0；已訪問點(diǎn)，mark值為1。
主控函數(shù)的功能：
1.對頂點(diǎn)作未訪問標(biāo)記（即初始化）
2.檢查是否存在未訪問過的頂點(diǎn)
3.選擇一個(gè)未訪問過的頂點(diǎn)作為搜索起點(diǎn)
4.通過搜索起點(diǎn)調(diào)用遞歸的搜索函數(shù)dfs
?
搜索函數(shù)dfs(v)的功能：
1.置頂點(diǎn)v已訪問標(biāo)記，使其mark域?yàn)?
2.沿v的鄰接表檢查其各鄰接點(diǎn)是否訪問過
3.對未訪問過的鄰接點(diǎn)w，遞歸調(diào)用dfs(w)
4.當(dāng)v的鄰接表“走”完后，對v的搜索終止，退回到dfs(v)的調(diào)用點(diǎn)
?
主控函數(shù)
void main_1( )
???? { int v;
????? for (v=0;v<n;v++) L[v].mark=0;? //置未訪問標(biāo)記
????? for (v=0;v<n;v++)?? //檢查各頂點(diǎn)是否訪問過??
?
? ? ?if(L[v].mark= =0) //如果v未訪問過
??????????? dfs(v);? //選v作搜索起點(diǎn)，調(diào)用搜索函數(shù)
????? …………? //? 其他處理操作
}
?
搜索函數(shù)
void? dfs (int v)?? //遞歸的搜索函數(shù)，v是頂點(diǎn)編號
?? { Eptr? p;? int w;
???? visit(v);? //? 訪問v
???? L[v].mark=1; // 作訪問標(biāo)記?
???? p=L[v].firstedge;? //p指向v的鄰接表首結(jié)點(diǎn)
???? while (p!=NULL)? //檢查v的所有鄰接點(diǎn)
???? { w=p->adjacent;? //w是v的鄰接點(diǎn)
?????? if (!L[w].mark)dfs(w);? //若w未訪問過，遞歸調(diào)用dfs
?????? p=p->next;? //遞歸返回后，再查看v的下一個(gè)鄰接點(diǎn)
???????? }
??? }
?
?
先深搜索的應(yīng)用：
對無向圖的先深搜索，可以
1.判斷是否連通
2.找出連通分量、雙連通分量
3.找出生成樹或生成林
對有向圖的先深搜索，可以
1.判斷圖中是否存在回路
2.找出強(qiáng)連通分量
3.對頂點(diǎn)進(jìn)行柘樸排序
?
?
求無向圖的連通分量算法（這里只給出修改后的主控函數(shù)）
? void? dfsmain()?
??? {?? int v,k=0;
??? for(v=0;v<n;v++)L[v].mark=0;
??? for(v=0;v<n;v++)
??? if(L[v].mark==0)
??????? {?? k++;
??????????? printf("第 %d? 個(gè)連通分量：\n {",k);
??????????? dfs(v);
??????????? printf(" }\n");
?????? }
???? }?
?
?
求無向圖的先深生成樹（林）算法（這里只給出修改說明）
主控函數(shù)不變
將搜索函數(shù)中的：
??? if(!L[w].mark)dfs(w);
改為 ：
?? if (!L[w].mark)
?????? {? 將（v，w）加進(jìn)樹邊集; L[w].father=v; dfs(w); }
?
判斷有向圖是否存在回路原理：
執(zhí)行dfs(v) 期間，區(qū)分：T、B、F、C
<v,w>是T，v是w父，w未訪問過，dfs(v)未終止
<v,w>是F，v是w祖，dfs(w)已終止
<v,w>是C，v在w之右，dfs(w)已終止
<v,w>是B，w是v祖，w已訪問過，dfs(w)未終止
?
結(jié)論：如果w已訪問過，但dfs(w)尚未終止，
?????????? 則<v，w>必是回邊
?
該標(biāo)記mark的作用：
L[v].mark=0，表示v尚未訪問過
L[v].mark=1，表示v已經(jīng)訪問過，但dfs(v)尚未終止
L[v].mark=2，表示v已經(jīng)訪問過，且dfs(v)已經(jīng)終止
在進(jìn)入dfs(v)之前，程序置L[v].mark=0
??? 在進(jìn)入dfs(v)之后，程序置L[v].mark=1
dfs(v)結(jié)束處，置L[v].mark=2
?
判斷有向圖是否存在回路算法：
主控函數(shù)
void? dfsmain( )
? { int v;
???? cycle=0;????????? //cycle是整體量
?? for(v=0;v<n;v++)L[v].mark=0;
???? for(v=0;v<n;v++)
?????? if(L[v].mark==0)dfs(v);
?? if(cycle) printf("圖中有回路\n");
???? else? printf("圖中沒有回路\n");
? }
?
void? dfs (int v)?? //遞歸的搜索函數(shù)，v是頂點(diǎn)編號
?? { Eptr? p;? int w;
??? visit(v);? //? 訪問v
??? L[v].mark=1; // 作訪問標(biāo)記?
??? p=L[v].firstedge;? //p指向v的鄰接表首結(jié)點(diǎn)
??? while (p!=NULL)? //檢查v的所有鄰接點(diǎn)
?? { w=p->adjacent;? //w是v的鄰接點(diǎn)
?? ?if(L[w].mark==0)
dfs(w);
????? elseif(L[w].mark==1)
cycle=1;
????????? //dfs(w)尚未終止，置有回路標(biāo)記
??? p=p->next;
??? }
? L[v].mark=2;???????? ?? //置dfs(v)終止標(biāo)記
}
?
?
2.先廣搜索
???????? 優(yōu)先選擇廣度，比如A與C、D、E、D，訪問A結(jié)點(diǎn)后，依次訪問C、D、E、D，不會繼續(xù)遞歸訪問與C相連接的結(jié)點(diǎn)。
?
是二叉樹按層遍歷的推廣，算法描述：
步驟1）將圖中所有頂點(diǎn)作“未訪問過”標(biāo)記。
步驟2）任選圖中一個(gè)尚未訪問過的頂點(diǎn)v作搜索起點(diǎn)。
步驟3）訪問v。
步驟4）相繼地訪問與v相鄰而尚未訪問的所有頂點(diǎn)
? w1，w2……，并依次訪問與這些頂點(diǎn)相鄰而尚未訪問過的所有頂點(diǎn)。
??? 反復(fù)如此，直到找不到這樣的頂點(diǎn)。
步驟5）若圖中尚有未訪問過的頂點(diǎn)，則轉(zhuǎn)步驟2；否則，搜索結(jié)束。
?
示例
?
?
?
?
?
先廣搜索的實(shí)現(xiàn)：
圖存儲形式：鄰接表
用一個(gè)隊(duì)存放等待訪問的頂點(diǎn)。
頂點(diǎn)結(jié)點(diǎn)含有進(jìn)隊(duì)否標(biāo)志域mark。
未進(jìn)隊(duì)，mark值為0；已進(jìn)過隊(duì)，mark值為1。
注意點(diǎn)：使用隊(duì)結(jié)構(gòu)記錄搜索路線（存放著等待訪問的頂點(diǎn)）
?
?
?
?
圖的先廣搜索算法：
?
void? bfs( )
?? { Eptr? p;???? int? u,v,w,first,last,q[n];?
1.?? first=last=0;? //隊(duì)列初始化
2.?? for(u=0;u<n;u++) L[u].mark=0;? //初始化
3.?? for(u=0;u<n;u++) //找未進(jìn)過隊(duì)的頂點(diǎn)
4.???? if(!L[u].mark)? //若u未進(jìn)隊(duì)
5.????? {? q[last++]=u;? //u進(jìn)隊(duì)
6.???????? L[u].mark=1;? //置u進(jìn)隊(duì)標(biāo)記
7.???????? while(first!=last) //當(dāng)隊(duì)列不空時(shí)循環(huán)
8.?????????? { v=q[first++];? //v出隊(duì)
9.??????? visit(v);? //訪問v
10.??????? p=L[v].firstedge; //檢查v的鄰接點(diǎn)
11.??????? while(p!=NULL)
12.????????? { w=p->adjacent;? // w是v的鄰接點(diǎn)
13.???????????? if (!L[w].mark)? //若w未進(jìn)過隊(duì)
14.??????????????? { q[last++]=w; L[w].mark=1; } w進(jìn)隊(duì)
15.?????????????? p=p->next; //找v的下一個(gè)鄰接點(diǎn)
??????????????? } // 與句12對應(yīng)
??????????? } // 與句8對應(yīng)，到隊(duì)空
??????? } // 與句5對應(yīng)，以u為起點(diǎn)的搜索結(jié)束
?? }
?
兩種搜索算法對照：
1.先深搜索算法比先廣搜索算法結(jié)構(gòu)好。
2.先深搜索可寫成遞歸形式，而先廣搜索無法寫成遞歸形式
3.先深搜索更常用
?
轉(zhuǎn)載于:https://www.cnblogs.com/gd-luojialin/p/8509515.html
總結(jié)
- 上一篇： NTP服务器时间同步
- 下一篇： hbase权威指南学习笔记