數(shù)據(jù)結(jié)構(gòu)-圖的遍歷(編輯修改稿)
2025-09-01 07:30 本頁面
【文章內(nèi)容簡介】 w2 訪問頂點 V 。 for (W W W3 ) 若 鄰接點 Wi未被訪問 ，則 從它出發(fā)進行深度優(yōu)先搜索歷。 深度優(yōu)先搜索 連通圖 深度遍歷序列： V1 V2 V4 V5 V3 V7 V6 V8 V1? V2 ?V4 ? V8 ?V5 ?V6 ?V3 ?V7 深度優(yōu)先搜索 V1 V2 V4 V5 V3 V7 V6 V8 深度優(yōu)先搜索 V1 V2 V4 V3 V7 V6 V8 深度 優(yōu)先搜索 V w1 w8 w3 w7 w6 w2 w5 w4 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷 對圖 G深度優(yōu)先搜索得到的頂點序列不是唯一的？ 搜索過程中經(jīng)過的邊和所有的頂點構(gòu)成了圖的一棵生成樹。 如何判別 V的鄰接點是否被訪問？ 為每個頂點設(shè)立一個 “ 訪問標(biāo)志 visited[w]” 。 深度優(yōu)先搜索 連通圖 void DFS(Graph G, int v) { // 從頂點 v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visited[v] = TRUE。 for(w=FirstAdjVex(G, v)。 w=0。 w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w)。 // 對 v的尚未訪問的鄰接頂點 w遞歸調(diào)用 DFS } // DFS 深度優(yōu)先搜索 連通圖 void DFS(Graph G, int v) { // 從頂點 v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visited[v] = TRUE。 for(w=FirstAdjVex(G, v)。 w=0。 w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w)。 // 對 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)。 visited[]=FALSE。//所有的頂點尚未被訪問過 Push(S, v)。 while(!Empty(S)){ Pop(S, u)。 if(!visited[u]){visit(u), visited[u]=TRUE}。 for(w=FirstAdjVex(G, u)。 w=0。 w=NextAdjVex(G,u,w)){ if (!visited[w]) Push(G, w)}//將沒訪問的鄰接點壓棧
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1