【正文】 集。這就是該有向圖的兩個(gè)強(qiáng)連通分量的頂點(diǎn)集。將 v2從棧頂彈出后，再?gòu)捻旤c(diǎn) v1出發(fā)，在訪問(wèn)頂點(diǎn) v3 v4后，頂點(diǎn) v4不存在未訪問(wèn)的鄰接點(diǎn)從而也成為 “ 死結(jié)點(diǎn) ” ，如圖 (c)所示。 ⑶ 每一次逆向深度優(yōu)先遍歷所訪問(wèn)到的頂點(diǎn)集便是該有向圖的一個(gè)強(qiáng)連通分量的頂點(diǎn)集，若僅作一次逆向深度優(yōu)先遍歷就能訪問(wèn)到圖的所有頂點(diǎn)，則該圖是強(qiáng)連通圖。 //從第 w個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖 G，建立子生成樹 q }//if }//DFSTree 從第 v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖 G，建立以 T為根的生成樹 例 A B L M C F D E G H K I J A B L M C F J D E G H K I 深度優(yōu)先生成森林 A B L M C F D E G H J K I A L M ^ ^ J ^ B ^ D ^ E ^ G ^ K ^ H ^ ^ I ^ ^ F ^ C ^ T 二、有向圖的強(qiáng)連通分量 深度優(yōu)先遍歷是求有向圖的強(qiáng)連通分量的一個(gè)有效方法，具體求解步驟如下： ⑴ 在有向圖中，從某個(gè)頂點(diǎn)出發(fā)進(jìn)行 深度優(yōu)先遍歷 ，并按其所有鄰接點(diǎn)的訪問(wèn)都完成 （即 出棧 ）的順序?qū)㈨旤c(diǎn)排列起來(lái)。} //是上一鄰接頂點(diǎn)的右兄弟結(jié)點(diǎn) q=p。 first=FALSE。//分配孩子結(jié)點(diǎn) *p={GetVex(G,w),NULL,NULL}。w=0。 first=TRUE。 Void DFSTree(Graph G,int v,CSTree amp。 //q指示當(dāng)前生成樹的根 DFSTree(G,v,p)。 //是第一棵樹的根 else qnextsibling=p。 //分配根結(jié)點(diǎn) *p={GetVex(G,v),NULL,NULL}。v。 ++v) visited[v]=FALSE。 for(v=0。 頂點(diǎn)集和遍歷圖過(guò)程中歷經(jīng)的邊的集合 構(gòu)成連通圖的 極小連通子圖 ，它是連通圖的一棵 生成樹 非連通圖 連通圖 V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍歷： V1? V2 ?V4 ? V8 ?V5 ?V3 ?V6 ?V7 V1 V2 V4 V5 V3 V7 V6 V8 深度優(yōu)先生成樹 V1 V2 V4 V5 V3 V7 V6 V8 廣度優(yōu)先生成樹 V1 V2 V4 V5 V3 V7 V6 V8 V1 V2 V4 V5 V3 V7 V6 V8 廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 2022/3/13 93 A B M L C F J D E H K G I A B M L C F J D E G K I H 2022/3/13 94 假設(shè)以 孩子兄弟鏈表 作生成森林的存儲(chǔ)結(jié)構(gòu) ,建立無(wú)向圖 G的深度優(yōu)先生成森林的孩子兄弟鏈表 Void DFSForest(Graph G,CSTree amp。 每個(gè) 連通分量中的頂點(diǎn)集，和遍歷時(shí)走過(guò)的邊 一起構(gòu)成若干棵 生成樹 ，這些連通分量的生成樹組成非連通圖的 生成森林 。 // 訪問(wèn)的頂點(diǎn) w入隊(duì)列 } // if } // while 例 1 4 2 3 5 1 2 3 4 1 3 4 2 vexdata firstarc 5 5 4 3 ^ ^ ^ adjvex next 5 5 1 ^ 5 1 1 4 3 ^ 2 2 1 0 1 2 3 4 5 f r 遍歷序列： 1 0 1 2 3 4 5 4 f r 遍歷序列： 1 4 0 1 2 3 4 5 4 3 f r 遍歷序列： 1 4 3 例 1 4 2 3 5 1 2 3 4 1 3 4 2 vexdata firstarc 5 5 4 3 ^ ^ ^ adjvex next 5 5 1 ^ 5 1 1 4 3 ^ 2 2 0 1 2 3 4 5 4 3 2 f r 遍歷序列： 1 4 3 2 0 1 2 3 4 5 3 2 f r 遍歷序列： 1 4 3 2 0 1 2 3 4 5 3 2 5 f r 遍歷序列： 1 4 3 2 5 0 1 2 3 4 5 2 5 f r 遍歷序列： 1 4 3 2 5 0 1 2 3 4 5 5 f r 遍歷序列： 1 4 3 2 5 0 1 2 3 4 5 f r 遍歷序列： 1 4 3 2 5 例 1 4 2 3 5 1 2 3 4 1 3 4 2 vexdata firstarc 5 5 4 3 ^ ^ ^ adjvex next 5 5 1 ^ 5 1 1 4 3 ^ 2 2 一、無(wú)向圖的連通分量與生成樹 對(duì)無(wú)向圖進(jìn)行遍歷時(shí) ?對(duì)于 連通圖 ，從 任一頂點(diǎn) 出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問(wèn)圖中 所有頂點(diǎn) 。 Visit(w)。 w!=0。 // v入隊(duì)列 while (!QueueEmpty(Q)) { DeQueue(Q, u)。 Visit(v)。 v。 //初始化訪問(wèn)標(biāo)志 InitQueue(Q)。 v。 因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程，其算法也不是遞歸的。 V1 V2 V4 V5 V3 V7 V6 V8 例 例 V1 V2 V4 V5 V3 V7 V6 V8 廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 廣度優(yōu)先搜索（遍歷）步驟： 簡(jiǎn)單歸納： ? 在訪問(wèn)了起始點(diǎn) v之后，依次訪問(wèn) v的鄰接點(diǎn)； ? 然后再依次 （順序） 訪問(wèn)這些點(diǎn) （下一層） 中未被訪問(wèn)過(guò)的鄰接點(diǎn)； ? 直到所有頂點(diǎn)都被訪問(wèn)過(guò)為止。 2022/3/13 81 V w1 w8 w3 w7 w6 w2 w5 w4 對(duì)連通圖，從起始點(diǎn) V到其余各頂點(diǎn)必定存在路徑。 v3 → BFS 結(jié)果 v4 → v5 → 起點(diǎn) v2 → v1 → v6 → v9 → v8 → v7 二、廣度優(yōu)先搜索遍歷圖 （ Breadth_First Search） 2022/3/13 80 從圖中的某個(gè)頂點(diǎn) V0出發(fā)，并在訪問(wèn)此頂點(diǎn)之后 依次訪問(wèn) V0的所有 未被訪問(wèn) 過(guò)的鄰接點(diǎn) ，之后 按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)它們的鄰接點(diǎn) ，直至圖中所有和 V0有路徑相通的頂點(diǎn)都被訪問(wèn)到。遍歷圖的過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程。 ++v) if (!visited[v]) DFS(G, v)。 // 訪問(wèn)標(biāo)志數(shù)組初始化 for (v=0。 v。 VisitFunc = Visit。} 2022/3/13 75 首先將圖中每個(gè)頂點(diǎn)的訪問(wèn)標(biāo)志設(shè)為 FALSE, 之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問(wèn)，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。 w!=0。 VisitFunc(v)。 w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w)。 for(w=FirstAdjVex(G, v)。//函數(shù)變量 2022/3/13 73 void DFS(Graph G, int v) { // 從頂點(diǎn) v出發(fā)， 深度優(yōu)先搜索遍歷 連通圖 G visited[v] = TRUE。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。 ?接著，退回一步， 退到前一次剛訪問(wèn)過(guò)的頂點(diǎn) ，看是否還有其它未被訪問(wèn)的鄰接頂點(diǎn)。 ? 若 v的第 1個(gè)鄰接點(diǎn)沒(méi)訪問(wèn)過(guò)，深度遍歷此鄰接點(diǎn)； ? 若當(dāng)前鄰接點(diǎn)已訪問(wèn)過(guò)，再找 v的第 2個(gè)鄰接點(diǎn)重新遍歷。 w2 w3 2022/3/13 67 V1 V2 V4 V5 V3 V7 V6 V8 V1 V2 V4 V5 V3 V7 V6 V8 深度遍歷： 深度遍歷： V1? V2 ?V4 ? V8 ?V5 ?V6 ?V3 ?V7 V2 V1 V4 V8 V5 V6 V3 V7 2022/3/13 68 可見(jiàn) : 1. 從深度優(yōu)先搜索遍歷連通圖的過(guò)程類似于樹的先根遍歷； 為每個(gè)頂點(diǎn)設(shè)立一個(gè) “訪問(wèn)標(biāo)志 visited[w]”。 一、深度優(yōu)先搜索遍歷圖 （ Depth_First Search） 連通圖 的深度優(yōu)先搜索遍歷 2022/3/13 66 V w1 SG1 SG2 SG3 W W2和 W3 均為 V 的鄰接點(diǎn)， SG SG2 和 SG3 分別為含頂點(diǎn) WW2和 W3 的子圖。 無(wú)向圖的結(jié)構(gòu)表示 例 a e c b d 1 2 3 4 a c d b 5 e 1 2 1 4 3 4 3 2 3 5 5 2 ^ ^ ^ ^ ^ 2022/3/13 63 知識(shí)回顧 ? 圖的定義 ? 圖的存儲(chǔ) 2022/3/13 64 圖的遍歷 從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍 圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn) 僅被訪問(wèn)一次的過(guò)程。 EBox *firstedge。 } AMLGraph。 邊的結(jié)構(gòu)表示 mark ivex ilink jvex jlink info 2022/3/13 61 typedef struct { // 鄰接多重表 VexBox adjmulist[MAX_VERTEX_NUM]。 //分別指向依附于 ivex和 jvex的下一條邊 InfoType *info。 // 訪問(wèn)標(biāo)記 int ivex, jvex。 Firstout Firstin data 頂點(diǎn)結(jié)點(diǎn) info tlink hlink headvex tailvex 弧結(jié)點(diǎn) 此無(wú)權(quán)圖未開(kāi)第 4分量 空間復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接表相同 。 有向圖的結(jié)構(gòu)表示 (十字鏈表 ) 例：畫出有向圖的十字鏈表。 // 頂點(diǎn)結(jié)點(diǎn) (表頭向量 ) int vexnum, arum。 } VexNode。 2022/3/13 57 頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu) 頂點(diǎn)信息數(shù)據(jù) 指向該頂點(diǎn)的第一條入弧 指向該頂點(diǎn)的第一條出弧 typedef struct VexNode { // 頂點(diǎn)的結(jié)構(gòu)表示 VertexType data。 struct ArcBox *hlink, *tlink。 開(kāi)設(shè) 弧結(jié)點(diǎn) ， 設(shè) 5個(gè)域 （每段弧是一個(gè)數(shù)據(jù)元素） 開(kāi)設(shè) 頂點(diǎn)結(jié)點(diǎn) ， 設(shè) 3個(gè)域 （每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素） tailvex headvex hlink tlink info data : 頂點(diǎn)信息 Firstin : 以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn) Firstout: 以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn) data Firstin Firstout 頂點(diǎn)結(jié)點(diǎn) 弧結(jié)點(diǎn) tailvex: 弧尾頂點(diǎn)位置 headvex: 弧頭頂點(diǎn)位置 hlink: 弧頭相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息 n個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？ 仍用順序存儲(chǔ)結(jié)構(gòu) 三、有向圖的十字鏈表存儲(chǔ)表示 2022/3/13 56 弧的結(jié)點(diǎn)結(jié)構(gòu) 弧尾頂點(diǎn)位置 弧頭頂點(diǎn)位置