數(shù)據(jù)結(jié)構(gòu)-圖的遍歷-資料下載頁
2025-08-05 07:30本頁面
【正文】 for (v=0。 v。 ++v) visited[v] = FALSE。 //初始化訪問標(biāo)志 InitQueue(Q)。 // 置空的輔助隊(duì)列 Q for ( v=0。 v。 ++v ) if ( !visited[v]) { // v 尚未訪問 } } // BFSTraverse … … 廣度優(yōu)先搜索 visited[v] = TRUE。 Visit(v)。 // 訪問 u EnQueue(Q, v)。 // v入隊(duì)列 while (!QueueEmpty(Q)) { DeQueue(Q, u)。 // 隊(duì)頭元素出隊(duì)并置為 u for(w=FirstAdjVex(G, u)。 w。 w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]=TRUE。 Visit(w)。 EnQueue(Q, w)。 // 訪問的頂點(diǎn) w入隊(duì)列 } // if } // while 課堂練習(xí) 1：無向圖 G=(V,E),其中： V={a,b,c,d,e,f}, E= {(a,b), (a,e), (a,c), (b,e), (c,f), (f,d), (e,d)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的（ ）。 A． a,b,e,c,d,f B． a,c,f,e,b,d C． a,e,b,c,f,d D． a,e,d,f,c,b a b e d c f 2：已知一無向圖 G=（ V， E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法從頂點(diǎn) a開始遍歷圖，得到的序列為 abecd，則采用的是 ____________。 課堂練習(xí) a d b e c 小結(jié)和作業(yè) 圖的遍歷定義、用途 圖的深度優(yōu)先搜索 圖的廣度優(yōu)先搜索 作業(yè)： 、 圖的遍歷方法 深度優(yōu)先搜索 連通圖 棧的變化 V1 V2 V4 V5 V3 V7 V6 V8 V1 V3 V2 V3 V5 V4 V3 V5 V8 V3 V5 V6 V5 V3 V5 V6 V3 V5 V3 V3 V5 V7 V3 V5 V3 深度優(yōu)先搜索 — 非連通圖 V1 V2 V4 V5 V3 V7 V6 V8 深度遍歷： V1? V2 ?V4 ? V8 ?V5 ?V3 ?V6 ?V7 2：遍歷圖的過程實(shí)質(zhì)上是 ______， breathfirst search遍歷圖的時(shí)間復(fù)雜度 ______； depthfirst search遍歷圖的時(shí)間復(fù)雜度 ______，兩者不同之處在于 ______，反映在數(shù)據(jù)結(jié)構(gòu)上的差別是______。 課堂練習(xí)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1