算法設(shè)計(jì)與分析 課件 第六章 回溯法6.1.1 DFS思想

計(jì)算機(jī)算法設(shè)計(jì)與分析第6章回溯法6.1.1深度優(yōu)先搜索策略深度優(yōu)先搜索（Depth-FirstSearch，DFS）策略是一種常用的圖遍歷搜索算法，用于在圖或樹結(jié)構(gòu)中搜索特定的目標(biāo)?；舅枷胧菑钠鹗冀Y(jié)點(diǎn)開始，沿著一條路徑一直向下搜索，直到無法繼續(xù)下去，然后回溯到前一個(gè)結(jié)點(diǎn)，繼續(xù)搜索其他路徑，直到找到目標(biāo)結(jié)點(diǎn)或者嘗試了所有可能后確定最優(yōu)解或確定沒有解。深度優(yōu)先實(shí)例ABCDEFABCDEF給定圖G=(V，E)，創(chuàng)建一個(gè)棧，用于存儲(chǔ)待訪問的結(jié)點(diǎn)；創(chuàng)建一個(gè)數(shù)組，用于存儲(chǔ)每個(gè)結(jié)點(diǎn)訪問狀態(tài)。深度優(yōu)先搜索策略的基本思想為：（1）初始化：任選一個(gè)結(jié)點(diǎn)v作為起始結(jié)點(diǎn)，將起始結(jié)點(diǎn)放入棧中。（2）當(dāng)棧不為空時(shí)，執(zhí)行以下步驟：①出棧-->當(dāng)前結(jié)點(diǎn)，訪問當(dāng)前結(jié)點(diǎn)其標(biāo)記為已訪問。②檢查是否為目標(biāo)結(jié)點(diǎn)，若是，則搜索結(jié)束，否則繼續(xù)。③獲取當(dāng)前結(jié)點(diǎn)的所有鄰居結(jié)點(diǎn)。④對(duì)于每個(gè)鄰居結(jié)點(diǎn)，如果它未被訪問，則將其放入棧中，并將其標(biāo)記為已訪問。（3）重復(fù)步驟（2），直到找到目標(biāo)結(jié)點(diǎn)提前結(jié)束，或者棧為空且沒找到目標(biāo)結(jié)點(diǎn)而搜索失敗結(jié)束。6.1.1深度優(yōu)先搜索策略DFS的非遞歸偽代碼DFS(start):beginstack.push(start)//將起始結(jié)點(diǎn)加入棧中visited[start]

true//標(biāo)記相鄰結(jié)點(diǎn)為已訪問whilestackisnotemptydocurrent

stack.pop()//彈出棧頂元素,并用current記錄 printcurrent//處理結(jié)點(diǎn)ifcurrent=objectthenreturnendif//若為目標(biāo)結(jié)點(diǎn)，搜索結(jié)束foreachneighborincurrent.neighborsdo//遍歷當(dāng)前結(jié)點(diǎn)的相鄰結(jié)點(diǎn)ifvisited[current]=falsethen//如果相鄰結(jié)點(diǎn)未被訪問過stack.push(neighbor)//將相鄰結(jié)點(diǎn)加入棧中 isited[neighbor]

true//標(biāo)記相鄰結(jié)點(diǎn)為已訪問

endifendforendwhileend初始化，入棧，置訪問標(biāo)記棧非空循環(huán)出棧，訪問并判斷是否為目標(biāo)對(duì)所有鄰接點(diǎn)，未訪問的入棧，并置訪問標(biāo)記DFS的遞歸偽代碼DFS(start):beginvisited[start]

trueprintstartifstart=objectthen//若為目標(biāo)結(jié)點(diǎn)，搜索結(jié)束returnendif

foreachneighborinstart.neighborsthen

ifvisited[neighbor]=falsethen

DFS(neighbor)

endifendforend初始化，入棧，置訪問標(biāo)記對(duì)所有鄰接點(diǎn)若未訪問，則作為新出發(fā)點(diǎn)遞歸時(shí)間復(fù)雜度采用鄰接表存儲(chǔ)時(shí)，深度優(yōu)先搜索的時(shí)間復(fù)雜度為O(|V|+|E|)，其中|V|