【技術(shù)分享】圖遍歷算法之深度優(yōu)先遍歷算法

深度優(yōu)先遍歷算法是經(jīng)典的圖論算法，它的思想是：從一條路徑的起始點(diǎn)開始追溯，直到到達(dá)路徑的最后一個頂點(diǎn)，然后回溯，繼續(xù)追溯下一條路徑，直到到達(dá)最后的頂點(diǎn)，如此往復(fù)，直到?jīng)]有路徑為止。它的遍歷過程如下：

（1）以圖中的任一頂點(diǎn)V為起始點(diǎn)，首先訪問頂點(diǎn)V，并將其標(biāo)記為已被訪問。

（2）從頂點(diǎn)V的任一個鄰接點(diǎn)出發(fā)繼續(xù)進(jìn)行深度優(yōu)先搜索，直至圖中所有和頂點(diǎn)V連通的頂點(diǎn)都已被訪問。

（3）若此時圖中仍有未被訪問的頂點(diǎn)，則選擇一個未被訪問的頂點(diǎn)作為新的出發(fā)點(diǎn)重復(fù)上述過程，直至圖中所有頂點(diǎn)都已被訪問為止。

深度優(yōu)先遍歷方法應(yīng)用了堆棧這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，這里以下圖所示的無向圖為例來介紹這個方法的遍歷過程。

步驟 1 ：假設(shè)以頂點(diǎn) A 為起點(diǎn)，將頂點(diǎn) A 壓入堆棧，如下圖所示。

步驟 2 ：彈出頂點(diǎn) A ，將頂點(diǎn) A 的鄰接點(diǎn) B 和 C 壓入堆棧，如下圖所示。

步驟 3 ：根據(jù)堆?！昂筮M(jìn)先出”的原則，彈出頂點(diǎn) C ，再將與頂點(diǎn) C 相鄰并且未被訪問過的頂點(diǎn) B 、頂點(diǎn) D 和頂點(diǎn) E 壓入堆棧，如下圖所示。

步驟 4 ：彈出頂點(diǎn) E ，將與頂點(diǎn) E 相鄰并且未被訪問過的頂點(diǎn) D 壓入堆棧，如下圖所示。

步驟 5 ：彈出頂點(diǎn) D ，將與頂點(diǎn) D 相鄰并且未被訪問過的頂點(diǎn) B 和頂點(diǎn) F 壓入堆棧，如下圖所示。

步驟 6 ：彈出頂點(diǎn) F ，將與頂點(diǎn) F 相鄰并且未被訪問過的頂點(diǎn)壓入堆棧。由于頂點(diǎn) F 的鄰接點(diǎn) D 已被訪問過，所以無需壓入堆棧，如下圖所示。

步驟 7 ：彈出頂點(diǎn) B ，將與頂點(diǎn) B 相鄰并且未被訪問過的頂點(diǎn)壓入堆棧。由于頂點(diǎn) B 的鄰接點(diǎn)都已被訪問過，所以無需壓入堆棧，如下圖所示。

步驟 8 ：將堆棧中的頂點(diǎn)依次彈出，并判斷是否已經(jīng)訪問過，直到堆棧中無頂點(diǎn)可以訪問為止，如下圖所示。

由此可知，對圖進(jìn)行深度優(yōu)先遍歷的順序為：頂點(diǎn) A 、頂點(diǎn) C 、頂點(diǎn) E 、頂點(diǎn) D 、頂點(diǎn) F 、頂點(diǎn) B 。

用Python代碼描述上述過程，則算法代碼如下：

def  dfs (graph, start):

    stack = []  #  定義堆棧

     stack.append(start) #  將起始頂點(diǎn)壓入堆棧

     visited =  set () #  定義集合

     while  stack:

        vertex = stack.pop() #  彈出棧頂元素

         if  vertex  not in  visited #  如果該頂點(diǎn)未被訪問過

            visited.add(vertex) #  將該頂點(diǎn)放入已訪問集合

             print (vertex, end  =  ' ' )  #  打印深度優(yōu)先遍歷的頂點(diǎn)

         for  w  in  graph[vertex] #  遍歷相鄰的頂點(diǎn)

             if  w  not in  visited  #  如果該頂點(diǎn)未被訪問過

                stack.append(w)  #  把頂點(diǎn)壓入堆棧