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