圖論中搜索算法講座

圖論中搜索算法講座第一頁，共五十七頁，2022年，8月28日圖論中搜索算法和最短路徑算法2第二頁，共五十七頁，2022年，8月28日ReadEuler,readEuler,heisthemasterofusall.

P.-S.deLaplace3第三頁，共五十七頁，2022年，8月28日4第四頁，共五十七頁，2022年，8月28日5第五頁，共五十七頁，2022年，8月28日§1圖_基本概念§2圖的存儲結構

§4最短路徑§3圖的遍歷算法內(nèi)容6第六頁，共五十七頁，2022年，8月28日圖是一種較線性表和樹更為復雜的數(shù)據(jù)結構。線性表:

線性結構樹:

層次結構圖:

結點之間的關系可以是任意的，即圖中任意兩個數(shù)據(jù)元素之間都可能相關。如：

ABCDE第一節(jié):圖的基本概念7第七頁，共五十七頁，2022年，8月28日1圖的定義和基本術語圖G

是由兩個集合—頂點集V(G)

和邊集E(G)

組成的，記作G=(V(G)，E(G))，簡稱G=(V，E)。ABCDEABCDEABCDEV是頂點的有窮非空集合

E是兩個頂點之間的關系，即邊的有窮集合

8第八頁，共五十七頁，2022年，8月28日無向圖和有向圖無向圖:

邊是頂點的無序對，即邊沒有方向性。v1v2v3v5v4上面無向圖可以表示為：G=(V,E),其中V={v1,v2,v3,v4,v5}E={(v1,v2)

,(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}(v1,v2)表示頂點v1和v2之間的邊，(v1,v2)=(v2,v1)。9第九頁，共五十七頁，2022年，8月28日有向圖:

其邊是頂點的有序對，即邊有方向性。v1v2v4v3V={v1,v2,v3,v4}E={<v1,v2>

,<v1,v3>,<v3,v4>,<v4,v1>,<v2,v1>}在有向圖中，通常邊稱為弧，<v1,v2>表示頂點v1到v2的弧。稱v1為弧尾，稱v2為弧頭。<v1,v2>≠<v2,v1>上面有向圖可以表示為：G=(V,E),其中10第十頁，共五十七頁，2022年，8月28日帶權無向圖(無向網(wǎng))和帶權有向圖(有向網(wǎng))有時對圖的邊或弧賦予相關的數(shù)值，這種與圖的邊或弧相關的數(shù)值叫做權。

這種帶權的圖通常稱為網(wǎng)。

帶權的有向圖稱為有向網(wǎng)。帶權的無向圖稱為無向網(wǎng)。ABCDE53821497這些權可以表示從一個頂點到另一個頂點的距離?？梢员硎緩囊粋€頂點到另一個頂點的耗費。11第十一頁，共五十七頁，2022年，8月28日子圖假設有兩個圖

G=(V,E)和

G’=(V’,E’)，如果

V’V，且

E’E，則稱

G’

為

G

的子圖。

v1v2v4v3求子圖v1v1v3v1v4v3v1v2v4v3v1v2v4v312第十二頁，共五十七頁，2022年，8月28日鄰接與關聯(lián)對于無向圖

G=(V,E)，如果邊

(v,v’)∈E，則稱頂點

v和

v’互為鄰接點，即

v

和

v’

相鄰接。

邊

(v,v’)依附于頂點

v和

v’，或者說

(v,v’)

與頂點

v

和

v’

相關聯(lián)。

對于有向圖

G=(V,E)，如果弧

<v,v’>∈E，則稱頂點

v鄰接到頂點

v’，頂點

v’鄰接自頂點

v。

vv’vv’弧<v,v’>

和頂點v,v’

相關聯(lián)。13第十三頁，共五十七頁，2022年，8月28日頂點的度對于無向圖，頂點

v的度是和

v相關聯(lián)的邊的數(shù)目，記做TD(v)。

v1v2v3v5v4頂點v3的度為

3對于有向圖，頂點

v的度

TD(V)分為兩部分——出度、入度。

以頂點

v為頭的弧的數(shù)目稱為

v的入度，記為ID(v)

；以頂點

v為尾的弧的數(shù)目稱為

v的出度，記為OD(v)；

頂點

v的度為TD(v)=ID(v)+OD(v)。

14第十四頁，共五十七頁，2022年，8月28日v1v2v4v3頂點v1

的出度為2頂點v1

的入度為1頂點v1

的度為315第十五頁，共五十七頁，2022年，8月28日路徑、鏈、簡單路徑、回路(環(huán))、簡單回路無向圖G中若存在一條有窮非空序列w=v0e1

v1e2

v2

ek

vk

，其中vi和ei分別為頂點和邊，則稱w

是從頂點v0到vk的一條路徑?！旤cv0和vk分別稱為路徑

w

的起點和終點。路徑的長度是路徑上的邊的數(shù)目。v0v1v2vk-1vk...e1e2ek起點和終點相同的路徑稱為回路(環(huán))。16第十六頁，共五十七頁，2022年，8月28日若路徑w的邊e1,e2,,ek

互不相同，則稱w為鏈。…若路徑w的頂點v0,v1,,vk

互不相同，則稱w為簡單路徑。…v0v1v2vk-1vk...e1e2ek鏈是否為簡單路徑?簡單路徑是否為鏈?不一定一定e1e2e3e4e5除了第一個頂點和最后一個頂點外，其余頂點不重復出現(xiàn)的回路稱為簡單回路(簡單環(huán))。17第十七頁，共五十七頁，2022年，8月28日例157324G26路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，118第十八頁，共五十七頁，2022年，8月28日有向圖G中若存在一條有窮非空序列w=v0e1

v1e2

v2

ek

vk

，其中vi和ei分別為頂點和弧，則稱w

是從頂點v0到vk的一條路徑。…v0v1v2vk-1vk...e1e2ek鏈簡單路徑回路簡單回路19第十九頁，共五十七頁，2022年，8月28日例245136G1路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，320第二十頁，共五十七頁，2022年，8月28日連通、連通圖無向圖G，如果從頂點

v

到頂點

v’

有路徑，則稱

v

和

v’

是連通的。

如果對于無向圖

G

中任意兩個頂點

vi,vj

∈V,vi和

vj都是連通的，則稱

G是連通圖。

v1v2v3v5v4是否為連通圖21第二十一頁，共五十七頁，2022年，8月28日第2節(jié)圖的存儲結構順序存儲鄰接矩陣鏈式存儲鄰接表鄰接多重表十字鏈表如何表達頂點之間存在的聯(lián)系？v1v2v4v322第二十二頁，共五十七頁，2022年，8月28日2.1鄰接矩陣設圖G=(V，E)具有n(n≥1)個頂點v1,v2,,vn

和m

條邊或弧e1,e2,,em

，則G的鄰接矩陣是n×n

階矩陣，記為A(G)

。……其每一個元素aij

定義為:鄰接矩陣存放n

個頂點信息和n2

條邊或弧信息。aij=01頂點vi與vj不相鄰接頂點vi與vj相鄰接v1v2v4v3例有向圖GA(G)=12341234011000000001100023第二十三頁，共五十七頁，2022年，8月28日v1v2v3v5v4例無向圖G0101010101010111010001100A(G)=1234512345優(yōu)點:1.容易判斷任意兩個頂點之間是否有邊或弧。2.容易求取各個頂點的度。24第二十四頁，共五十七頁，2022年，8月28日無向圖，頂點vi

的度是鄰接矩陣中第

i行或第

i列的元素之和。例G中，v1

的度為2。v1v2v3v5v4例無向圖G0101010101010111010001100A(G)=123451234525第二十五頁，共五十七頁，2022年，8月28日v1v2v4v3例有向圖GA(G)=123412340110000000011000有向圖，頂點vi

的出度是鄰接矩陣中第

i行的元素之和。頂點vi

的入度是鄰接矩陣中第

i列的元素之和。例v1

的出度為2；入度為1。26第二十六頁，共五十七頁，2022年，8月28日無向圖的鄰接矩陣都是對稱矩陣。有向圖的鄰接矩陣一般不對稱。12341234011000000001100001010101010101110100011001234512345故無向圖可以采用壓縮存儲方式無向圖有向圖27第二十七頁，共五十七頁，2022年，8月28日帶權圖(網(wǎng))的鄰接矩陣v1v2v3v5v4v65487935651aij=

wij∞頂點vi與vj相鄰接頂點vi與vj不相鄰接∞5∞7∞∞∞∞4∞∞∞

8∞∞∞∞9∞∞5∞∞6∞∞∞5∞∞A=

123456123456

3∞∞∞1∞28第二十八頁，共五十七頁，2022年，8月28日鄰接矩陣存儲的缺點：這種存貯方式的空間復雜度正比于圖的結點個數(shù)的平方，所以，當圖中結點很多但邊卻很少時，采用這種結構會造成很大的浪費。29第二十九頁，共五十七頁，2022年，8月28日2.2鄰接表對圖中每一個頂點建立一個單鏈表，指示與該頂點關聯(lián)的邊或出弧。vexinfofirstarcadjvexnextarcarcinfo表結點頭結點adjvex:鄰接頂點位置arcinfo:邊的信息nextarc

:下一條關聯(lián)邊結點vexinfo:頂點的信息firstarc:第一條關聯(lián)邊結點v1v2v3v5v4v6548793565130第三十頁，共五十七頁，2022年，8月28日v1v2v3v5v4例無向圖Ge1e2e3e4e5e612345v1v2v3v4v54e22e1∧5e43e31e1∧5e64e52e3∧3e51e2∧3e62e4∧如何獲取頂點的度？頂點vi

的度為第i條鏈表中的結點數(shù)。需要多少存儲空間？n+2e31第三十一頁，共五十七頁，2022年，8月28日v1v2v4v3例有向圖Ge1e2e3e41234v1v2v3v43e22e1∧∧4e3∧1e4∧32第三十二頁，共五十七頁，2022年，8月28日鄰接矩陣與鄰接表存儲空間求頂點的度求頂點的鄰接頂點鄰接表省一樣一樣判斷兩個頂點是否關聯(lián)鄰接矩陣方便0101010101010111010001100123451234512345v1v2v3v4v54e22e1∧5e43e31e1∧5e64e52e3∧3e51e2∧3e62e4∧33第三十三頁，共五十七頁，2022年，8月28日3圖的遍歷與樹的遍歷類似，如果從圖中某一頂點出發(fā)訪遍圖中所有頂點，且使每一個頂點僅被訪問一次，這一過程稱為圖的遍歷。圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等算法的基礎。通常有兩條遍歷圖的路徑:深度優(yōu)先搜索、廣度優(yōu)先搜索。圖的遍歷相對復雜，為了避免同一個頂點被訪問多次，增設一個輔助的布爾數(shù)組visited[0..n-1]

指示頂點是否已被訪問過。34第三十四頁，共五十七頁，2022年，8月28日3.1深度優(yōu)先搜索深度優(yōu)先搜索是類似于樹的一種先序遍歷v1v2v3v5v4v6v7v8圖可分為三部分:基結點第一個鄰接結點導出的子圖其它鄰接頂點導出的子圖深度優(yōu)先搜索順序:v1v2v4v8v5v3v6v735第三十五頁，共五十七頁，2022年，8月28日1.從圖中某個頂點v

出發(fā)，訪問此頂點；2.然后依次從v

的未被訪問的鄰接點出發(fā)進行深度優(yōu)先遍歷；3.直至圖中所有和v

有路徑相通的頂點都被訪問到。4.若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點做起始點，重復上述過程，直至圖中所有頂點都被訪問到。算法描述:36第三十六頁，共五十七頁，2022年，8月28日深度優(yōu)先遍歷算法(DFS)遞歸算法開始訪問V0,置標志求V0鄰接點有鄰接點w求下一鄰接點wV0W訪問過結束NYNYDFS開始標志數(shù)組初始化Vi=1Vi訪問過DFSVi=Vi+1Vi==Vexnums結束NNYY37第三十七頁，共五十七頁，2022年，8月28日visited[v]=TRUE

；printf(v)；//訪問此頂點for(w=FirstAdjVex(G,v)；w>=0；w=NextAdjVex(G,v,w))if(!visited[w])DFSTraverse(G,w)

；returnOK；voidDFSTraverse(GraphG，intv){//visited[0..n-1]初始為0；v指示頂點在數(shù)組中的位置；}38第三十八頁，共五十七頁，2022年，8月28日v1v2v3v5v4v6v7v8過程分析v1v2v3v4v6v8v5v7深度優(yōu)先搜索順序:v1v2v4v8v5v3v6v739第三十九頁，共五十七頁，2022年，8月28日棧實現(xiàn)深度優(yōu)先搜索v1v2v3v4v6v8v5v7深度優(yōu)先搜索順序:v1v2v4v8v5v3v6v7v1v2v4v8v5v3v6v7總是從棧頂出發(fā)搜索！40第四十頁，共五十七頁，2022年，8月28日initstack(S)；visited[v]=TRUE；Push(S,v)

；printf(v)；Gettop(S,v)

；for(w=FirstAdjVex(G,v)；w>=0；w=NextAdjVex(G,v,w))if(!visited[w]){visited[w]=TRUE；Push(S,w)；printf(w)；Gettop(S,v)；}Pop(S)

；while(!StackEmpty(S)){}voidDFSTraverse(GraphG，intv){}41第四十一頁，共五十七頁，2022年，8月28日深度優(yōu)先搜索的C語言實現(xiàn)：typedefstructnode{intadjvex;//鄰接點域，存放與Vi鄰接的點在表頭數(shù)組中的位置structnode*next;//鏈域，指示下一條邊或弧}JD;//表頭接點：typedefstructtnode{intvexdata;//存放頂點信息structnode*firstarc;//指示第一個鄰接點}TD;TDga[M];//ga[0]不用v1v2v3v5v4e1e2e3e4e5e642第四十二頁，共五十七頁，2022年，8月28日voidtraver(TDg[],intn){inti;staticintvisited[M];for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0) dfs(g,i,visited);}43第四十三頁，共五十七頁，2022年，8月28日voiddfs(TDg[],intv,intvisited[]){JD*w;inti;printf("%d",v);visited[v]=1;w=g[v].firstarc;while(w!=NULL){i=w->adjvex;if(visited[i]==0) dfs(g,i,visited);w=w->next;}}44第四十四頁，共五十七頁，2022年，8月28日3.2廣度優(yōu)先搜索廣度優(yōu)先搜索類似于樹的層次遍歷，廣度優(yōu)先搜索順序:v1v2v3v4v5v6v7v8v1v2v3v5v4v6v7v8只有父輩結點被訪問后才會訪問子孫結點！把圖人為的分層，按層遍歷。45第四十五頁，共五十七頁，2022年，8月28日1.從圖中某個頂點v

出發(fā)，訪問此頂點；2.然后依次訪問v

的各個未曾訪問的鄰接點；4.直至圖中所有和v

有路徑相通的頂點都被訪問到。5.若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點做起始點，重復上述過程，直至圖中所有頂點都被訪問到。3.然后依次從這些鄰接點出發(fā)再依次訪問它們的鄰接點；算法描述:46第四十六頁，共五十七頁，2022年，8月28日v1v2v3v5v4v6v7v8過程分析廣度優(yōu)先搜索順序:v1v2v3v4v6v5v7v8v1v2v3v4v5v6v7v847第四十七頁，共五十七頁，2022年，8月28日廣度優(yōu)先遍歷算法開始標志數(shù)組初始化Vi=1Vi訪問過BFSVi=Vi+1Vi==Vexnums結束NNYY48第四十八頁，共五十七頁，2022年，8月28日開始訪問V0,置標志求V鄰接點ww存在嗎V下一鄰接點ww訪問過結束NYNYBFS初始化隊列V0入隊隊列空嗎隊頭V出隊訪問w,置標志w入隊NaaY49第四十九頁，共五十七頁，2022年，8月28日隊列實現(xiàn)廣度優(yōu)先搜索算法InitQueue(Q)；visited[v]=TRUE；EnQueue(Q,v)

；printf(v)；DeQueue(Q,u)；while(!QueueEmpty(Q)){}voidBFSTraverse(GraphG，intv){//visited[0..n-1]初始均為0；v指示頂點在數(shù)組中的位置；}for(w=FirstAdjVex(G,u)；w>=0；w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE；EnQueue(Q,w)；printf(w)；}//其鄰接頂點均送入隊列50第五十頁，共五十七頁，2022年，8月28日4最短路徑ABCGFED旅客希望?？空驹缴僭胶茫瑒t應選擇A——B——C——G旅客考慮的是旅程越短越好，1120920720210540340640190A——D——E——F——G51第五十一頁，共五十七頁，2022年，8月28日帶權圖的最短路徑計算問題通常在實際中，航運、鐵路、船行都具有有向性，故我們以帶權有向圖為例介紹最短路徑算法。帶權無向圖的最短路徑算法也通用。從單個源點到其余各頂點的最短路徑算法。52第五十二頁，共五十七頁，2022年，8月28日4.1從單個源點到其余各頂點的最短路徑算法——Dijkstra算法思想:貪心算法(局部最優(yōu))，按路徑長度遞增的次序產(chǎn)生最短路徑。貪心算法:利用局部最優(yōu)來計算全局最優(yōu)。利用已得到的頂點的最短路徑來計算其它頂點的最短路徑。例，v5v0v1v4v3601005v21030201050求從v0

到其余各頂點的最短路徑。1.初始，D[i]的值為v0

到vi

的弧的權值D[i]

表示v0

到vi

的最短路徑的長度顯然，D[i]

中的最小值D[2]

便是v0到v2

的最短路徑的長度，Path[2]=(v0,v2)Path[i]表示v0

到vi

的最短路徑53第五十三頁，共五十七頁，2022年，8月28日設下一條最短路徑的終點是vk

，則這條最短路徑或者是(v0,vk)、或者是v0經(jīng)過v2

或v4到達vk

的路徑；2.如何尋找下一條最短路徑？例，v5v0v1v4v3601005v21030201050設下一條最短路徑的終點是vj

，則這條最短路徑或者是(v0,vj)、或者是

v0經(jīng)過v2到達vj

的路徑；其中取D[i](D[2]除外)

中的最小值得到v4，Path[4]=(v0,v4)。3.如何尋找下一條最短路徑？取D[i](D[2]、D[4]除外)

中的最小值得到v3

，Path[3]=(v0,v4,