【文章內(nèi)容簡介】 //該邊依附的兩個(gè)頂點(diǎn)的位置 struct EBox *ilink, *jlink。 //分別指向依附于 ivex和 jvex的下一條邊 InfoType *info。 // 該邊信息指針 } EBox。 邊的結(jié)構(gòu)表示 mark ivex ilink jvex jlink info 2022/3/13 61 typedef struct { // 鄰接多重表 VexBox adjmulist[MAX_VERTEX_NUM]。 int vexnum, edgenum。 } AMLGraph。 頂點(diǎn)的結(jié)構(gòu)表示 typedef struct VexBox { VertexType data。 EBox *firstedge。 // 指向第一條依附該頂點(diǎn)的邊 } VexBox。 無向圖的結(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 知識回顧 ? 圖的定義 ? 圖的存儲 2022/3/13 64 圖的遍歷 從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍 圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn) 僅被訪問一次的過程。 深度優(yōu)先搜索 廣度優(yōu)先搜索 2022/3/13 65 從圖中某個(gè)頂點(diǎn) V0 出發(fā)，訪問此頂點(diǎn)，然后 依次從 V0的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖 ， 直至圖中所有和 V0有路徑相通的頂點(diǎn)都被訪問到。 一、深度優(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 的子圖。 訪問頂點(diǎn) V ： for (W W W3 ) 若 該鄰接點(diǎn) W未被訪問 ， 則 從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。 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 可見 : 1. 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷； 為每個(gè)頂點(diǎn)設(shè)立一個(gè) “訪問標(biāo)志 visited[w]”。 2. 如何判別 V的鄰接點(diǎn)是否被訪問？ 深度優(yōu)先搜索（遍歷）步驟： 簡單歸納： ? 訪問起始點(diǎn) v。 ? 若 v的第 1個(gè)鄰接點(diǎn)沒訪問過，深度遍歷此鄰接點(diǎn)； ? 若當(dāng)前鄰接點(diǎn)已訪問過，再找 v的第 2個(gè)鄰接點(diǎn)重新遍歷。 2022/3/13 70 詳細(xì)歸納： ?在訪問圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問 它的任一鄰接頂點(diǎn) w1； ?再從 w1 出發(fā)，訪問 與 w1鄰接 但還 未被訪問 過的頂點(diǎn) w2； ?然后再從 w2 出發(fā)，進(jìn)行類似的訪問， … ?如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。 ?接著，退回一步， 退到前一次剛訪問過的頂點(diǎn) ，看是否還有其它未被訪問的鄰接頂點(diǎn)。 如果有 ， 則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問； 如果沒有 ， 就 再退回一步 進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。 ? 連通圖 的深度優(yōu)先遍歷算法 – 遞歸算法 開始 訪問 V0,置 標(biāo)志 求 V0鄰接點(diǎn) 有鄰接點(diǎn) w 求下一鄰接點(diǎn) w?V0 W訪問過 結(jié)束 N Y N Y DFS Boolean visited[MAX] //訪問標(biāo)志數(shù)組 Status（ *VisitFunc)(int v)。//函數(shù)變量 2022/3/13 73 void DFS(Graph G, int v) { // 從頂點(diǎn) v出發(fā)， 深度優(yōu)先搜索遍歷 連通圖 G visited[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 V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍歷： V1? 1 2 3 4 V1 V3 V4 V2 vexdata firstarc 2 7 8 3 ^ ^ ^ adjvex next 5 V5 6 4 1 ^ 5 1 2 8 2 ^ V6 V7 V8 6 7 8 7 3 6 3 5 4 ^ ^ ^ V3 ? V7 ? V6 ? V2 ? V5 ? V8 ? V4 DFS(Graph G, int v){ visited[v] = TRUE。 VisitFunc(v)。 for(w=FirstAdjVex(G, v)。 w!=0。 w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w)。} 2022/3/13 75 首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為 FALSE, 之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。 非連通圖 的深度優(yōu)先搜索遍歷 2022/3/13 76 void DFSTraverse(Graph G, Status (*Visit)(int v)) { // 對圖 G 作深度優(yōu)先遍歷。 VisitFunc = Visit。 for (v=0。 v。 ++v) visited[v] = FALSE。 // 訪問標(biāo)志數(shù)組初始化 for (v=0。 v。 ++v) if (!visited[v]) DFS(G, v)。 // 對尚未訪問的頂點(diǎn)調(diào)用 DFS } 2022/3/13 77 a b c h d e k f g F F F F F F F F F T T T T T T T T T a c h d k f e b g 訪問標(biāo)志 : 訪問次序 : 例如 : 0 1 2 3 4 5 6 7 8 2022/3/13 78 算法分析 ? 對每個(gè)頂點(diǎn)至多調(diào)用一次 DFS函數(shù)。遍歷圖的過程實(shí)質(zhì)上是對每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程。 – 采用二維數(shù)組： O(n2) – 采用鄰接表： O(n+e) 基本思想： —— 仿樹的層次遍歷過程 。 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ā)，并在訪問此頂點(diǎn)之后 依次訪問 V0的所有 未被訪問 過的鄰接點(diǎn) ，之后 按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn) ，直至圖中所有和 V0有路徑相通的頂點(diǎn)都被訪問到。 若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。 2022/3/13 81 V w1 w8 w3 w7 w6 w2 w5 w4 對連通圖，從起始點(diǎn) V到其余各頂點(diǎn)必定存在路徑。 其中， Vw1, Vw2, Vw8 的路徑長度為 1； Vw7, Vw3, Vw5 的 路徑長度為 2； Vw6, Vw4 的路徑長度為 3。 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)先搜索（遍歷）步驟： 簡單歸納： ? 在訪問了起始點(diǎn) v之后，依次訪問 v的鄰接點(diǎn)； ? 然后再依次 （順序） 訪問這些點(diǎn) （下一層） 中未被訪問過的鄰接點(diǎn)； ? 直到所有頂點(diǎn)都被訪問過為止。 廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。 因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程，其算法也不是遞歸的。 ? 廣度優(yōu)先遍歷算法 開始 標(biāo)志數(shù)組初始化 Vi=1 Vi訪問過 BFS Vi=Vi+1 Vi==Vexnums 結(jié)束 N N Y Y 開始 訪問 V0,置 標(biāo)志 求 V鄰接點(diǎn) w w存在嗎 V下一鄰接點(diǎn) ?w w訪問過 結(jié)束 N Y N Y BFS 初始化隊(duì)列 V0入隊(duì) 隊(duì)列空嗎 隊(duì)頭 V出隊(duì) 訪問 w,置 標(biāo)志 w入隊(duì) N a a Y 2022/3/13 85 void BFSTraverse(Graph G, Status (*Visit)(int v)){ for (v=0。 v。 ++v) visited[v] = FALSE。 //初始化訪問標(biāo)志 InitQueue(Q)。 // 置空的輔助隊(duì)列 Q for ( v=0。 v。 ++v ) if ( !visited[v]) { // v 尚未訪問 } } // BFSTraverse … … 2022/3/13 86 visited[v] = TRUE。 Visit(v)。 // 訪問 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 ( ! visited[w]) { visited[w]=TRUE。 Visit(w)。 EnQueue(Q, w)。 // 訪問的頂點(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