數(shù)據(jù)結(jié)構(gòu)-圖的遍歷-預(yù)覽頁(yè)
【正文】 + n2 ?鄰接表用于 DG和 DN： n + e或者 n + 2e；用于UDG和 UDN： n + 2e ?十字鏈表 : n + e ?鄰接多重鏈表 : n + e 二、存儲(chǔ)空間 存儲(chǔ)結(jié)構(gòu)的比較 三、對(duì)操作的支持 對(duì)頂點(diǎn)的訪問(wèn) LocateVex(G, u)。 PutVex(amp。G, v)。 // 刪除 G中頂點(diǎn) v及其相關(guān)的弧。G, v, w)。 NextAdjVex(G, v, w)。 //返回第 1個(gè)鄰接點(diǎn)的位置，沒(méi)有鄰接點(diǎn)，返回 1。//v的第 1個(gè)鄰接點(diǎn) if(!p) return 1。amp。 else return 1。 V w1 w3 w2 深度優(yōu)先搜索 SG1 SG2 SG3 V w1 w3 w2 訪問(wèn)頂點(diǎn) V 。 深度優(yōu)先搜索 連通圖 void DFS(Graph G, int v) { // 從頂點(diǎn) v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visited[v] = TRUE。 // 對(duì) v的尚未訪問(wèn)的鄰接頂點(diǎn) w遞歸調(diào)用 DFS } // DFS 深度優(yōu)先搜索 連通圖 void DFS(Graph G, int v) { // 從頂點(diǎn) v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visited[v] = TRUE。 // 對(duì) v的尚未訪問(wèn)的鄰接頂點(diǎn) w遞歸調(diào)用 DFS } // DFS 深度優(yōu)先搜索 連通圖 V1 V2 V3 V4 V5 V1 V2 V8 V5 V6 V4 V2 V8 V8 V3 V1 V6 V7 V3 V8 按照完成 DFS的先后，頂點(diǎn)的次序是 : V5 , V7, V3, V6, V8, V4, V2, V1 DFS(G, V1) V1 V2 V4 V5 V3 V7 V6 V8 V7 void DFS(Graph G, int v) {//非遞歸算法 InitStack(S)。 if(!visited[u]){visit(u), visited[u]=TRUE}。 } // DFS 深度優(yōu)先搜索 連通圖 深度優(yōu)先搜索 — 非連通圖 首先將圖中每個(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èn)標(biāo)志數(shù)組初始化 for (v=0。 ，則令選一個(gè)未曾被訪問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到。 Vw6, Vw4的路徑長(zhǎng)度為 3。 ++v) visited[v] = FALSE。 ++v ) if ( !visited[v]) { // v 尚未訪問(wèn) } } // BFSTraverse … … 廣度優(yōu)先搜索 visited[v] = TRUE。 // 隊(duì)頭元素出隊(duì)并置為 u for(w=FirstAdjVex(G, u)。 EnQueue(Q, w)。 課堂練習(xí)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1