實驗四 圖的遍歷算法.doc

實驗四 圖的遍歷算法4.1.實驗的問題與要求1.如何對給定圖的每個頂點各做一次且僅做一次訪問？有哪些方法可以實現(xiàn)圖的遍歷？2.如何用這些算法解決實際問題？3.熟練掌握圖的基本存儲方法4.熟練掌握圖的兩種搜索路徑的遍歷方法5.掌握有關(guān)圖的操作算法并用高級語言實現(xiàn)4.2.實驗的基本思想和基本原理和樹的遍歷類似，圖的遍歷也是從某個頂點出發(fā)，沿著某條搜索路徑對圖中每個頂點各做一次且僅做一次訪問。它是許多圖的算法的基礎(chǔ)。遍歷常用兩種方法：深度優(yōu)先搜索遍歷；廣度優(yōu)先搜索遍歷 4.2.1 深度優(yōu)先搜索（Depth-First Traversal）深度優(yōu)先搜索是一種遞歸的過程，正如算法名稱那樣，深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的頂點，如果它還有以此為起點而未探測到的邊，就沿此邊繼續(xù)下去。當(dāng)結(jié)點v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點v有那條邊的始結(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源結(jié)點可達的所有結(jié)點為止。如果還存在未被發(fā)現(xiàn)的結(jié)點，則選擇其中一個作為源結(jié)點并重復(fù)以上過程，整個進程反復(fù)進行直到所有結(jié)點都被發(fā)現(xiàn)為止。1.圖的深度優(yōu)先遍歷的遞歸定義 假設(shè)給定圖G的初態(tài)是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發(fā)點(源點)，則深度優(yōu)先遍歷可定義如下：首先訪問出發(fā)點v，并將其標(biāo)記為已訪問過；然后依次從v出發(fā)搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復(fù)上述過程，直至圖中所有頂點均已被訪問為止。 圖的深度優(yōu)先遍歷類似于樹的前序遍歷。采用的搜索方法的特點是盡可能先對縱深方向進行搜索。這種搜索方法稱為深度優(yōu)先搜索(Depth-First Search)。相應(yīng)地，用此方法遍歷圖就很自然地稱之為圖的深度優(yōu)先遍歷。2.深度優(yōu)先搜索的過程 設(shè)x是當(dāng)前被訪問頂點，在對x做過訪問標(biāo)記后，選擇一條從x出發(fā)的未檢測過的邊(x，y)。若發(fā)現(xiàn)頂點y已訪問過，則重新選擇另一條從x出發(fā)的未檢測過的邊，否則沿邊(x，y)到達未曾訪問過的y，對y訪問并將其標(biāo)記為已訪問過；然后從y開始搜索，直到搜索完從y出發(fā)的所有路徑，即訪問完所有從y出發(fā)可達的頂點之后，才回溯到頂點x，并且再選擇一條從x出發(fā)的未檢測過的邊。上述過程直至從x出發(fā)的所有邊都已檢測過為止。此時，若x不是源點，則回溯到在x之前被訪問過的頂點；否則圖中所有和源點有路徑相通的頂點(即從源點可達的所有頂點)都已被訪問過，若圖G是連通圖，則遍歷過程結(jié)束，否則繼續(xù)選擇一個尚未被訪問的頂點作為新源點，進行新的搜索過程。算法思路 :(1)、首先訪問一個頂點vi(初始點),將其標(biāo)記為已訪問過(因為圖的每個頂點可能有多個前驅(qū)和后繼，所以當(dāng)一個頂點被訪問以后，必須記錄它已經(jīng)被訪問，以避免再次被訪問，為此設(shè)置一個輔助數(shù)組visitedn, 它的每個元素的初值均為邏輯值假（false），即為常量0，表明尚未被訪問，一旦訪問了頂點vi，就將對應(yīng)元素visitedi設(shè)置為邏輯值真，即為常量1，表明vi已被訪問)。(2)、然后從vi的任一未被訪問過的鄰接點出發(fā)進行深度優(yōu)先搜索遍歷，當(dāng)vi所有鄰接點均被訪問過，則退回到上一個頂點vk,從vk的另一個未被訪問過的鄰接點出發(fā)進行深度優(yōu)先搜索遍歷，直到退回到初始點并且沒有未被訪問過的鄰接點為止。遍歷過程 (1)訪問vo, 記錄visited0=True, 從v0的一個未被訪問過的鄰接點v1出發(fā)遍歷； (2)訪問v1, visited1=True,從v1的一個未被訪問過的鄰接點v4出發(fā)遍歷； (3)訪問v4, visited4=True,從v4的一個未被訪問過的鄰接點v5出發(fā)遍歷； (4)訪問v5, visited5=True,由于v5的兩個鄰接點v1和v4都被訪問過，退回上一鄰接點v4，又v4的兩個鄰接點v1和v5都被訪問過，再退回上一鄰接點v1,從未被訪問過鄰接點V6出發(fā)遍歷； (5)訪問v6, visited6=True,從v6的一個未被訪問過的鄰接點v2出發(fā)遍歷； (6)訪問v2, visited2=True,v2所有鄰接點都訪問過，退回上一頂點v6,同理，v6退回v1,v1退回v0,再從v0未被訪問過鄰接點v3出發(fā)遍歷；(7)訪問v3, visited3=True，退回v0,因所有鄰接點都訪問過，再退回，結(jié)束。3.鄰接表表示的深度優(yōu)先搜索非遞歸算法（參考代碼）:#define MAXVEX 100void dfs(adjlist g，int v,int n) /*從頂點v出發(fā)進行深度優(yōu)先遍歷*/ struct vexnode *stackMAXVEX, *p; int visitedMAXVEX,top=0; for(i=1;i0|p!=NULL) while(p!=NULL) if (visitedp-adjvex=1) p=p-next; else printf(“%d”,p-adjvex); visitedp-adjvex=1; top+; stacktop=p; p=gp-adjvex.link; if(top0) top-; /*退棧，回溯查找已被訪問結(jié)點的未被訪問過的鄰接點 */ p=stacktop; p =p-next; 4.DFS時間復(fù)雜性一個有n個頂點、e條邊的圖，在深度優(yōu)先搜索圖的過程中，找鄰接點所需時間為O(e)。對輔助數(shù)組初始化時間為O(n)。因此，當(dāng)用鄰接表作為圖的存儲結(jié)構(gòu)時，深度優(yōu)先搜索圖的時間復(fù)雜性為O(e+n)。4.2.2圖的廣度優(yōu)先搜索（Breadth-first Traversal）廣度優(yōu)先搜索算法（又稱寬度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。1.廣度優(yōu)先搜索的基本思想首先訪問圖中某指定的起始點Vi并將其標(biāo)記為已訪問過，然后由Vi出發(fā)訪問與它相鄰接的所有頂點Vj、 Vk，并均標(biāo)記為已訪問過，然后再按照Vj、Vk的次序，訪問每一個頂點的所有未被訪問過的鄰接頂點，并均標(biāo)記為已訪問過，下一步再從這些頂點出發(fā)訪問與它們相鄰接的尚未被訪問的頂點，如此做下去，直到所有的頂點均被訪問過為止在廣度優(yōu)先搜索中，若對頂點V1的訪問先于頂點V2的訪問，則對V1鄰接頂點的訪問也先于V2鄰接頂點的訪問。就是說廣度優(yōu)先搜索中對鄰接點的尋找具有“先進先出”的特性。因此，為了保證訪問頂點的這種先后關(guān)系，需借助一個隊列暫存那些剛訪問過的頂點。設(shè)此隊列由一個一維數(shù)組構(gòu)成，數(shù)組名為Queue，隊首指針和隊尾指針分別為front和rear。假設(shè)數(shù)組足夠大，不必考慮有溢出的可能性。廣度優(yōu)先搜索不是遞歸過程，不能用遞歸形式。2.遍歷過程 (1)訪問v0,visited0=True (2)訪問v0所有未訪問過鄰接v1和v2, visited1=True, visited2=True;(3)訪問v1所有未被訪問過的鄰接點v3和v4,v5,并將它們標(biāo)記已訪問過；(4)訪問v2所有未被訪問過的鄰接點v6, visited6=True；(5)訪問v3所有未被訪問過的鄰接點v7, visited7=True；(6)訪問v4所有未被訪問過的鄰接點(無)(7)訪問v5所有未被訪問過的鄰接點v8, visited8=True；(8)訪問v6所有未被訪問過的鄰接點(無)；(9)依次訪問v7，v8所有未被訪問過的鄰接點(無)，結(jié)束。3.BFS時間復(fù)雜度一個有n個頂點、e條邊的圖，在廣度優(yōu)先搜索圖的過程中，每個頂點至多進一次隊列，圖的搜索過程實質(zhì)上是通過邊來找頂點的過程，找鄰接點所需時間為O(e)。對輔助數(shù)組初始化時間為O(n)。因此，當(dāng)用鄰接表作為圖的存儲結(jié)構(gòu)時，廣度優(yōu)先搜索圖時間復(fù)雜度的c為O(e+n)。 4.3.實驗內(nèi)容與實現(xiàn)提示1.寫一個圖形的鄰接矩陣表示的深度優(yōu)先搜索程序。（遞歸算法）算法提示：（參考代碼） void DFSM(MGraph *G，int i) /以vi為出發(fā)點對鄰接矩陣表示的圖G進行DFS搜索，設(shè)鄰接矩陣是0,l矩陣 int j； printf(visit vertex：c，G-vexsi)；/訪問頂點vi visitedi=TRUE； for(j=0；jn；j+) /依次搜索vi的鄰接點 if(G-edgesij=1&!visitedj) DFSM(G，j)/(vi，vj)E，且vj未訪問過，故vj為新出發(fā)點 /DFSM注意： 遍歷操作不會修改圖G的內(nèi)容，故上述算法中可將G定義為ALGraph或MGraph類型的參數(shù)，而不一定要定義為ALGraph和MGraph的指針類型。但基于效率上的考慮，選擇指針類型的參數(shù)為宜。2.寫一個鄰接表表示的深度優(yōu)先搜索算法算法提示：（參考代碼）void DFS(ALGraph *G，int i) /以vi為出發(fā)點對鄰接表表示的圖G進行深度優(yōu)先搜索 EdgeNode *p； printf(visit vertex：c，G-adjlisti.vertex)；/訪問頂點vi visitedi=TRUE； /標(biāo)記vi已訪問 p=G-adjlisti.firstedge； /取vi邊表的頭指針 while(p)/依次搜索vi的鄰接點vj，這里j=p-adjvex if (!visitedp-adjvex)/若vi尚未被訪問 DFS(G，p-adjvex);/則以Vj為出發(fā)點向縱深搜索 p=p-next； /找vi的下一鄰接點 /DFS3.寫一個圖的鄰接表表示的廣度優(yōu)先搜索算法(非遞歸算法)。4.寫一個鄰接矩陣表示的圖的廣度優(yōu)先搜索算法（非遞歸算法）算法提示：（參考代碼） void BFSM(MGraph *G，int k) 以vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索 int i，j； CirQueue Q； InitQueue(&Q)； printf(visit vertex：c，G-vexsk)； /訪問源點vk visitedk=TRUE； EnQueue(&Q，k)； while(!QueueEmpty(&Q) i=DeQueue(&Q)； /vi出隊 for(j=0;jn;j+)/依次搜索vi的鄰接點vj if(G-edgesij=1&!visitedj)/vi未訪問 printf(visit vertex：c，G-vexsj)；/訪問vi visitedj=TRUE； EnQueue(&Q，j)；/訪問過的vi人隊 /endwhile /BFSM5.應(yīng)用題如下圖：圖中共有9個頂點，14條邊為：98，95，81，75，65，63，60，51，43，42，30，21，20，10分別用深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷此圖。實現(xiàn)提示：根據(jù)題給信息，程序中建立的數(shù)據(jù)為：edges=98817565636051434230212010;createAMLGraph(G,10,13,edges); 深度遍歷可以利用遞歸算法。(1).深度優(yōu)先遍歷的遞歸算法(參考代碼)：void DFS(ALGraph *G，int i) /以vi為出發(fā)點對鄰接表表示的圖G進行深度優(yōu)先搜索 EdgeNode *p； printf(visit vertex：c，G-adjlisti.vertex)；/訪問頂點vi visitedi=TRUE； /標(biāo)記vi已訪問 p=G-adjlisti.firstedge； /取vi邊表的頭指針 while(p)/依次搜索vi的鄰接點vj，這里j=p-adjvex if (!visitedp-adjvex)/若vi尚未被訪問 DFS(G，p-adjvex);/則以Vj為出發(fā)點向縱深搜索 p=p-next； /找vi的下一鄰接點 /DFS(2).鄰接表表示圖的廣度優(yōu)先搜索算法（參考代碼） void BFS(ALGraph*G，int k) / 以vk為源點對用鄰接表表示的圖G進行廣度優(yōu)先搜索 int i； CirQueue Q； /須將隊列定義中DataType改為int EdgeNode *p； InitQueue(&Q)；/隊列初始化 /訪問源點vk printf(visit vertex：e，G-adjlistk.vertex)； visitedk=TRUE； EnQueue(&Q，k)；/vk已訪問，將其人隊。（實際上是將其序號人隊） while(!QueueEmpty(&Q)/隊非空則執(zhí)行 i=DeQueue(&Q)； /相