[資料結構]深度優先搜尋算法（Depth-First-Search，DFS）

深度優先搜尋算法的概念

　　與廣度優先搜尋算法不同，深度優先搜尋算法類似與樹的先序周遊。這種搜尋算法所遵循的搜尋政策是盡可能“深”地搜尋一個圖。它的基本思想如下：首先通路圖中某一個起始頂點v，然後由v出發，通路與v相鄰且未被通路的任一頂點w1,再通路與w1鄰接且未被通路的任一頂點w2，….重複上述過程。當不能再繼續向下通路時，依次退回到最近被通路的頂點，若它還有鄰接頂點未被通路過，則從該點開始繼續上述搜尋過程，直到圖中所有頂點均被通路過為止(還是舉相同的例子，從你開始周遊你的所有親戚，例如：先通路你的兒子，再從你的兒子繼續通路你的兒子的兒子，直到你的兒子是最後一個頂點，再回退回上一層，通路你兒子的女兒，再通路你兒子的女兒的兒子….依此類推，直到你的所有親戚都被通路過一次為止，這和廣度優先搜尋的算法差別還是很大的)。

　　

算法僞代碼

　　DFS采用的是遞歸的過程，是以這個過程需要一個遞歸工作的輔助棧，僞代碼如下：

　　

bool visited[MAX_VERTEX_NUM];//通路标記數組

void DFSTraverse(Graph G){
//對圖G進行深度優先周遊，通路函數為visit（）
    for(v=;v<G.vexnum;++i)
        visited[v]=false;//初始化所有頂點的資料，false表示未曾通路過
    for(v=;v<G.vexnum;++v)
        if(!visited[v])
            DFS(G,v);//這裡從0周遊到最後一個頂點是為了防止有極端情況出現：可能存在頂點wi無法從頂點w0周遊到，是以需要對它也調用一次DFS算法
}

void DFS(Graph G,int v){
//從頂點v出發，采用遞歸的思想，深度優先周遊圖G
    visit（v）;//通路頂點v
    visited[v]=true;//設定這個頂點為已經通路過

    for(w=FirstNeighbor(G,v);w>=;w=NextNeighbor(G,v,w))
        if(!visited[w])
            DFS(G,w);//遞歸調用查找第一個未被通路的鄰接頂點
}
           

執行個體及分析

　　

　　首先通路a，并置a為已經通路；然後通路與a鄰接且未被通路的頂點b，置b為已經通路，然後通路與b鄰接且未被通路的頂點d，置d為已經通路。此時d已經沒有未被通路過的鄰接點，這時候傳回上一個通路過的頂點b，通路與其鄰接且未被通路的頂點e，置e為已經通路……。依此類推，直到途中所有的頂點都被通路一次且僅僅被通路一次，周遊結果為abdehcfg。

DFS算法的性能分析

　　DFS算法是一個遞歸算法，需要借助一個遞歸工作棧，是以它的空間複雜度是O(|V|)。

　　周遊圖的過程實際上是對每個頂點查找其鄰接點的過程，其耗費的時間取決于所采用的存儲結構，當以鄰接矩陣表示時，查找每個頂點的臨界點所需時間為O（|V|），故總的時間複雜度為O(|V|²)。當以鄰接表表示時，查找所有頂點的鄰接點所需時間為O(|E|)，通路頂點所需時間為O(|V|),此時，總的時間複雜度為O(|V|+|E|)。

轉載于:https://www.cnblogs.com/lizhenghao126/p/11053737.html