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