1. 圖的遍歷

在理解DFS算法之前，我們首先需要對什么是遍歷進(jìn)行了解，遍歷的概念就是：從某一個點(diǎn)出發(fā)（一般是首或尾），依次將數(shù)據(jù)結(jié)構(gòu)中的每一個數(shù)據(jù)訪問且只訪問一遍。

2. DFS簡介

DFS（Depth-First-Search，深度優(yōu)先搜索）算法的具體做法是：從某個點(diǎn)一直往深處走，走到不能往下走之后，就回退到上一步，直到找到解或把所有點(diǎn)走完。

在實(shí)現(xiàn)這一個依次的訪問順序時，操作動作存儲與數(shù)據(jù)結(jié)構(gòu)（棧）的思想及其相似，同時也由于棧的性質(zhì)，我們可以通過遞歸來簡化棧的創(chuàng)建，因此DFS算法的兩種做法分別時利用棧或者遞歸實(shí)現(xiàn)。

算法步驟（遞歸或棧實(shí)現(xiàn)）

a)訪問指定起始地點(diǎn)。

b)若當(dāng)前訪問頂點(diǎn)的鄰接頂點(diǎn)有未被訪問的頂點(diǎn)，就任選一個訪問。如果沒有就回退到最近訪問的頂點(diǎn)，直到與起始頂點(diǎn)相通的所有點(diǎn)被遍歷完。

c)若途中還有頂點(diǎn)未被訪問，則再選一個點(diǎn)作為起始頂點(diǎn)，并重復(fù)前面的步驟。

3. 圖的DFS

我們直接以案例進(jìn)行講解，就本圖而言，其訪問順序可以是（不唯一）：1-2-4-5-3

首先從1開始，1結(jié)點(diǎn)處可以訪問2，3兩個結(jié)點(diǎn)，那么按照我們自定義的優(yōu)先順序線訪問2結(jié)點(diǎn)，此時，2結(jié)點(diǎn)有4，5兩個結(jié)點(diǎn)訪問，依舊按次序訪問呢4結(jié)點(diǎn)，4結(jié)點(diǎn)可以訪問5結(jié)點(diǎn)，5結(jié)點(diǎn)無法繼續(xù)向下訪問故結(jié)束訪問，并回退4結(jié)點(diǎn)，4結(jié)點(diǎn)無法沒有其他分支且自己已被訪問故又退回2結(jié)點(diǎn)，2結(jié)點(diǎn)的兩個分支4，5結(jié)點(diǎn)均已被訪問，故再退回1結(jié)點(diǎn)，此時只有3結(jié)點(diǎn)未被訪問，訪問3結(jié)點(diǎn)，最終得到次序：1-2-4-5-3

4.相關(guān)代碼

DFS算法的相關(guān)模板如下：

void dfs()//參數(shù)用來表示狀態(tài)  
{  
    if(到達(dá)終點(diǎn)狀態(tài))  
    {  
        ...//根據(jù)需求添加  
        return;  
    }  
    if(越界或者是不合法狀態(tài))  
        return;  
    if(特殊狀態(tài))//剪枝，去除一些不需要訪問的場景，不一定i俺家
        return ;
    for(擴(kuò)展方式)  
    {  
        if(擴(kuò)展方式所達(dá)到狀態(tài)合法)  
        {  
            修改操作;//根據(jù)題意來添加  
            標(biāo)記；  
            dfs（）；  
            (還原標(biāo)記)；  
            //是否還原標(biāo)記根據(jù)題意  
            //如果加上（還原標(biāo)記）就是 回溯法  
        }  
 
    }  
}

對于圖論而言（代碼節(jié)選，僅做參考，最主要還請記憶上面的模板那代碼）：

//從pos點(diǎn)開始，深度遍歷無向圖
//pos表示當(dāng)前結(jié)點(diǎn)，G表示圖，visited[]數(shù)組用來表示該節(jié)點(diǎn)是否已經(jīng)訪問
void DFS(int pos,pGraph G,int visited[30]){
    node p;
    printf("%d ",pos);//打印深度遍歷的點(diǎn)
    visited[pos]=1;//標(biāo)記為以訪問過
    p=G->vertice[pos].firstarc;//將當(dāng)前點(diǎn)的第一個指針賦值給p
    //是否存在鄰接點(diǎn)
    while(p!=NULL) {
        //判斷該鄰接點(diǎn)是否被遍歷過
        if(visited[p->adjvex]==0){
            DFS(p->adjvex,G,visited);
        }
        p=p->next;//后移一位，為之后是否有鄰接點(diǎn)做準(zhǔn)備
    }
}

5. 實(shí)際應(yīng)用

在最早期的搜索算法，如HTML的搜索，是基于并利用DFS的，現(xiàn)在諸如一些拓?fù)鋱D，網(wǎng)絡(luò)等準(zhǔn)確且數(shù)據(jù)量不大的定位運(yùn)算等依舊應(yīng)用非常多的DFS算法，同時DFS算法也是算法競賽入門級別的標(biāo)準(zhǔn)算法，公司的入職考試算法等。