實(shí)驗(yàn)四 圖的遍歷算法.doc

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