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权威指南学习笔记
