圖的遍歷和連通性課件

7.3圖的遍歷遍歷：從已給的連通圖中某一頂點出發(fā)，沿著一些邊，訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。遍歷實質(zhì)：找每個頂點的鄰接點的過程。圖的特點：圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。解決思路：可設置一個輔助數(shù)組

visited[n]，用來標記每個被訪問過的頂點。它的初始狀態(tài)為false，在圖的遍歷過程中，一旦某一個頂點i

被訪問，就立即改visited[i]為true，防止它被重復訪問。怎樣避免重復訪問？17.3圖的遍歷遍歷：從已給的連通圖中某一頂點出發(fā)，沿著一深度優(yōu)先搜索和廣度優(yōu)先搜索圖常用的遍歷：一、深度優(yōu)先搜索(DFS)Depth_FirstSearch基本思想：——類似于樹的先根遍歷過程。1、連通圖的深度優(yōu)先搜索遍歷步驟：訪問起始點v;依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖直至圖中所有和v有路徑相通的頂點都被訪問到。2深度優(yōu)先搜索和廣度優(yōu)先搜索圖常用的遍歷：一、深度優(yōu)先搜v1v1v2v3v8v7v6v4v5DFS結(jié)果：例1：→→→→→→→v2v4v8v5v3v6v7起點應退回到V8，因為V2已有標記voidDFS(GraphG,intv){//從頂點v出發(fā)，深度優(yōu)先遍歷Gvisited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);

//對v的尚未訪問的鄰接頂點w遞歸調(diào)用DFS}//DFS3v1v1v2v3v8v7v6v4v5DFS結(jié)果：例1：→→對于無向圖，這個算法可以遍歷到v頂點所在的連通分量中的所有頂點，而與v頂點不在一個連通分量中的所有頂點遍歷不到；對于有向圖可以遍歷到起始頂點v能夠到達的所有頂點。若希望遍歷到圖中的所有頂點，就需要在上述深度優(yōu)先遍歷算法的基礎(chǔ)上，增加對每個頂點訪問狀態(tài)的檢測。2、非連通圖的深度優(yōu)先搜索遍歷步驟：訪問起始點v及圖中所有和v有路徑相通的頂點。如果圖中尚有頂點未被訪問，則以該頂點為起始點，進行深度優(yōu)先搜索遍歷。重復上述過程，直至所有頂點都已被訪問。4對于無向圖，這個算法可以遍歷到v頂點所在的連通分量中的所abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg訪問標志:訪問次序:例2:0123456788123456705abchdekfgFFFFFvoid

DFSTraverse(GraphG,Status(*Visit)(intv)){

//對圖G作深度優(yōu)先遍歷。

VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;

//訪問標志數(shù)組初始化

for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);

//對尚未訪問的頂點調(diào)用DFS}6voidDFSTraverse(GraphG,6DFS算法效率分析:（設圖中有n個頂點，e條邊）（1）如果用鄰接矩陣來表示圖，遍歷圖中每一個頂點都要從頭掃描該頂點所在行，因此遍歷全部頂點所需的時間為O(n2)。（2）如果用鄰接表來表示圖，雖然有2e個表結(jié)點，但只需掃描e個結(jié)點即可完成遍歷，加上訪問n個頭結(jié)點的時間，因此遍歷圖的時間復雜度為O(n+e)。結(jié)論：稠密圖適于在鄰接矩陣上進行深度優(yōu)先遍歷；稀疏圖適于在鄰接表上進行深度優(yōu)先遍歷。7DFS算法效率分析:（設圖中有n個頂點，e條邊）結(jié)二、廣度優(yōu)先搜索(BFS)基本思想：——仿樹的層次遍歷過程。Breadth_FirstSearch在訪問了起始點v之后，依次訪問v的各個未曾訪問過的鄰接點；然后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。步驟：8二、廣度優(yōu)先搜索(BFS)基本思想：——仿樹的層次遍歷過v1v1v2v3v8v7v6v4v5BFS結(jié)果：例1：→→→→v2v3→v4v5→v6v7→v8v3→BFS結(jié)果：→

v4

→v5→起點起點v2→v1→v6v9→v8→v7例2：9v1v1v2v3v8v7v6v4v5BFS結(jié)果：例1：→→討論：答:利用一個隊列結(jié)構(gòu)記錄頂點訪問順序，將訪問的每個頂點入隊，然后，再依次出隊，出隊時訪問其鄰接點并將鄰接點入隊。（2）如何避免重復訪問某個頂點？（1）在廣度優(yōu)先遍歷中，要求先被訪問的頂點其鄰接點也被優(yōu)先訪問，應采用何種方式記錄頂點訪問順序？答：創(chuàng)建一個一維數(shù)組visited[0..n-1]（n是圖中頂點的數(shù)目），用來記錄每個頂點是否已經(jīng)被訪問過。（3）廣度優(yōu)先搜索有回退的情況嗎？10討論：答:利用一個隊列結(jié)構(gòu)記錄頂點訪問順序，將訪問的每個頂點答：廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有回退的情況。因此廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。

void

BFSTraverse(GraphG,Status(*Visit)(intv)){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;

//初始化訪問標志

InitQueue(Q);

//置空的輔助隊列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){//v尚未訪問

…………}}//BFSTraverse11答：廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一visited[v]=TRUE;Visit(v);//訪問vEnQueue(Q,v);

//v入隊列while(!QueueEmpty(Q)){

DeQueue(Q,u);

//隊頭元素出隊并置為ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;Visit(w);

EnQueue(Q,w);

//訪問的頂點w入隊列

}//if}//while12visited[v]=TRUE;Visit(v);BFS算法效率分析:如果使用鄰接表來表示圖，則BFS循環(huán)的總時間代價為

d0+d1+…+dn-1=O(e)，其中的

di是頂點

i的度。如果使用鄰接矩陣，則BFS對于每一個被訪問到的頂點，都要循環(huán)檢測矩陣中的整整一行（

n個元素），總的時間代價為O(n2)。（設圖中有n個頂點，e條邊）空間復雜度相同，都是O(n)(借用堆棧或隊列裝n個頂點）；時間復雜度只與存儲結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無關(guān)。DFS與BFS之比較：13BFS算法效率分析:如果使用鄰接表來表示圖，則BFS循環(huán)的生成樹：是一個極小連通子圖，它含有圖中全部頂點，但只有n-1條邊。生成森林：由若干棵生成樹組成，含全部頂點，但構(gòu)成這些樹的邊是最少的。（對有向或無向圖均適用）思考1：若對連通圖進行遍歷，得到的是什么？一個極小連通子圖，即圖的生成樹！由深度優(yōu)先搜索得到的生成樹，為深度優(yōu)先生成樹。由廣度優(yōu)先搜索得到的生成樹，為廣度優(yōu)先生成樹。思考2：若對非連通圖進行遍歷，得到的是什么？各連通分量的生成樹，即圖的生成森林！7.4圖的連通性1.求無向圖的生成樹（或生成森林）14生成樹：是一個極小連通子圖，它含有圖中全部頂點，但只有n-1例1：畫出下圖的生成樹。DFS生成樹v0v1v2v4v4v3鄰接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成樹v0v1v3v2v4v0v1v2v4v4v3v0v1v2v4v4v315例1：畫出下圖的生成樹。DFS生成樹v0v1v2v4v4vDEABCFJLMGHIK例2：畫出下圖的生成森林（或極小連通子圖）下面選用鄰接表方式來求深度優(yōu)先生成森林16DEABCFJLMGHIK例2：畫出下圖的生成森林（或極小連1155M12L11K10J9I8H7G6F5E4D3C2B1A012^^0^120^0^4^378^106^6^1011^126^709^1219^111^1229^47^10811DFS結(jié)果：ABMJLCFDEGHKI171155M12L11K10J9I8H7G6F5E4D3C2BDEGHIK子圖1：子圖2：子圖3：AFCMLBJDEGHIKAFCMLBJ生成森林注：圖的生成樹（生成森林）不唯一！18DEGHIK子圖1：子圖2：子圖3：AFCMLBJDEGHI2.求無向網(wǎng)的最小生成樹目標：在網(wǎng)絡的多個生成樹中，尋找一個各邊權(quán)值之和最小的生成樹。即在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。欲在n個城市間建立通信網(wǎng)，則n個城市應鋪n-1條線路；但因為每條線路都會有對應的經(jīng)濟成本，而n個城市可能有n(n-1)/2條線路，那么，如何選擇n–1條線路使總費用最少？典型用途：最小生成樹（MST）的性質(zhì)如下：V是頂點集，U是V的一個非空子集，若(u0,v0)是一條最小權(quán)值的邊，其中u0

U，v0

V-U；則：(u0,v0)必在最小生成樹上。192.求無向網(wǎng)的最小生成樹目標：在網(wǎng)絡的多個生成樹中，尋找求MST有多種算法，但最常用的是以下兩種：Prim（普里姆）算法Kruskal（克魯斯卡爾）算法Prim算法特點:頂點歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)。Kruskal算法特點：邊歸并，適于求稀疏網(wǎng)。對邊操作對頂點操作普里姆算法的基本思想:在生成樹的構(gòu)造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U和尚未落在生成樹上的頂點集V-U，則應在所有連通U中頂點和V-U中頂點的邊中選取權(quán)值最小的邊。如圖所示：20求MST有多種算法，但最常用的是以下兩種：Prim（普里姆）abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67集合U集合V-Uu0v021abcdegf例如:195141827168213ae12d方法：設置一個輔助數(shù)組，對當前V－U集中的每個頂點，記錄和頂點集U中頂點相連接的代價最小的邊。對每個屬于V-U的頂點vi，在輔助數(shù)組中存在一個相應的分量closedge[i-1]，它包含兩個域，其中l(wèi)owcost存儲該邊上的權(quán)。顯然，closedge[i-1].lowcost＝Min{cost(u,vi)|u€U}存儲方式：struct{VertexTypeadjvex;//U集中的頂點序號

VRTypelowcost;//邊的權(quán)值}closedge[MAX_VERTEX_NUM];22方法：設置一個輔助數(shù)組，對當前V－U集中的每個頂點，記錄和頂abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd721