數(shù)據(jù)結(jié)構(gòu)第17講圖的遍歷與連通性C.ppt

7.2 圖的存儲結(jié)構(gòu),圖的數(shù)組(鄰接矩陣)存儲表示 圖的鄰接表存儲表示 有向圖的十字鏈表存儲表示 無向圖的鄰接多重表存儲表示,鄰接矩陣是用于描述圖中頂點(diǎn)之間關(guān)系(即弧或邊的權(quán))的矩陣。 鄰接表類似樹的孩子鏈表。即對圖中的每個頂點(diǎn)vi建立一個單鏈表，表中結(jié)點(diǎn)表示依附于該頂點(diǎn)vi的邊或弧。,表結(jié)點(diǎn),表頭結(jié)點(diǎn),V1,V3,V2,V4,例：,3.有向圖的十字鏈表存儲表示,兩種結(jié)點(diǎn)結(jié)構(gòu)：,頂點(diǎn)結(jié)點(diǎn),弧結(jié)點(diǎn),0 1 2 3,v3,v1,v4,v2,例：,tailvex,headvex,hlink,tlink,/,4.無向圖的鄰接多重表存儲表示,邊結(jié)點(diǎn),頂點(diǎn)結(jié)點(diǎn),例：,第7章 圖 7.1 圖的定義和術(shù)語 7.2 圖的存儲結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的連通性問題 7.5 有向無環(huán)圖及其應(yīng)用 7.6 最短路徑,7.3 圖的遍歷,從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個頂點(diǎn)僅被訪問一次。這一過程就叫做圖的遍歷。 通常有兩條遍歷圖的路徑： 深度優(yōu)先搜索 廣度優(yōu)先搜索,1.深度優(yōu)先搜索(DFS),基本思想： 從圖中某頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)，然后依次從V0的各個未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到； 若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)； 重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。,例：從頂點(diǎn)v1出發(fā)，DFS下圖。,頂點(diǎn)訪問序列為：v1,v2,v4,v8,v5,v3,v6,v7,圖的DFS算法一般描述 int visitedMAXVEX; /訪問標(biāo)志數(shù)組 void DFSgraph(Graph G, Visit() /對圖G作深度優(yōu)先遍歷 for( v=0; vG.vexnum; +v ) visitedv=FALSE; /訪問標(biāo)志數(shù)組初始化 for( v=0; vG.vexnum; +v ) if( !visitedv ) DFS(G,v); /對尚未訪問的頂點(diǎn)調(diào)用DFS ,void DFS (Graph G,int v) /從第v個頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G visitedv=TRUE ; Visit(v); /訪問第v個頂點(diǎn) for(w=FirstAdjVex(G,v); w=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G,w); /對v的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用DFS ,用鄰接表實(shí)現(xiàn)圖的深度優(yōu)先搜索,v1,v6,v2,v5,v3,v8,v4,v7,v9,v10,分析： 在遍歷圖時，對圖中每個頂點(diǎn)至多調(diào)用一次DFS函數(shù)，因?yàn)橐坏┠硞€頂點(diǎn)被標(biāo)志成已被訪問，就不再從它出發(fā)進(jìn)行搜索。 因此，遍歷圖的過程實(shí)質(zhì)上是對每個頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(fèi)的時間則取決于所采用的存儲結(jié)構(gòu)。,2.廣度優(yōu)先搜索(BFS),基本思想： 從圖中某個頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到； 若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)； 重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。,例：從頂點(diǎn)v1出發(fā)，BFS下圖。,頂點(diǎn)訪問序列為：v1,v2,v3,v4,v5,v6,v7,v8,用鄰接表實(shí)現(xiàn)圖的廣度優(yōu)先搜索,BFS非遞歸算法,void BFSTraverse(Graph G, Status (*Visit)(int v) /使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visitedv for (v=0; vG.vexnum; +v) visitedv = FALSE; InitQueue(Q); / 置空的輔助隊(duì)列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v尚未訪問 visitedv = TRUE; Visit(v); EnQueue(Q, v); / v入隊(duì),while (!QueueEmpty(Q) DeQueue(Q, u); / 隊(duì)頭元素出隊(duì)并置為u for (w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)） if ( ! visitedw) /w為u的尚未訪問的鄰接頂點(diǎn) visitedw = TRUE; Visit(w); EnQueue(Q, w); /if /while if / BFSTraverse,分析： 每個頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過程實(shí)質(zhì)上是通過邊或弧找鄰接點(diǎn)的過程，因此廣度優(yōu)先搜索遍歷圖的時間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅在于對頂點(diǎn)訪問的順序不同。,第7章 圖 7.1 圖的定義和術(shù)語 7.2 圖的存儲結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的連通性問題 7.5 有向無環(huán)圖及其應(yīng)用 7.6 最短路徑,7.4 圖的連通性問題,1）無向圖的連通分量和生成樹 2）最小生成樹 3）普里姆算法 4）克魯斯卡爾算法,1.無向圖的連通分量和生成樹 基本概念 連通分量的頂點(diǎn)集：即從該連通分量的某一頂點(diǎn)出發(fā)進(jìn)行搜索所得到的頂點(diǎn)訪問序列； 生成樹：某連通分量的極小連通子圖； 生成森林：非連通圖的各個連通分量的極小連通子圖構(gòu)成的集合。,設(shè)E(G)為連通子圖G中所有邊的集合，則從圖中任一頂點(diǎn)出發(fā)遍歷圖時，必定將E(G)分成兩個集合T(G)和B(G)，其中T(G)是遍歷過程中歷經(jīng)的邊的集合。顯然，T(G)和圖G中所有頂點(diǎn)一起構(gòu)成連通圖G的極小連通子圖，按照7.1節(jié)的定義，它是連通圖的一棵生成樹，并且稱由深度優(yōu)先搜索得到的為深度優(yōu)先生成樹；由廣度優(yōu)先搜索得到的為廣度優(yōu)先生成樹。,例：求下圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。,對非連通圖，每個連通分量中的頂點(diǎn)集和遍歷時走過的邊一起構(gòu)成若干棵生成樹，這些連通分量的生成樹組成非連通圖的生成森林。 例：,生成非連通圖的深度優(yōu)先生成森林的算法,void DFSForest (Graph G，CSTree /建立以p為根的生成樹 /DFSForest,void DFSTree (Graph G，int v，CSTree /分配孩子結(jié)點(diǎn) *p=GetVex(G,w)，NULL，NULL； if(first) /w是v的第一個未被訪問的鄰接頂點(diǎn) Tlchild=p；first=FALSE；/是根的左孩子結(jié)點(diǎn) else /w是v的其它未被訪問的鄰接頂點(diǎn) qnextsibling =p；/是上一鄰接頂點(diǎn)的右兄弟結(jié)點(diǎn) q = p； DFSTree(G, w, q)； /從第w個頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立子生成樹q /if /DFSTree,1.理解并掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜