圖的搜索算法課件

1、圖的搜索算法課件圖的搜索算法課件第五章第五章 圖的搜索算法圖的搜索算法 5 51 1 圖搜索概述圖搜索概述 5 51 11 1 圖及其術(shù)語圖及其術(shù)語 5 51 12 2 圖搜索及其術(shù)語圖搜索及其術(shù)語5 52 2 廣度優(yōu)先搜索廣度優(yōu)先搜索 5 52 21 1 算法框架算法框架 522 廣度優(yōu)先搜索的廣度優(yōu)先搜索的圖的搜索算法課件圖的搜索算法課件上一頁 下一頁 返回首頁 圖圖是一種限止最少的數(shù)據(jù)結(jié)構(gòu)，因此更接近現(xiàn)實，實際問是一種限止最少的數(shù)據(jù)結(jié)構(gòu)，因此更接近現(xiàn)實，實際問題中很多數(shù)據(jù)關(guān)系都可以抽象成圖，相關(guān)問題則可利用圖的基題中很多數(shù)據(jù)關(guān)系都可以抽象成圖，相關(guān)問題則可利用圖的基本算法進行求解，很早就

2、有專門研究圖的是一門數(shù)學(xué)學(xué)科本算法進行求解，很早就有專門研究圖的是一門數(shù)學(xué)學(xué)科“圖圖論論”；其中的計算問題包括圖的搜索、路徑問題、連通性問題、；其中的計算問題包括圖的搜索、路徑問題、連通性問題、可平面性檢驗、著色問題、網(wǎng)絡(luò)優(yōu)化等。圖論中的著名算法有：可平面性檢驗、著色問題、網(wǎng)絡(luò)優(yōu)化等。圖論中的著名算法有：求最小生成樹的求最小生成樹的Kruskal算法、求最短路徑的算法、求最短路徑的Dijkstra算法算法和和Floyd算法、求二部圖最大匹配（指派問題）的匈牙利算法、算法、求二部圖最大匹配（指派問題）的匈牙利算法、求一般圖最大匹配的求一般圖最大匹配的Edmonds“花花”算法、求網(wǎng)絡(luò)最大流和最算

3、法、求網(wǎng)絡(luò)最大流和最小割的算法等。其中的一些算法在數(shù)據(jù)結(jié)構(gòu)課程中已經(jīng)學(xué)習(xí)過小割的算法等。其中的一些算法在數(shù)據(jù)結(jié)構(gòu)課程中已經(jīng)學(xué)習(xí)過了。了。 圖的搜索算法課件圖的搜索算法課件1顯式圖與隱式圖顯式圖與隱式圖 在路徑問題、連通性問題、可平面性檢驗、著色在路徑問題、連通性問題、可平面性檢驗、著色問題和網(wǎng)絡(luò)優(yōu)化等問題中，圖的結(jié)構(gòu)是顯式給出的，問題和網(wǎng)絡(luò)優(yōu)化等問題中，圖的結(jié)構(gòu)是顯式給出的，包括圖中的頂點、邊及權(quán)重，這類圖我們稱為包括圖中的頂點、邊及權(quán)重，這類圖我們稱為顯式圖顯式圖，也就是一般意義上的也就是一般意義上的圖圖。 隱式圖隱式圖是由問題的初始結(jié)點，為了求解或求證是由問題的初始結(jié)點，為了求解或求證問題

4、，根據(jù)題目的規(guī)則（一般是由題目的意思隱含問題，根據(jù)題目的規(guī)則（一般是由題目的意思隱含給出的），也就是生成子結(jié)點的約束條件，逐步擴給出的），也就是生成子結(jié)點的約束條件，逐步擴展結(jié)點，直到得到目標(biāo)結(jié)點為止的一個展結(jié)點，直到得到目標(biāo)結(jié)點為止的一個隱式的圖隱式的圖。 5 51 11 1 圖及其術(shù)語圖及其術(shù)語圖的搜索算法課件圖的搜索算法課件2.顯式圖的常用術(shù)語 如圖如圖5-1所示的所示的 ， ， 均為顯式圖均為顯式圖 (Graph)。圖。圖中的這些點中的這些點(v1,v2,vn)(v1,v2,vn)被稱為被稱為頂點頂點 (vertex)或或結(jié)點結(jié)點，連，連接頂點的曲線或直線稱為接頂點的曲線或直線稱為邊邊

5、 (edge)。 通常將這種由若干個頂點以及連接某些頂點的邊所組通常將這種由若干個頂點以及連接某些頂點的邊所組成的圖形稱為成的圖形稱為圖圖，頂點通常被稱作是圖中的，頂點通常被稱作是圖中的數(shù)據(jù)元素數(shù)據(jù)元素 .上一頁 下一頁 返回首頁v1v2v3v4v1v3v2v4v1v2v3v4v5圖圖 5-1 v1v3v2v434296圖圖 5-2 圖的搜索算法課件圖的搜索算法課件圖 帶權(quán)圖帶權(quán)圖：j即圖即圖5 -2給圖給圖 5-1中各圖的邊上附加一個代表性數(shù)據(jù)中各圖的邊上附加一個代表性數(shù)據(jù) (比如表示長度、流量或其他比如表示長度、流量或其他 )，則稱其為帶權(quán)圖，則稱其為帶權(quán)圖 。環(huán)環(huán) (cycle)：圖：圖

6、5-1中中 圖中的圖中的 v 1點本身也有邊相連，這種邊點本身也有邊相連，這種邊稱為環(huán)。稱為環(huán)。 有限圖有限圖：頂點與邊數(shù)均為有限的圖，如圖：頂點與邊數(shù)均為有限的圖，如圖 5-1中的三個圖均屬中的三個圖均屬于有限圖。于有限圖。 簡單圖簡單圖：沒有環(huán)且每兩個頂點間最多只有一條邊相連的圖，如：沒有環(huán)且每兩個頂點間最多只有一條邊相連的圖，如圖圖 5-1中的中的 圖。圖。 鄰接與關(guān)聯(lián)鄰接與關(guān)聯(lián)：當(dāng)（：當(dāng)（ v 1， v 2） E，或，或 E，即，即 v 1， v 2間有邊相連時，則稱間有邊相連時，則稱 v 1和和 v 2是相鄰的，它們互為鄰接是相鄰的，它們互為鄰接點（點（ adjacent），同時稱（

7、），同時稱（ v 1， v 2）或）或 是與頂是與頂點點 v 1、 v 2相關(guān)聯(lián)的邊。相關(guān)聯(lián)的邊。 上一頁 下一頁 返回首頁圖的搜索算法課件圖的搜索算法課件頂點的度數(shù)頂點的度數(shù) (degree)：從該頂點引出的邊的條數(shù)，即與該頂點相：從該頂點引出的邊的條數(shù)，即與該頂點相關(guān)聯(lián)的邊的數(shù)目，簡稱度。關(guān)聯(lián)的邊的數(shù)目，簡稱度。入度（入度（ indegree）：有向圖中把以頂點：有向圖中把以頂點 v為終點的邊的條數(shù)稱為為終點的邊的條數(shù)稱為是頂點是頂點 v的入度。的入度。 出度（出度（ outdegree）：有向圖中把以頂點：有向圖中把以頂點 v為起點的邊的條數(shù)稱為起點的邊的條數(shù)稱為是頂點為是頂點 v的出度

8、。的出度。終端頂點終端頂點：有向圖中把出度為：有向圖中把出度為 0的頂點稱為終端頂點，如圖的頂點稱為終端頂點，如圖 5-1中中 圖的圖的 v 3。 路徑與路長：路徑與路長：在圖在圖 G=( V， E)中，如果存在由不同的邊中，如果存在由不同的邊 (v i0， v i1 )， (v i1， v i2 )， ， (v in-1， v in )或是或是 ， ， ， )組成的序列，則稱頂點組成的序列，則稱頂點 v i0， v in是連通的，頂點序列（是連通的，頂點序列（ v i0， v i1， v i2， ， v in）是從頂點是從頂點 v i0到頂點到頂點 v in的一條道路。路長是道路上邊的數(shù)目，

9、的一條道路。路長是道路上邊的數(shù)目， v i0到到 v in的這條道路上的路長為的這條道路上的路長為 n。 連通圖：連通圖：對于圖中任意兩個頂點對于圖中任意兩個頂點 v i、 v j V， v i、 v j之間有之間有道路相連，則稱該圖為連通圖。如道路相連，則稱該圖為連通圖。如 5-1中的中的 圖。圖。網(wǎng)絡(luò)：網(wǎng)絡(luò)：帶權(quán)的連通圖，如圖帶權(quán)的連通圖，如圖 5-2所示。所示。圖的搜索算法課件圖的搜索算法課件3 3隱式圖術(shù)語隱式圖術(shù)語 1 1）子集樹子集樹 當(dāng)要求解的問題需要是在當(dāng)要求解的問題需要是在n n 個元素的子集中進行搜索，其搜個元素的子集中進行搜索，其搜索空間樹被稱作索空間樹被稱作子集樹（子集

10、樹（subset treesubset tree）。這。這n n個元素都有在子個元素都有在子集中或被選取記為集中或被選取記為1 1，不在子集中或被舍去記為，不在子集中或被舍去記為0 0，這樣搜索空，這樣搜索空間為：間為： （0 0，0 0，0 0，0 0），（），（0 0，0 0，0 0，1 1），）， （0 0，0 0，1 1，0 0），（），（0 0，0 0，1 1，1 1），）， （1 1，1 1，1 1，1 1）。）。共共2 2n n 個狀態(tài)。若表示為個狀態(tài)。若表示為樹形結(jié)構(gòu)樹形結(jié)構(gòu)就是一棵有就是一棵有2 2n n個葉結(jié)點的二叉?zhèn)€葉結(jié)點的二叉樹，對樹中所有分支進行遍歷的算法都必須耗時樹

11、，對樹中所有分支進行遍歷的算法都必須耗時O（2n）。 上一頁上一頁 下一頁下一頁 返回返回首頁首頁圖的搜索算法課件圖的搜索算法課件圖圖5-3 n=3的子集樹的子集樹 上一頁 下一頁 返回首頁圖的搜索算法課件圖的搜索算法課件2）排列樹）排列樹 上一頁上一頁 下一頁下一頁 返回返回首頁首頁 當(dāng)要求解的問題需要在當(dāng)要求解的問題需要在n n 元素的排列中搜索問題的解時，元素的排列中搜索問題的解時，解空間樹被稱作解空間樹被稱作排列樹（排列樹（permutation treepermutation tree）。搜索空間為：搜索空間為：（1 1，2 2，3 3，n-1n-1，n n）, , （2 2，1 1

12、，3 3，n-1n-1，n n）, , （2 2，3 3，1 1，n-1n-1，n n）, ,（2 2，3 3，4 4，1 1，n-1n-1，n n）, ,（n n，n-1n-1，3 3，2 2，1 1） 第一個元素有第一個元素有n 種選擇，第二個元素有種選擇，第二個元素有n-1種選擇，第三個種選擇，第三個元素有元素有n-2種選擇，種選擇，第，第n個元素有個元素有1種選擇，共計種選擇，共計n!個狀態(tài)。個狀態(tài)。若表示為樹形就是一個若表示為樹形就是一個n度樹，這樣的樹有度樹，這樣的樹有n! 個葉結(jié)點，所以每個葉結(jié)點，所以每一個遍歷樹中所有節(jié)點的算法都必須耗時一個遍歷樹中所有節(jié)點的算法都必須耗時O(

13、n! ) 圖的搜索算法課件圖的搜索算法課件上一頁 下一頁 返回首頁圖圖5-3 n=4的部分子集樹的部分子集樹 12503418 X1=115121o75173133282623211383292419454035615651141196416303227252220234 X2=2341 3 41 241 23X3=311 43 42 32 43 44 3 4 2 3 2 4 3 4 1 3 x4=1 圖的搜索算法課件圖的搜索算法課件4 4圖的存儲圖的存儲 1 1）鄰接矩陣法鄰接矩陣法 上一頁上一頁 下一頁下一頁 返回返回首頁首頁 鄰接矩陣鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣，是表示頂點之間相

14、鄰關(guān)系的矩陣，設(shè)設(shè)G=(V,E)G=(V,E)是具有是具有n n個頂點的個頂點的圖圖，則，則G G的鄰接矩陣可定義為：的鄰接矩陣可定義為： Ai,j=1, Ai,j=1, 若（若（Vi,Vj)Vi,Vj)或或是是E(G)E(G)中的邊。中的邊。 Ai,j=0, Ai,j=0, 若若 (Vi,Vj)(Vi,Vj)或或不是不是E(G)E(G)中的邊。中的邊。若若G G是是網(wǎng)絡(luò)網(wǎng)絡(luò)，則鄰接矩陣可定義為：，則鄰接矩陣可定義為： Ai,j=WAi,j=Wij ij 若（若（Vi,Vj)Vi,Vj)或或?qū)儆趯儆贓(G);E(G); Ai,j=0或或 若（若（Vi,Vj）或）或 不屬于不屬于E(G); 其中

15、，其中，Wij表示邊上的權(quán)值，表示邊上的權(quán)值，表示一個計算機允許的，大于表示一個計算機允許的，大于所有邊上權(quán)值的數(shù)；所有邊上權(quán)值的數(shù)； 圖的搜索算法課件圖的搜索算法課件 上一頁上一頁 下一頁下一頁 返回返回首頁首頁圖的搜索算法課件圖的搜索算法課件2 2）鄰接表）鄰接表 上一頁上一頁 下一頁下一頁 返回首頁返回首頁 例例11 對于圖對于圖G G中的每個結(jié)點中的每個結(jié)點Vi, Vi, 把所有鄰接于把所有鄰接于ViVi的頂點的頂點VjVj鏈成一個鏈成一個單鏈表，這個單鏈表就稱為頂點單鏈表，這個單鏈表就稱為頂點ViVi的鄰接表。的鄰接表。 鄰接表由邊表和頂點兩部分組成。鄰接表由邊表和頂點兩部分組成。

16、邊表邊表為一個為一個單鏈表單鏈表，每個表結(jié)點均有兩個域：，每個表結(jié)點均有兩個域： 鄰接點域鄰接點域adjvexadjvex，存放與，存放與vivi相鄰接的頂點相鄰接的頂點v vj j的序號的序號j j。 鏈 域鏈 域 n e x tn e x t ， 將 鄰 接 表 的 所 有 表 結(jié) 點 鏈 在 一 起 。， 將 鄰 接 表 的 所 有 表 結(jié) 點 鏈 在 一 起 。 頂 點 表頂 點 表 為 一 數(shù) 組 ， 每 個 元 素 均 有 兩 個 域 ：為 一 數(shù) 組 ， 每 個 元 素 均 有 兩 個 域 ： 頂 點 域頂 點 域 v e r t e xv e r t e x ， 存 放 頂 點

17、， 存 放 頂 點 v vi i的 信 息的 信 息 指針域指針域firstedgefirstedge， v vi i的邊表的頭指針。的邊表的頭指針。 對于無向圖來說，對于無向圖來說，ViVi的鄰接表中每個表結(jié)點都對應(yīng)于與的鄰接表中每個表結(jié)點都對應(yīng)于與ViVi相相關(guān)聯(lián)的一條邊，關(guān)聯(lián)的一條邊， 對于有向圖來說，對于有向圖來說，ViVi的鄰接表中每個表結(jié)點對應(yīng)于的鄰接表中每個表結(jié)點對應(yīng)于ViVi為始點為始點射出的一條邊。射出的一條邊。 圖的搜索算法課件圖的搜索算法課件圖7.1 上一頁上一頁 下一頁下一頁 返回首返回首頁頁圖圖5-5 圖圖5-1中（中（1）圖的鄰接表）圖的鄰接表 圖的搜索算法課件圖的

18、搜索算法課件 512 圖搜索及其術(shù)語1 1窮舉搜索與啟發(fā)式搜索窮舉搜索與啟發(fā)式搜索 窮舉搜索窮舉搜索是對圖的最基本的搜索算法，是蠻力策略的一種是對圖的最基本的搜索算法，是蠻力策略的一種表現(xiàn)形式。即不考慮給定問題的特有性質(zhì)，按事先定好的順序，表現(xiàn)形式。即不考慮給定問題的特有性質(zhì)，按事先定好的順序，依次運用規(guī)則，盲目搜索的方法。依次運用規(guī)則，盲目搜索的方法。 啟發(fā)式搜索啟發(fā)式搜索是利用一些是利用一些啟發(fā)信息啟發(fā)信息，提前判斷出先搜索哪些，提前判斷出先搜索哪些狀態(tài)可能盡快找到問題的解或某些情況不可能取到最優(yōu)解，從狀態(tài)可能盡快找到問題的解或某些情況不可能取到最優(yōu)解，從而可以提前舍棄對這些狀態(tài)的嘗試。即

19、考慮給定問題的特有性而可以提前舍棄對這些狀態(tài)的嘗試。即考慮給定問題的特有性質(zhì)，選用合適的細(xì)則，提高搜索的效率。質(zhì)，選用合適的細(xì)則，提高搜索的效率。 上一頁 下一頁 返回首頁圖的搜索算法課件圖的搜索算法課件2相關(guān)概念和術(shù)語 上一頁上一頁 下一頁下一頁 返回返回首頁首頁 問題狀態(tài)問題狀態(tài): :樹中的每一個結(jié)點確定所求解問題的一個問題狀態(tài)。樹中的每一個結(jié)點確定所求解問題的一個問題狀態(tài)。狀態(tài)空間狀態(tài)空間: :由根結(jié)點到其它結(jié)點的所有路徑（分支），就確定由根結(jié)點到其它結(jié)點的所有路徑（分支），就確定 了這個問題的狀態(tài)空間。了這個問題的狀態(tài)空間。解狀態(tài)解狀態(tài): :是這樣一些問題狀態(tài)是這樣一些問題狀態(tài)S，對于

20、這些問題狀態(tài)，由根到，對于這些問題狀態(tài)，由根到S 的那條路徑確定了這解空間中的一個元組。的那條路徑確定了這解空間中的一個元組。 答案狀態(tài)答案狀態(tài): :是這樣的一些解狀態(tài)是這樣的一些解狀態(tài)S，對于這些解狀態(tài)而言，由，對于這些解狀態(tài)而言，由 根到根到S的這條路徑確定了這問題的一個解的這條路徑確定了這問題的一個解狀態(tài)空間樹狀態(tài)空間樹: :解空間的樹結(jié)構(gòu)又稱隱式圖。解空間的樹結(jié)構(gòu)又稱隱式圖。 圖的搜索算法課件圖的搜索算法課件活結(jié)點活結(jié)點：如果已生成一個結(jié)點而它的所有兒子結(jié)點還沒有：如果已生成一個結(jié)點而它的所有兒子結(jié)點還沒有全部生成，則這個結(jié)點叫做活結(jié)點。全部生成，則這個結(jié)點叫做活結(jié)點。 E-結(jié)點結(jié)點：

21、當(dāng)前正在生成其兒子結(jié)點的活結(jié)點叫：當(dāng)前正在生成其兒子結(jié)點的活結(jié)點叫E-結(jié)點（正結(jié)點（正 擴展的結(jié)點）。擴展的結(jié)點）。死結(jié)點死結(jié)點 ：不再進一步擴展或者其兒子結(jié)點已全部生成的生：不再進一步擴展或者其兒子結(jié)點已全部生成的生成結(jié)點就是死結(jié)點成結(jié)點就是死結(jié)點 。圖的搜索算法課件圖的搜索算法課件521 算法框架 1算法的基本思路算法的基本思路 算法設(shè)計的基本步驟為算法設(shè)計的基本步驟為： 1）確定圖的存儲方式；確定圖的存儲方式； 2）圖的遍歷過程中的操作，其中包括為輸圖的遍歷過程中的操作，其中包括為輸出問題解而進行的存儲操作；出問題解而進行的存儲操作； 3 3）輸出問題的結(jié)論。輸出問題的結(jié)論。 上一頁 下

22、一頁 返回首頁圖的搜索算法課件圖的搜索算法課件2 2算法框架算法框架 上一頁上一頁 下一頁下一頁 返回首頁返回首頁 例例11 從從廣度優(yōu)先搜索定義可以看出活結(jié)點的擴展是按先來先處廣度優(yōu)先搜索定義可以看出活結(jié)點的擴展是按先來先處理的原則進行的，所以在算法中要用理的原則進行的，所以在算法中要用“隊隊”來存儲每個來存儲每個E-E-結(jié)點結(jié)點擴展出的活結(jié)點。為了算法的簡潔，抽象地定義：擴展出的活結(jié)點。為了算法的簡潔，抽象地定義：queuequeue為隊列類型，為隊列類型，InitQueue( ) InitQueue( ) 為隊列初始化函數(shù)，為隊列初始化函數(shù)， EnQueue(QEnQueue(Q，k)k

23、)為入隊函數(shù)，為入隊函數(shù)，QueueEmpty(Q) QueueEmpty(Q) 為判斷隊空函數(shù)，為判斷隊空函數(shù)，DeQueue(Q) DeQueue(Q) 為出隊函數(shù)。為出隊函數(shù)。 實際應(yīng)用中，用數(shù)組或鏈表實現(xiàn)隊列。實際應(yīng)用中，用數(shù)組或鏈表實現(xiàn)隊列。 開辟開辟數(shù)組數(shù)組visitedvisited記錄記錄visitedvisited結(jié)點的搜索情況。結(jié)點的搜索情況。 在算法框架中以輸出結(jié)點值表示在算法框架中以輸出結(jié)點值表示“訪問訪問”。圖的搜索算法課件圖的搜索算法課件1 1）鄰接表表示圖的廣度優(yōu)先搜索算法）鄰接表表示圖的廣度優(yōu)先搜索算法 int visitedn; /n visitedn; /n

24、 為結(jié)點個數(shù)為結(jié)點個數(shù)/ /bfs(int k,graph head) int i； queue Q ； edgenode *p； /定義隊列定義隊列/ InitQueue(Q)； /隊列初始化隊列初始化/ print(“visit vertex”，k)； / 訪問源點訪問源點vk/ visitedk=1； EnQueue(Q，k)； /vk已訪問，將其入隊。已訪問，將其入隊。/ while(!QueueEmpty(Q) /隊非空則執(zhí)行隊非空則執(zhí)行/ i=DeQueue(Q)； / vi出隊為出隊為E-結(jié)點結(jié)點/ p=headi.firstedge； /取取vi的邊表頭指針的邊表頭指針/ wh

25、ile(pnull) /擴展擴展E-結(jié)點結(jié)點 / if(visitedp-adjvex=0) /若若vj未訪問過未訪問過/ print (“visitvertex”，p-adjvex)；/訪問訪問vj/ visitedp-adjvex=1； EnQueue(Q，p-adjvex)； /訪問過的訪問過的vj人隊人隊/ p=p-next ； /找找vi的下一鄰接點的下一鄰接點/ 圖的搜索算法課件圖的搜索算法課件2）鄰接矩陣表示的圖的廣度優(yōu)先搜索算法）鄰接矩陣表示的圖的廣度優(yōu)先搜索算法上一頁上一頁 下一頁下一頁 返回返回首頁首頁bfsm(int k, graph g100，int n) int i，

26、j； CirQueue Q； InitQueue(Q)； print (visit vertex， k)； /訪問源點訪問源點vk/ visitedk=1； EnQueue(Q，k)； while(not QueueEmpty(Q) i=DeQueue(Q)； /vi出隊出隊/ for(j=0;jn;j+) /擴展結(jié)點擴展結(jié)點/ if(gij=1 and visitedj=0) print(visit vertex，j)； visitedj=1； EnQueue(Q，j)； /訪問過的訪問過的vj人隊人隊/ 圖的搜索算法課件圖的搜索算法課件522 廣度優(yōu)先搜索的應(yīng)用 【例1】已知若干個城市的地

27、圖，求從一個城市到另一個城市的路徑，要求路徑中經(jīng)過的城市最少 【例2】走迷宮問題 上一頁 下一頁 返回首頁圖的搜索算法課件圖的搜索算法課件【例1】已知若干個城市的地圖，求從一個城市到另一個城市的路徑，要求路徑中經(jīng)過的城市最少。 算法設(shè)計： 上一頁 下一頁 返回首頁 例2 例3 圖的廣度優(yōu)先搜索類似與樹的層次遍圖的廣度優(yōu)先搜索類似與樹的層次遍歷，逐層搜索正好可以盡快找到一個結(jié)點歷，逐層搜索正好可以盡快找到一個結(jié)點與另一個結(jié)點相對而言最直接的路徑。與另一個結(jié)點相對而言最直接的路徑。圖的搜索算法課件圖的搜索算法課件 如圖如圖5-6表示的是從城市表示的是從城市A到城市到城市H的交通的交通圖。從圖中可以

28、看出，從城市圖。從圖中可以看出，從城市A到城市到城市H要經(jīng)要經(jīng)過若干個城市。現(xiàn)要找出一條經(jīng)過城市最少過若干個城市。現(xiàn)要找出一條經(jīng)過城市最少一條路線。一條路線。 上一頁上一頁 下一頁下一頁 返回首頁返回首頁 例例2 2 例例33圖5-6 表5-1 圖5-6的鄰接距陣 圖的搜索算法課件圖的搜索算法課件具體過程如下： 1 1）將城市將城市A A（編號（編號1 1）入隊，隊首）入隊，隊首qhqh置置為為0 0、隊尾、隊尾qeqe置為置為1 1。2 2）將隊首所指的城市所有可直通的城將隊首所指的城市所有可直通的城市入隊市入隊( (如果這個城市在隊中出現(xiàn)過就不如果這個城市在隊中出現(xiàn)過就不入隊入隊),),然

29、后將隊首加然后將隊首加1 1，得到新的隊首城，得到新的隊首城市。重復(fù)以上步驟，直到城市市。重復(fù)以上步驟，直到城市H H入隊為止。入隊為止。當(dāng)搜到城市當(dāng)搜到城市H H時，搜索結(jié)束。時，搜索結(jié)束。 3）輸出最少城市線路輸出最少城市線路。 上一頁 下一頁 返回首頁 例2 例3圖的搜索算法課件圖的搜索算法課件數(shù)據(jù)結(jié)構(gòu)設(shè)計： 1 1）線性線性數(shù)組數(shù)組a作為活結(jié)點隊的存儲空間。作為活結(jié)點隊的存儲空間。2 2）隊列的每個結(jié)點有兩個成員：隊列的每個結(jié)點有兩個成員：ai.city記記錄入隊的城市，錄入隊的城市，ai.pre記錄該城市的前趨城記錄該城市的前趨城市在隊列中的下標(biāo)，這樣通過市在隊列中的下標(biāo)，這樣通過a

30、i.pre就可以就可以倒推出最短線路。倒推出最短線路。3 3）設(shè)置數(shù)組設(shè)置數(shù)組visited記錄已搜索過的城市。記錄已搜索過的城市。 上一頁 下一頁 返回首頁 例2 例3圖的搜索算法課件圖的搜索算法課件算法如下：search( )( )qh=0; qe=1;sq1.city=1;sq1.pre=0;visited1=1;qh=0; qe=1;sq1.city=1;sq1.pre=0;visited1=1; while( qhqe) / while( qhqe) /當(dāng)隊不空當(dāng)隊不空/ /qh=qh+1; /qh=qh+1; /結(jié)點出隊結(jié)點出隊/ / for(i=1;i=n,i+) /for(i=

31、1;i=n,i+) /擴展結(jié)點擴展結(jié)點/ / if if （jzsqqh.cityi=1 and visitedi=0jzsqqh.cityi=1 and visitedi=0） qe=qe+1; / qe=qe+1; /結(jié)點入隊結(jié)點入隊/ /sqqe.city=i;sqqe.pre=qh;visitedqe=1;sqqe.city=i;sqqe.pre=qh;visitedqe=1;if (sqqe.city=8) out( );if (sqqe.city=8) out( ); print(“No avaliable way.”);print(“No avaliable way.”); 上一

32、頁 下一頁 返回首頁 例2 例3圖的搜索算法課件圖的搜索算法課件算法分析算法分析：時間復(fù)雜度是：時間復(fù)雜度是O（n）；空間復(fù)雜性為）；空間復(fù)雜性為（n2），包括圖本身的存儲空間和搜索時輔助空間），包括圖本身的存儲空間和搜索時輔助空間“隊隊”的存儲空間。的存儲空間。out( ); /out( ); /輸出路徑輸出路徑/ /print(sqqe.city);print(sqqe.city); while(sqqe.pre0)while(sqqe.pre0) qe=sqqe.pre; print(-,sqqe.city); 圖的搜索算法課件圖的搜索算法課件【例2】走迷宮問題 上一頁 下一頁 返回首頁

33、 例1 例3 迷宮是許多小方格構(gòu)成的矩形，在每個小方格中有的是墻（圖中的迷宮是許多小方格構(gòu)成的矩形，在每個小方格中有的是墻（圖中的“1”1”）有的是路（圖中的）有的是路（圖中的“0”0”）。走迷宮就是從一個小方格沿上、下、左、）。走迷宮就是從一個小方格沿上、下、左、右四個方向到鄰近的方格，當(dāng)然不能穿墻。設(shè)迷宮的入口是在左上角右四個方向到鄰近的方格，當(dāng)然不能穿墻。設(shè)迷宮的入口是在左上角(1,1)(1,1)，出口是右下角出口是右下角(8,8)(8,8)。根據(jù)給定的迷宮，找出一條從入口到出口的路徑。根據(jù)給定的迷宮，找出一條從入口到出口的路徑。 圖的搜索算法課件圖的搜索算法課件算法設(shè)計： 上一頁 下一

34、頁 返回首頁 例1 例3 從入口開始廣度優(yōu)先搜索可到達(dá)的方格入隊，再擴展從入口開始廣度優(yōu)先搜索可到達(dá)的方格入隊，再擴展 隊首的方格，直到搜索到出口時算法結(jié)束。隊首的方格，直到搜索到出口時算法結(jié)束。 對于迷宮中任意一點對于迷宮中任意一點A（Y，X），有四個搜索方向：），有四個搜索方向： 向上向上A（Y-1，X） 向下向下A（Y+1，X） 向左向左A（Y，X-1） 向右向右A（Y，X+1） 當(dāng)對應(yīng)方格可行（值為當(dāng)對應(yīng)方格可行（值為0），就擴展為活結(jié)點。），就擴展為活結(jié)點。 圖的搜索算法課件圖的搜索算法課件數(shù)據(jù)結(jié)構(gòu)設(shè)計：數(shù)據(jù)結(jié)構(gòu)設(shè)計： 上一頁 下一頁 返回首頁 例1 例3 用用數(shù)組數(shù)組做隊的存儲空間

35、，隊中結(jié)點有三個做隊的存儲空間，隊中結(jié)點有三個成員：行號、列號、前一個方格在隊列中的成員：行號、列號、前一個方格在隊列中的下標(biāo)。搜索過的方格不另外開辟空間記錄其下標(biāo)。搜索過的方格不另外開辟空間記錄其訪問的情況，而是用迷宮原有的存儲空間置訪問的情況，而是用迷宮原有的存儲空間置元素值為元素值為“-1”-1”時，標(biāo)識已經(jīng)訪問過該方格。時，標(biāo)識已經(jīng)訪問過該方格。 為了構(gòu)造循環(huán)體，用數(shù)組為了構(gòu)造循環(huán)體，用數(shù)組fx=1,-1,0,0fx=1,-1,0,0、fy= 0,0,-1,1 fy= 0,0,-1,1 模擬上下左右搜索時的下標(biāo)模擬上下左右搜索時的下標(biāo)的變化過程。的變化過程。 圖的搜索算法課件圖的搜索算

36、法課件int jz88= 1,0,0,0,1,0,1,1,0,1,1,1,1,0,1,1, 0,1,1,0,0,1,1,1, 0,1,0,1,1,1,0,1, 1,1,0,1,1,1,0,0,0,0,1,1,1,1,1,0, 1,1,1,0,0,1,1,0, 1,1,1,1,0,0,0,1;struct intcity, pre; sq100;int qh,qe,i,visited100;main( )int i,n=8;for(i=1;i=n,i=i+1) visitedi=0;search( );圖的搜索算法課件圖的搜索算法課件search( )qh=0; qe=1;sq1.city=1;

37、sq1.pre=0; visited1=1;while( qhqe) /當(dāng)隊不空當(dāng)隊不空/qh=qh+1; /結(jié)點出隊結(jié)點出隊/ for(i=1;i=n,i=i+1) /擴展結(jié)點擴展結(jié)點/if （jzsqqh.cityi=1 and visitedi=0） qe=qe+1; /結(jié)點入隊結(jié)點入隊/ sqqe.city=i;sqqe.pre=qh;visitedqe=1;if (sqqe.city=8) out( ); print(“No avaliable way.”);圖的搜索算法課件圖的搜索算法課件out( ); /輸出路徑輸出路徑/print(sqqe.city);while(sqqe.p

38、re0) qe=sqqe.pre; print(-,sqqe.city); 算法分析算法分析： 算法算法的時間復(fù)雜度并不復(fù)雜是的時間復(fù)雜度并不復(fù)雜是O O（n n），算法的空間復(fù)雜性），算法的空間復(fù)雜性為為O O（n n2 2），包括圖本身的存儲空間和搜索時輔助空間），包括圖本身的存儲空間和搜索時輔助空間“隊隊”的的存儲空間。存儲空間。 上一頁 下一頁 返回首頁 例1 例3圖的搜索算法課件圖的搜索算法課件 深度優(yōu)先遍歷深度優(yōu)先遍歷首先訪問出發(fā)點首先訪問出發(fā)點v v，并將其標(biāo)記為，并將其標(biāo)記為已訪問過；然后依次從已訪問過；然后依次從v v出發(fā)搜索出發(fā)搜索v v的每個鄰接點的每個鄰接點w w。若若

39、w w未曾訪問過，則以未曾訪問過，則以w w為新的出發(fā)點繼續(xù)進行深度為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷，直至圖中所有和源點優(yōu)先遍歷，直至圖中所有和源點v v有路徑相通的頂點有路徑相通的頂點均已被訪問為止。均已被訪問為止。 若此時圖中仍有未訪問的頂點，則另選一個尚若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復(fù)上述過程，直至圖未訪問的頂點作為新的源點重復(fù)上述過程，直至圖中所有頂點均已被訪問為止。中所有頂點均已被訪問為止。5.3 深度優(yōu)先搜索深度優(yōu)先搜索圖的搜索算法課件圖的搜索算法課件 深度搜索與廣度搜索的相近，最終都要深度搜索與廣度搜索的相近，最終都要擴展一個結(jié)點的所有子結(jié)點擴

40、展一個結(jié)點的所有子結(jié)點. . 區(qū)別在于對擴展結(jié)點過程，深度搜索擴區(qū)別在于對擴展結(jié)點過程，深度搜索擴展的是展的是E-E-結(jié)點的鄰接結(jié)點中的一個，并將其結(jié)點的鄰接結(jié)點中的一個，并將其作為新的作為新的E-E-結(jié)點繼續(xù)擴展，當(dāng)前結(jié)點繼續(xù)擴展，當(dāng)前E-E-結(jié)點仍為結(jié)點仍為活結(jié)點，待搜索完其子結(jié)點后，回溯到該結(jié)活結(jié)點，待搜索完其子結(jié)點后，回溯到該結(jié)點擴展它的其它未搜索的鄰接結(jié)點。而廣度點擴展它的其它未搜索的鄰接結(jié)點。而廣度搜索，則是擴展搜索，則是擴展E-E-結(jié)點的所有鄰接結(jié)點，結(jié)點的所有鄰接結(jié)點，E-E-結(jié)點就成為一個死結(jié)點。結(jié)點就成為一個死結(jié)點。圖的搜索算法課件圖的搜索算法課件 5 53 31 1 算法

41、框架算法框架 1算法的基本思路算法的基本思路 2算法框架算法框架圖的搜索算法課件圖的搜索算法課件1 1算法的基本思路算法的基本思路 算法設(shè)計的基本步驟為：算法設(shè)計的基本步驟為： 1 1）確定圖的存儲方式；）確定圖的存儲方式； 2 2）遍歷過程中的操作，其中包括為輸出）遍歷過程中的操作，其中包括為輸出問題解而進行的存儲操作；問題解而進行的存儲操作； 3 3）輸出問題的結(jié)論。）輸出問題的結(jié)論。 4 4）一般在回溯前的應(yīng)該將結(jié)點狀態(tài)恢復(fù)）一般在回溯前的應(yīng)該將結(jié)點狀態(tài)恢復(fù)為原始狀態(tài)，特別是在有多解需求的問題中。為原始狀態(tài)，特別是在有多解需求的問題中。圖的搜索算法課件圖的搜索算法課件2算法框架算法框架

42、1）用鄰接表存儲圖的搜索算法）用鄰接表存儲圖的搜索算法 2）用鄰接矩陣存儲圖的搜索算法）用鄰接矩陣存儲圖的搜索算法圖的搜索算法課件圖的搜索算法課件graph head100graph head100；dfs(int k) / headdfs(int k) / head圖的頂點數(shù)組圖的頂點數(shù)組/ / edgenode edgenode * *ptr / ptrptr / ptr圖的邊表指針圖的邊表指針/ / visitedk=1; / visitedk=1; /* * 記錄已遍歷過記錄已遍歷過 * */ / print(“ print(“訪問訪問 ”,k); /,k); /* * 印出遍歷頂點值

43、印出遍歷頂點值 * */ / ptr=headk.firstedge; / ptr=headk.firstedge; /* * 頂點的第一個鄰接點頂點的第一個鄰接點 * */ / while ( ptr NULL ) / while ( ptr NULL ) /* * 遍歷至鏈表尾遍歷至鏈表尾 * */ / if ( visitedptr-vertex=0) / if ( visitedptr-vertex=0) /* * 如過沒遍歷過如過沒遍歷過 * */ / dfs(ptr-vertex); / dfs(ptr-vertex); /* * 遞歸遍歷遞歸遍歷 * */ / ptr = ptr

44、-nextnode; / ptr = ptr-nextnode; /* * 下一個頂點下一個頂點 * */ / 算法分析：n n圖中有圖中有 n n 個頂點，個頂點，e e 條邊。掃描邊的時間為條邊。掃描邊的時間為O(e)O(e)。遍歷圖的時間復(fù)雜性為遍歷圖的時間復(fù)雜性為O(n+e)O(n+e)。 返回返回 圖的搜索算法課件圖的搜索算法課件graph g100100,int ngraph g100100,int n；dfsm(int k)dfsm(int k) int j int j； print(“ print(“訪問訪問 ”,k);,k); visitedk=1 visitedk=1； f

45、or(j=1 for(j=1；j=nj=n；j+) /j+) /依次搜索依次搜索vkvk的鄰接點的鄰接點 if(gkj=1 and visitedj=0) if(gkj=1 and visitedj=0) dfsm(g,j) dfsm(g,j) /(vk /(vk，vj)Evj)E，且，且vjvj未訪問過，故未訪問過，故vjvj為新出發(fā)點為新出發(fā)點 算法分析：查找每一個頂點的所有的邊，所需時間為查找每一個頂點的所有的邊，所需時間為O(n)O(n)，遍，遍歷圖中所有的頂點所需的時間為歷圖中所有的頂點所需的時間為O(n2)O(n2)。 返回返回圖的搜索算法課件圖的搜索算法課件5 53 32 2 深

46、度優(yōu)先搜索的應(yīng)用深度優(yōu)先搜索的應(yīng)用【例【例1】走迷宮問題：問題同】走迷宮問題：問題同522【例【例2】1、算法設(shè)計：深度優(yōu)先搜索，就是一直向深度優(yōu)先搜索，就是一直向著可通行的下一個方格行進，直到搜索到出著可通行的下一個方格行進，直到搜索到出口就找到一個解。若行不通時，則返回上一口就找到一個解。若行不通時，則返回上一個方格，繼續(xù)搜索其它方向。個方格，繼續(xù)搜索其它方向。圖的搜索算法課件圖的搜索算法課件2、數(shù)據(jù)結(jié)構(gòu)設(shè)計：我們還是用迷宮本身的存儲我們還是用迷宮本身的存儲空間除了記錄走過的信息，還要標(biāo)識是否可行：空間除了記錄走過的信息，還要標(biāo)識是否可行： mazeij=3 mazeij=3 標(biāo)識走過的方

47、格標(biāo)識走過的方格 ； mazeij=2 mazeij=2 標(biāo)識走入死胡同的方格，標(biāo)識走入死胡同的方格，這樣，最后存儲為這樣，最后存儲為“3”3”的方格為可行的方格。的方格為可行的方格。而當(dāng)一個方格四個方向都搜索完還沒有走到出口，而當(dāng)一個方格四個方向都搜索完還沒有走到出口，說明該方格或無路可走或只能走入了說明該方格或無路可走或只能走入了“死胡同死胡同”。圖的搜索算法課件圖的搜索算法課件3、算法int maze88=0,0,0,0,0,0,0,0,int maze88=0,0,0,0,0,0,0,0, 0,11,1,1,0,1,0,0,0,0,0,1,0,1,0, 0,11,1,1,0,1,0,0

48、,0,0,0,1,0,1,0, 0,1,0,0,0,0,1,0,0,1,0,1,1,0,1,0, 0,1,0,0,0,0,1,0,0,1,0,1,1,0,1,0, 0,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0, 0,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0, 0,1,1,1,1,1,1,0;fx4=1,-1,0,0, 0,1,1,1,1,1,1,0;fx4=1,-1,0,0, fy4=0,0,-1,1; int i,j,k,total; fy4=0,0,-1,1; int i,j,k,total;main( )main( ) int total=0; int

49、 total=0; maze11=3; / maze11=3; /入口坐標(biāo)設(shè)置已走標(biāo)志入口坐標(biāo)設(shè)置已走標(biāo)志/ / search(1,1);search(1,1); print(“Total is”,total); / print(“Total is”,total); /統(tǒng)計總步數(shù)統(tǒng)計總步數(shù)/ / 圖的搜索算法課件圖的搜索算法課件search(int i, int j)search(int i, int j)int k,newi,newj;int k,newi,newj; for(k=1;k=4;k+) / for(k=1;k=4;k+) /搜索可達(dá)的方格搜索可達(dá)的方格/ / if( if(ch

50、eck(i,j,k)check(i,j,k)=1)=1) newi=i+fxk; newj=j+fyk; newi=i+fxk; newj=j+fyk; mazenewinewj=3; / mazenewinewj=3; /來到新位置后來到新位置后, ,設(shè)置已走過標(biāo)志設(shè)置已走過標(biāo)志/ / if (newi=8 and newj=8) / if (newi=8 and newj=8) /到出口則輸出到出口則輸出, ,否則下一步遞歸否則下一步遞歸/ / Out( );Out( ); else search(newi,newj); else search(newi,newj); mazeij=2;

51、/ mazeij=2; /某一方格只能走入死胡同某一方格只能走入死胡同/ / 圖的搜索算法課件圖的搜索算法課件 Out( )Out( ) int i,j; int i,j; for( i=1;i=8;i+) for( i=1;i=8;i+) print(“ print(“換行符換行符”);); for(j=1;j=8;j+) for(j=1;j=8;j+) if if（mazeij=3mazeij=3） print(“V”);print(“V”); total+; / total+; /統(tǒng)計總步數(shù)統(tǒng)計總步數(shù)/ / else else print(“ print(“* *”);”); 圖的搜索算

52、法課件圖的搜索算法課件check(int i,int j,int k)check(int i,int j,int k)int flag=1;int flag=1; i= i+fxk; j= j +fyk; i= i+fxk; j= j +fyk; if(i8 or j8) / if(i8 or j8) /是否在迷宮內(nèi)是否在迷宮內(nèi)/ / flag=0; flag=0; else else if(mazeij0) / if(mazeij0) /是否可行是否可行/ / flag=0; flag=0; return(flag); return(flag); 圖的搜索算法課件圖的搜索算法課件 4、算法說

53、明： 1）和廣度優(yōu)先算法一樣每個方格有四個方）和廣度優(yōu)先算法一樣每個方格有四個方向可以進行搜索，這樣一點結(jié)點（方格）向可以進行搜索，這樣一點結(jié)點（方格）就可多次成為就可多次成為“活結(jié)點活結(jié)點”，而在廣度優(yōu)先，而在廣度優(yōu)先算法一點結(jié)點（方格）就可一次成為算法一點結(jié)點（方格）就可一次成為“活活結(jié)點結(jié)點”，一出隊就成了死結(jié)點。，一出隊就成了死結(jié)點。 2）用廣度優(yōu)先算法，搜索出的是一條最短）用廣度優(yōu)先算法，搜索出的是一條最短的路徑，而用深度優(yōu)先搜索則只能找出一的路徑，而用深度優(yōu)先搜索則只能找出一條可行的路徑，而不能保證是最短的路徑。條可行的路徑，而不能保證是最短的路徑。 3）在空間效率上二者相近。都需

54、要輔助空）在空間效率上二者相近。都需要輔助空間。間。 圖的搜索算法課件圖的搜索算法課件【例【例2】有如圖有如圖1所示的七巧板，試編寫一所示的七巧板，試編寫一源程序如下，使用至多四種不同顏色對七巧源程序如下，使用至多四種不同顏色對七巧板進行涂色板進行涂色(每塊涂一種顏色每塊涂一種顏色)，要求相鄰區(qū)域，要求相鄰區(qū)域的顏色互不相同，打印輸出所有可能的涂色的顏色互不相同，打印輸出所有可能的涂色方案。方案。 圖的搜索算法課件圖的搜索算法課件1、問題分析:為了讓算法為了讓算法能識別不同區(qū)域間的相鄰關(guān)能識別不同區(qū)域間的相鄰關(guān) 系，我們把七巧板上每一個系，我們把七巧板上每一個區(qū)域看成一個頂點若兩個區(qū)區(qū)域看成一

55、個頂點若兩個區(qū)域相鄰，則相應(yīng)的頂點間用域相鄰，則相應(yīng)的頂點間用一條邊相連，這樣該問題就一條邊相連，這樣該問題就轉(zhuǎn)化為圖一個圖的搜索問題轉(zhuǎn)化為圖一個圖的搜索問題了。了。圖的搜索算法課件圖的搜索算法課件2、算法設(shè)計: 按順序分別對號、號、按順序分別對號、號、.、號區(qū)域、號區(qū)域進行試探性涂色，用、號代表種顏進行試探性涂色，用、號代表種顏色。色。 則涂色過程如下：則涂色過程如下： 1 1）對某一區(qū)域涂上與其相鄰區(qū)域不同的顏色。）對某一區(qū)域涂上與其相鄰區(qū)域不同的顏色。 2 2）若使用種顏色進行涂色均不能滿足要求，）若使用種顏色進行涂色均不能滿足要求，則回溯一步，更改前一區(qū)域的顏色。則回溯一步，更改前一區(qū)

56、域的顏色。 3 3）轉(zhuǎn)步驟繼續(xù)涂色，直到全部區(qū)域全部涂）轉(zhuǎn)步驟繼續(xù)涂色，直到全部區(qū)域全部涂色為止，輸出結(jié)果。色為止，輸出結(jié)果。 已經(jīng)有研究證明，對任意的平面圖至少存在一已經(jīng)有研究證明，對任意的平面圖至少存在一種四色涂色法。種四色涂色法。圖的搜索算法課件圖的搜索算法課件3、數(shù)據(jù)采用的存儲結(jié)構(gòu)：鄰接矩陣存儲鄰接矩陣存儲 0 1 0 0 1 0 10 1 0 0 1 0 1 1 0 0 1 0 1 01 0 0 1 0 1 0 0 0 0 0 0 1 10 0 0 0 0 1 1 0 1 0 0 0 1 10 1 0 0 0 1 1 1 0 0 0 0 0 11 0 0 0 0 0 1 0 1 1

57、1 0 0 00 1 1 1 0 0 0 1 0 1 1 1 0 01 0 1 1 1 0 0圖的搜索算法課件圖的搜索算法課件4、算法如下:int data77,n,color7,total;int data77,n,color7,total;main( )main( ) int i,j; int i,j; for(i=1;i=n;i+) for(i=1;i=n;i+) for(j=1;j=n;j+) for(j=1;j=n;j+) input(dataij); input(dataij); for(j=1;j=n;j+) for(j=1;j7) if (s7) output( );outpu

58、t( ); else else for(i=1;i=4;i+) for(i=1;i=4;i+) colors=i; colors=i; if if （colorsame(s)colorsame(s)=0=0） try(s+1);try(s+1); 圖的搜索算法課件圖的搜索算法課件 output( )output( ) int i,; int i,; print( print(換行符，換行符，serial numberserial number：,total);,total); for i:=1 to n do for i:=1 to n do print(colori); print(colo

59、ri); total=total+1; total=total+1; 圖的搜索算法課件圖的搜索算法課件colorsame(int s)colorsame(int s) / /判斷相鄰點是否同色判斷相鄰點是否同色/ / int i,flag; int i,flag; flag=0; flag=0; for(i=1;i=s-1;i+) for(i=1;iDFN(3)=3L(10)=4DFN(3)=3。同理，結(jié)點。同理，結(jié)點2 2、5 5也是關(guān)結(jié)點。也是關(guān)結(jié)點。圖的搜索算法課件圖的搜索算法課件 按后根次序訪問深度優(yōu)先生成樹的結(jié)點，按后根次序訪問深度優(yōu)先生成樹的結(jié)點，可以很容易地算出可以很容易地算出L

60、 L（U U）。于是，為了確定）。于是，為了確定圖圖G G的關(guān)結(jié)點的關(guān)結(jié)點, ,必須既完成對必須既完成對G G的深度優(yōu)先檢索，的深度優(yōu)先檢索，產(chǎn)生產(chǎn)生G G的深度優(yōu)先生成樹的深度優(yōu)先生成樹T T，又要按后根次序，又要按后根次序訪問樹訪問樹T T的結(jié)點。的結(jié)點。圖的搜索算法課件圖的搜索算法課件算法ART計算DFN和L的算法如下： int DFNnint DFNn，LnLn，numnum，n n ART ART（u u，v v） /u/u是深度優(yōu)先檢索的開是深度優(yōu)先檢索的開始結(jié)點。在深度優(yōu)先生成樹中，始結(jié)點。在深度優(yōu)先生成樹中， u u若有父親，那末若有父親，那末v v就是它的父親。假設(shè)就是它的父