數(shù)據(jù)結(jié)構(gòu)-圖的遍歷(參考版)
2025-08-08 07:30本頁(yè)面
【正文】 課堂練習(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：遍歷圖的過(guò)程實(shí)質(zhì)上是 ______， breathfirst search遍歷圖的時(shí)間復(fù)雜度 ______； depthfirst search遍歷圖的時(shí)間復(fù)雜度 ______，兩者不同之處在于 ______，反映在數(shù)據(jù)結(jié)構(gòu)上的差別是______。 // 訪問(wèn)的頂點(diǎn) w入隊(duì)列 } // if } // while 課堂練習(xí) 1：無(wú)向圖 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)序列正確的（ ）。 Visit(w)。 w。 // v入隊(duì)列 while (!QueueEmpty(Q)) { DeQueue(Q, u)。 Visit(v)。 v。 //初始化訪問(wèn)標(biāo)志 InitQueue(Q)。 v。 廣度優(yōu)先搜索 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)到。 Vw7, Vw3, Vw5的路徑長(zhǎng)度為 2。 廣度優(yōu)先搜索 V w1 w8 w3 w7 w6 w2 w5 w4 對(duì)連通圖，從起始點(diǎn) V到其余各頂點(diǎn)必定存在路徑。 // 對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用 DFS } } 深度優(yōu)先搜索 頂點(diǎn) V0 出發(fā)，訪問(wèn)此頂點(diǎn) 依次從 V0的 各個(gè)未被訪問(wèn)的 鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖 ， 直至圖中所有與 V0有路徑的頂點(diǎn)都被訪問(wèn)到。 v。 ++v) visited[v] = FALSE。 深度優(yōu)先搜索 — 非連通圖 a c h d k f e b g 訪問(wèn)次序 : a b c h d e k f g 8 1 2 3 4 5 6 7 0 a c h d k f e b g F F F F F F F F F 0 1 2 3 4 5 6 7 8 T T T T T T T T T 訪問(wèn)標(biāo)志 : 深度優(yōu)先搜索 — 非連通圖 void DFSTraverse(G
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1