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

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

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

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

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

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

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

foreachneighborinstart.neighborsthen

ifvisited[neighbor]=falsethen

DFS(neighbor)

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