圖的遍歷和連通性

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

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

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

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

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

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

v4

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

void

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

//初始化訪問標(biāo)志

InitQueue(Q);

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

…………}}//BFSTraverse第十二頁，共二十五頁，2022年，8月28日12visited[v]=TRUE;Visit(v);//訪問vEnQueue(Q,v);

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

DeQueue(Q,u);

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

EnQueue(Q,w);

//訪問的頂點(diǎn)w入隊(duì)列

}//if}//while第十三頁，共二十五頁，2022年，8月28日13BFS算法效率分析:如果使用鄰接表來表示圖，則BFS循環(huán)的總時(shí)間代價(jià)為

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

di是頂點(diǎn)

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

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

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