【文章內容簡介】 //該邊依附的兩個頂點的位置 struct EBox *ilink, *jlink。 //分別指向依附于 ivex和 jvex的下一條邊 InfoType *info。 // 該邊信息指針 } EBox。 邊的結構表示 mark ivex ilink jvex jlink info 2022/3/13 61 typedef struct { // 鄰接多重表 VexBox adjmulist[MAX_VERTEX_NUM]。 int vexnum, edgenum。 } AMLGraph。 頂點的結構表示 typedef struct VexBox { VertexType data。 EBox *firstedge。 // 指向第一條依附該頂點的邊 } VexBox。 無向圖的結構表示 例 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 圖的遍歷 從圖中某個頂點出發(fā)游歷圖，訪遍 圖中其余頂點，并且使圖中的每個頂點 僅被訪問一次的過程。 深度優(yōu)先搜索 廣度優(yōu)先搜索 2022/3/13 65 從圖中某個頂點 V0 出發(fā)，訪問此頂點，然后 依次從 V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖 ， 直至圖中所有和 V0有路徑相通的頂點都被訪問到。 一、深度優(yōu)先搜索遍歷圖 （ Depth_First Search） 連通圖 的深度優(yōu)先搜索遍歷 2022/3/13 66 V w1 SG1 SG2 SG3 W W2和 W3 均為 V 的鄰接點， SG SG2 和 SG3 分別為含頂點 WW2和 W3 的子圖。 訪問頂點 V ： for (W W W3 ) 若 該鄰接點 W未被訪問 ， 則 從它出發(fā)進行深度優(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)先搜索遍歷連通圖的過程類似于樹的先根遍歷； 為每個頂點設立一個 “訪問標志 visited[w]”。 2. 如何判別 V的鄰接點是否被訪問？ 深度優(yōu)先搜索（遍歷）步驟： 簡單歸納： ? 訪問起始點 v。 ? 若 v的第 1個鄰接點沒訪問過，深度遍歷此鄰接點； ? 若當前鄰接點已訪問過，再找 v的第 2個鄰接點重新遍歷。 2022/3/13 70 詳細歸納： ?在訪問圖中某一起始頂點 v 后，由 v 出發(fā)，訪問 它的任一鄰接頂點 w1； ?再從 w1 出發(fā)，訪問 與 w1鄰接 但還 未被訪問 過的頂點 w2； ?然后再從 w2 出發(fā)，進行類似的訪問， … ?如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。 ?接著，退回一步， 退到前一次剛訪問過的頂點 ，看是否還有其它未被訪問的鄰接頂點。 如果有 ， 則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問； 如果沒有 ， 就 再退回一步 進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。 ? 連通圖 的深度優(yōu)先遍歷算法 – 遞歸算法 開始 訪問 V0,置 標志 求 V0鄰接點 有鄰接點 w 求下一鄰接點 w?V0 W訪問過 結束 N Y N Y DFS Boolean visited[MAX] //訪問標志數組 Status（ *VisitFunc)(int v)。//函數變量 2022/3/13 73 void DFS(Graph G, int v) { // 從頂點 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的尚未訪問的鄰接頂點 w // 遞歸調用 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 首先將圖中每個頂點的訪問標志設為 FALSE, 之后搜索圖中每個頂點，如果未被訪問，則以該頂點為起始點，進行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點。 非連通圖 的深度優(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。 // 訪問標志數組初始化 for (v=0。 v。 ++v) if (!visited[v]) DFS(G, v)。 // 對尚未訪問的頂點調用 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 訪問標志 : 訪問次序 : 例如 : 0 1 2 3 4 5 6 7 8 2022/3/13 78 算法分析 ? 對每個頂點至多調用一次 DFS函數。遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程。 – 采用二維數組： O(n2) – 采用鄰接表： O(n+e) 基本思想： —— 仿樹的層次遍歷過程 。 v3 → BFS 結果 v4 → v5 → 起點 v2 → v1 → v6 → v9 → v8 → v7 二、廣度優(yōu)先搜索遍歷圖 （ Breadth_First Search） 2022/3/13 80 從圖中的某個頂點 V0出發(fā)，并在訪問此頂點之后 依次訪問 V0的所有 未被訪問 過的鄰接點 ，之后 按這些頂點被訪問的先后次序依次訪問它們的鄰接點 ，直至圖中所有和 V0有路徑相通的頂點都被訪問到。 若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。 2022/3/13 81 V w1 w8 w3 w7 w6 w2 w5 w4 對連通圖，從起始點 V到其余各頂點必定存在路徑。 其中， 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)先搜索（遍歷）步驟： 簡單歸納： ? 在訪問了起始點 v之后，依次訪問 v的鄰接點； ? 然后再依次 （順序） 訪問這些點 （下一層） 中未被訪問過的鄰接點； ? 直到所有頂點都被訪問過為止。 廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有回退的情況。 因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。 ? 廣度優(yōu)先遍歷算法 開始 標志數組初始化 Vi=1 Vi訪問過 BFS Vi=Vi+1 Vi==Vexnums 結束 N N Y Y 開始 訪問 V0,置 標志 求 V鄰接點 w w存在嗎 V下一鄰接點 ?w w訪問過 結束 N Y N Y BFS 初始化隊列 V0入隊 隊列空嗎 隊頭 V出隊 訪問 w,置 標志 w入隊 N a a Y 2022/3/13 85 void BFSTraverse(Graph G, Status (*Visit)(int v)){ for (v=0。 v。 ++v) visited[v] = FALSE。 //初始化訪問標志 InitQueue(Q)。 // 置空的輔助隊列 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入隊列 while (!QueueEmpty(Q)) { DeQueue(Q, u)。 // 隊頭元素出隊并置為 u for(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 例 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