一、深度優(yōu)先搜索

深度優(yōu)先搜索是一個(gè)針對(duì)圖和樹(shù)的遍歷算法。早在19世紀(jì)就被用于解決迷宮問(wèn)題。

對(duì)于下面的樹(shù)而言，DFS方法首先從根節(jié)點(diǎn)1開(kāi)始，其搜索節(jié)點(diǎn)順序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中優(yōu)先選擇左分枝）。

DFS的非遞歸實(shí)現(xiàn)方式相比于BFS應(yīng)該說(shuō)大同小異，只是把queue換成了stack而已，stack具有后進(jìn)先出LIFO(Last Input First Output)的特性，DFS的操作步驟如下：

• 1、把起始點(diǎn)放入stack；
• 2、重復(fù)下述3步驟，直到stack為空為止：
  • 從stack中訪問(wèn)棧頂?shù)狞c(diǎn)；
  • 找出與此點(diǎn)鄰接的且尚未遍歷的點(diǎn)，進(jìn)行標(biāo)記，然后全部放入stack中；
  • 如果此點(diǎn)沒(méi)有尚未遍歷的鄰接點(diǎn)，則將此點(diǎn)從stack中彈出。

二、深度優(yōu)先遍歷(非遞歸)圖文演示

下面結(jié)合一個(gè)圖(graph)的實(shí)例，說(shuō)明DFS的工作過(guò)程和原理：

• 1、將起始節(jié)點(diǎn)1放入棧stack中，標(biāo)記為已遍歷。

• 2、從stack中訪問(wèn)棧頂?shù)墓?jié)點(diǎn)1，找出與節(jié)點(diǎn)1鄰接的節(jié)點(diǎn)，有2、9兩個(gè)節(jié)點(diǎn)，我們可以選擇其中任何一個(gè)，選擇規(guī)則可以人為設(shè)定，這里假設(shè)按照節(jié)點(diǎn)數(shù)字順序由小到大選擇，選中的是2，標(biāo)記為已遍歷，然后放入stack中。

• 3、從stack中取出棧頂?shù)墓?jié)點(diǎn)2，找出與節(jié)點(diǎn)2鄰接的節(jié)點(diǎn)，有1、3、5三個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)1已遍歷過(guò)，排除；3、5中按照預(yù)定的規(guī)則選中的是3，標(biāo)記為已遍歷，然后放入stack中。

• 4、從stack中取出棧頂?shù)墓?jié)點(diǎn)3，找出與節(jié)點(diǎn)3鄰接的節(jié)點(diǎn)，有2、4兩個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)2已遍歷過(guò)，排除；選中的是節(jié)點(diǎn)4，標(biāo)記為已遍歷，然后放入stack中。

• 5、從stack中取出棧頂?shù)墓?jié)點(diǎn)4，找出與節(jié)點(diǎn)4鄰接的節(jié)點(diǎn)，有3、5、6三個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)3已遍歷過(guò)，排除；選中的是節(jié)點(diǎn)5，標(biāo)記為已遍歷，然后放入stack中。

• 6、從stack中取出棧頂?shù)墓?jié)點(diǎn)5，找出與節(jié)點(diǎn)5鄰接的節(jié)點(diǎn)，有2、4兩個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)2、4都已遍歷過(guò)，因此節(jié)點(diǎn)5沒(méi)有尚未遍歷的鄰接點(diǎn)，則將此點(diǎn)從stack中彈出。

• 7、當(dāng)前stack棧頂?shù)墓?jié)點(diǎn)是4，找出與節(jié)點(diǎn)4鄰接的節(jié)點(diǎn)，有3、5、6三個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)3、5都已遍歷過(guò)，排除；選中的是節(jié)點(diǎn)6，標(biāo)記為已遍歷，然后放入stack中。

• 8、當(dāng)前stack棧頂?shù)墓?jié)點(diǎn)是6，找出與節(jié)點(diǎn)6鄰接的節(jié)點(diǎn)，有4、7、8三個(gè)節(jié)點(diǎn)，4已遍歷，按照規(guī)則選中的是7，標(biāo)記為已遍歷，然后放入stack中。

• 9、當(dāng)前stack棧頂?shù)墓?jié)點(diǎn)是7，找出與節(jié)點(diǎn)7鄰接的節(jié)點(diǎn)，只有節(jié)點(diǎn)6，已遍歷過(guò)，因此沒(méi)有尚未遍歷的鄰接點(diǎn)，將節(jié)點(diǎn)7從stack中彈出。

• 10、當(dāng)前stack棧頂?shù)墓?jié)點(diǎn)是6，找出與節(jié)點(diǎn)6鄰接的節(jié)點(diǎn)，有節(jié)點(diǎn)7、8，7已遍歷過(guò)，因此將節(jié)點(diǎn)8放入stack中。

• 11、當(dāng)前stack棧頂?shù)墓?jié)點(diǎn)是8，找出與節(jié)點(diǎn)8鄰接的節(jié)點(diǎn)，有節(jié)點(diǎn)1、6、9，1、6已遍歷過(guò)，因此將節(jié)點(diǎn)9放入stack中。

• 12、當(dāng)前stack棧頂?shù)墓?jié)點(diǎn)是9，沒(méi)有尚未遍歷的鄰接點(diǎn)，將節(jié)點(diǎn)9彈出，依次類(lèi)推，棧中剩余節(jié)點(diǎn)8、6、4、3、2、1都沒(méi)有尚未遍歷的鄰接點(diǎn)，都將彈出，最后棧為空。

• 13、DFS遍歷完成。

三、鄰接表進(jìn)行深度優(yōu)先遍歷

3.1 構(gòu)建數(shù)據(jù)結(jié)構(gòu)

public class Graph {

    //頂點(diǎn)個(gè)數(shù)
    private int V;

    //邊的條數(shù)
    private int E;

    //領(lǐng)接表的底層存儲(chǔ)結(jié)構(gòu)
    private TreeSet<Integer>[] adj;

}

3.2 通過(guò)該結(jié)構(gòu)定義，構(gòu)造一個(gè)圖(無(wú)向圖）

/**
 * @Author: huangyibo
 * @Date: 2022/3/28 1:02
 * @Description: 領(lǐng)接表, 目前只支持無(wú)向無(wú)權(quán)圖
 */

public class Graph {

    //頂點(diǎn)個(gè)數(shù)
    private int V;

    //邊的條數(shù)
    private int E;

    //領(lǐng)接表的底層存儲(chǔ)結(jié)構(gòu)
    private TreeSet<Integer>[] adj;

    public Graph(String filename){
        File file = new File(filename);
        try {
            Scanner scanner = new Scanner(file);
            V = scanner.nextInt();
            if(V < 0){
                throw new IllegalArgumentException("V must be non-negative");
            }
            adj = new TreeSet[V];
            //初始化領(lǐng)接表
            for (int i = 0; i < V; i++) {
                adj[i] = new TreeSet<>();
            }

            E = scanner.nextInt();
            if(E < 0){
                throw new IllegalArgumentException("E must be non-negative");
            }
            for (int i = 0; i < E; i++) {
                int a = scanner.nextInt();
                //校驗(yàn)頂點(diǎn)a是否合法
                validateVertex(a);

                int b = scanner.nextInt();
                //校驗(yàn)頂點(diǎn)b是否合法
                validateVertex(b);

                //校驗(yàn)是否是自環(huán)邊
                if(a == b){
                    throw new IllegalArgumentException("Self Loop is Detected!");
                }
                //校驗(yàn)是否是平行邊
                if(adj[a].contains(b)){
                    throw new IllegalArgumentException("Parallel Edges are Detected!");
                }
                adj[a].add(b);
                adj[b].add(a);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    /**
     * 校驗(yàn)頂點(diǎn)是否合法
     * @param v
     */
    private void validateVertex(int v){
        if(v < 0 || v >= V){
            throw new IllegalArgumentException("vertex " + v + " is invalid");
        }
    }

    /**
     * 獲取頂點(diǎn)個(gè)數(shù)
     * @return
     */
    public int V(){
        return V;
    }

    /**
     * 獲取邊的條數(shù)
     * @return
     */
    public int E(){
        return E;
    }

    /**
     * 圖中是否存在v到w的邊
     * @param v
     * @param w
     * @return
     */
    public boolean hasEdge(int v, int w){
        //校驗(yàn)頂點(diǎn)v是否合法
        validateVertex(v);
        //校驗(yàn)頂點(diǎn)w是否合法
        validateVertex(w);
        return adj[v].contains(w);
    }

    /**
     * 返回和v相鄰的頂點(diǎn)
     * @param v
     * @return
     */
    public Iterable<Integer> adj(int v){
        //校驗(yàn)頂點(diǎn)v是否合法
        validateVertex(v);
        return adj[v];
    }

    /**
     * 返回頂點(diǎn)v的度
     * 頂點(diǎn)v的度（Degree）是指在圖中與v相關(guān)聯(lián)的邊的條數(shù)
     * @param v
     * @return
     */
    public int degree(int v){
        //校驗(yàn)頂點(diǎn)v是否合法
        validateVertex(v);
        return adj[v].size();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d\n", V, E));
        for (int v = 0; v < V; v++) {
            sb.append(String.format("%d : ", v));
            for (Integer w : adj[v]) {
                sb.append(String.format("%d ", w));
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}

3.3 鄰接表的深度優(yōu)先算法(非遞歸)

/**
 * @Author: huangyibo
 * @Date: 2022/3/28 1:02
 * @Description: 圖的深度優(yōu)先遍歷, 非遞歸方式
 */

public class GraphDFS {

    private Graph G;

    /**
     * 圖的頂點(diǎn)是否已經(jīng)被遍歷過(guò)
     */
    private boolean[] visited;

    //圖的深度優(yōu)先遍歷結(jié)果
    private List<Integer> order = new ArrayList<>();

    public GraphDFS(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        //循環(huán)所有頂點(diǎn), 防止一個(gè)圖出現(xiàn)多個(gè)連通圖(連通分量)的情況
        for (int v = 0; v < G.V(); v++) {
            if(!visited[v]){
                dfs(v);
            }
        }
    }

    /**
     * 圖的深度優(yōu)先遍歷, 非遞歸方式
     * @param source
     */
    private void dfs(int source) {
        Stack<Integer> stack = new Stack<>();
        //將源結(jié)點(diǎn)壓入棧頂
        stack.push(source);
        //標(biāo)記為已訪問(wèn)
        visited[source] = true;
        //如果棧不為空
        while(!stack.isEmpty()){
            Integer v = stack.pop();
            //當(dāng)前出棧頂點(diǎn)添加到圖的深度優(yōu)先遍歷結(jié)果集
            order.add(v);
            //遍歷頂點(diǎn)V的相鄰頂點(diǎn)
            for (Integer w : G.adj((v))) {
                //如果沒(méi)有遍歷過(guò)
                if(!visited[w]){
                    //頂點(diǎn)w壓入棧頂
                    stack.push(w);
                    //標(biāo)記w為已訪問(wèn)
                    visited[w] = true;
                }
            }
        }
    }

    /**
     * 圖的深度優(yōu)先遍歷結(jié)果集
     * @return
     */
    public List<Integer> order(){
        return order;
    }

    public static void main(String[] args) {
        Graph graph = new Graph("src/main/resources/g1.txt");
        GraphDFS graphDFS = new GraphDFS(graph);
        System.out.println(graphDFS.order());
    }
}

g1.txt

7 6
0 1
0 2
1 3
1 4
2 3
2 6

參考：
https://blog.csdn.net/saltriver/article/details/54429068