圖的遍歷和連通性

圖的遍歷和連通性第一頁，共二十五頁，2022年，8月28日17.3圖的遍歷遍歷：從已給的連通圖中某一頂點出發(fā)，沿著一些邊，訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。遍歷實質：找每個頂點的鄰接點的過程。圖的特點：圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點。解決思路：可設置一個輔助數組

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

被訪問，就立即改visited[i]為true，防止它被重復訪問。怎樣避免重復訪問？第二頁，共二十五頁，2022年，8月28日2深度優(yōu)先搜索和廣度優(yōu)先搜索圖常用的遍歷：一、深度優(yōu)先搜索(DFS)Depth_FirstSearch基本思想：——類似于樹的先根遍歷過程。1、連通圖的深度優(yōu)先搜索遍歷步驟：訪問起始點v;依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖直至圖中所有和v有路徑相通的頂點都被訪問到。第三頁，共二十五頁，2022年，8月28日3v1v1v2v3v8v7v6v4v5DFS結果：例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遞歸調用DFS}//DFS第四頁，共二十五頁，2022年，8月28日4對于無向圖，這個算法可以遍歷到v頂點所在的連通分量中的所有頂點，而與v頂點不在一個連通分量中的所有頂點遍歷不到；對于有向圖可以遍歷到起始頂點v能夠到達的所有頂點。若希望遍歷到圖中的所有頂點，就需要在上述深度優(yōu)先遍歷算法的基礎上，增加對每個頂點訪問狀態(tài)的檢測。2、非連通圖的深度優(yōu)先搜索遍歷步驟：訪問起始點v及圖中所有和v有路徑相通的頂點。如果圖中尚有頂點未被訪問，則以該頂點為起始點，進行深度優(yōu)先搜索遍歷。重復上述過程，直至所有頂點都已被訪問。第五頁，共二十五頁，2022年，8月28日5abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg訪問標志:訪問次序:例2:012345678812345670第六頁，共二十五頁，2022年，8月28日6void

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

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

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

//訪問標志數組初始化

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

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

v4

→v5→起點起點v2→v1→v6v9→v8→v7例2：第十頁，共二十五頁，2022年，8月28日10討論：答:利用一個隊列結構記錄頂點訪問順序，將訪問的每個頂點入隊，然后，再依次出隊，出隊時訪問其鄰接點并將鄰接點入隊。（2）如何避免重復訪問某個頂點？（1）在廣度優(yōu)先遍歷中，要求先被訪問的頂點其鄰接點也被優(yōu)先訪問，應采用何種方式記錄頂點訪問順序？答：創(chuàng)建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來記錄每個頂點是否已經被訪問過。（3）廣度優(yōu)先搜索有回退的情況嗎？第十一頁，共二十五頁，2022年，8月28日11答：廣度優(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尚未訪問

…………}}//BFSTraverse第十二頁，共二十五頁，2022年，8月28日12visited[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}//while第十三頁，共二十五頁，2022年，8月28日13BFS算法效率分析:如果使用鄰接表來表示圖，則BFS循環(huán)的總時間代價為

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

di是頂點

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

n個元素），總的時間代價為O(n2)。（設圖中有n個頂點，e條邊）空間復雜度相同，都是O(n)(借用堆?；蜿犃醒bn個頂點）；時間復雜度只與存儲結構（鄰接矩陣或鄰接表）有關，而與搜索路徑無關。DFS與BFS之比較：第十四頁，共二十五頁，2022年，8月28日14生成樹：是一個極小連通子圖，它含有圖中全部頂點，但只有n-1條邊。生成森林：由若干棵生成樹組成，含全部頂點，但構成這些樹的邊是最少的。（對有向或無向圖均適用）思考1：若對連通圖進行遍歷，得到的是什么？一個極小連通子圖，即圖的生成樹！由深度優(yōu)先搜索得到的生成樹，為深度優(yōu)先生成樹。由廣度優(yōu)先搜索得到的生成樹，為廣度優(yōu)先生成樹。思考2：若對非連通圖進行遍歷，得到的是什么？各連通分量的生成樹，即圖的生成森林！7.4圖的連通性1.求無向圖的生成樹（或生成森林）第十五頁，共二十五頁，2022年，8月28日15例1：畫出下圖的生成樹。DFS生成樹v0v1v2v4v4v3鄰接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成樹v0v1v3v2v4v0v1v2v4v4v3v0v1v2v4v4v3第十六頁，共二十五頁，2022年，8月28日16DEABCFJLMGHIK例2：畫出下圖的生成森林（或極小連通子圖）下面選用鄰接表方式來求深度優(yōu)先生成森林第十七頁，共二十五頁，2022年，8月28日171155M12L11K10J9I8H7G6F5E4D3C2B1A012^^0^120^0^4^378^106^6^1011^126^709^1219^111^1229^47^10811DFS結果：ABMJLCFDEGHKI第十八頁，共二十五頁，2022年，8月28日18DEGHIK子圖1：子圖2：子圖3：AFCMLBJDEGHIKAFCMLBJ生成森林注：圖的生成樹（生成森林）不唯一！第十九頁，共二十五頁，2022年，8月28日192.求無向網的最小生成樹目標：在網絡的多個生成樹中，尋找一個各邊權值之和最小的生成樹。即在e條帶權的邊中選取n-1條邊（不構成回路），使“權值之和”為最小。欲在n個城市間建立通信網，則n個城市應鋪n-1條線路；但因為每條線路都會有對應的經濟成本，而n個城市可能有n(n-1)/2條線路，那么，如何選擇n–1條線路使總費用最少？典型用途：最小生成樹（MST）的性質如下：V是頂點集，U是V的一個非空子集，若(u0,v0)是一條最小權值的邊，其中u0U，v0V-U；則：(u0,v0)必在最小生成樹上。第二十頁，共二十五頁，2022年，8月28日20求MST有多種算法，但最常用的是以下兩種：Prim（普里姆）算法Kruskal（克魯斯卡爾）算法Prim算法特點:頂點歸并，與邊數無關，適于稠密網。Kruskal算法特點：邊歸并，適于求稀疏網。對邊操作對頂點操作普里姆算法的基本思想:在生成樹的構造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U和尚未落在生成樹上的頂點集V-U，則應在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。如圖所示：第二十一頁，共二十五頁，2022年，8月28日21abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹權值和=14+8+3+5+16+21=67集合U集合V-Uu0v0第二十二頁，共二十五頁，2022年，8月28日22方法：設置一個輔助數組，對當前V－U集中的每個頂點，記錄和頂點集U中頂點相連接的代價最小的邊。對每個屬于V-U的頂點vi，在輔助數組中存在一個相應的分量closedge[i-1]，它包含兩個域，其中l(wèi)owcost存儲該邊上的權。顯然，closedge[i-1].lowcost＝Min{cost(u,vi)|u€U}存儲方式：struct{VertexTypeadjvex;//U集中的頂點序號

VRTypelowcost;//邊的權值}closedge[MAX_VERTEX_NUM];第二十三頁，共二十五頁，2022年，8月28日23abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213