本文为王争老师在『极客时间』中的课程《数据结构与算法之美》的学习笔记，想要学习原文的同学购买相关课程学习。如有侵权请联系作者删除。

DFS理解

深度优先搜索(Depth First Search, DFS)可以理解为走迷宫，假设当一个人走迷宫的时候，会遇到岔路口，面对多条路选择时，可以先随便选择一条，走着走着发现如果走不通了，可以退回到上一个岔路口，然后重新选择一条，用同样的方法继续走，直到直到出口为止。这样的策略即为DFS。

DFS示意图

接下来我们将DFS应用到图的搜索中，如下图所示：

深度优先遍历示意图

DFS代码

在完成相应的java代码前，我们先解释相关函数及参数的含义：

• HashMap<Integer, LinkedList<Integer>> graph：我们使用一个HashMap来存储图，其中HashMap中的key为图的顶点，LinkedList<Integer>>为与该顶点相连的顶点；
• HashMap<Integer, Boolean> visited：我们使用一个visited用来记录顶点是否被访问，用来避免顶点被重复访问；
• visit(HashMap<Integer, LinkedList<Integer>> graph, HashMap<Integer, Boolean> visited, Integer start)：该函数为DFS的主体部分，用来遍历各个顶点。

具体java代码如下所示：

import java.util.HashMap;
import java.util.LinkedList;

public class TestDFS {

    private static void dfs(HashMap<Integer, LinkedList<Integer>> graph, HashMap<Integer, Boolean> visited){
        visit(graph, visited, 1);
        visit(graph, visited, 2);
    }


    private static void visit(HashMap<Integer, LinkedList<Integer>> graph, HashMap<Integer, Boolean> visited, Integer start){
        // 如果该顶点没有被访问，则访问该顶点
        if (!visited.containsKey(start)){
            System.out.println("当前进入节点为：" + start);
            visited.put(start, true);
            // 访问该顶点的相连顶点
            for (Integer i : graph.get(start)){
                if (!visited.containsKey(i)){
                    visit(graph,visited, i);    // 递归访问相连顶点
                }
            }
            System.out.println("当前离开节点为：" + start);
        }
    }

    public static void main(String[] args) {

        // 构造各个顶点
        LinkedList<Integer> v1 = new LinkedList<>();
        v1.add(2);
        v1.add(3);
        v1.add(4);
        LinkedList<Integer> v2 = new LinkedList<>();
        v2.add(1);
        v2.add(3);
        LinkedList<Integer> v3 = new LinkedList<>();
        v3.add(1);
        v3.add(2);
        LinkedList<Integer> v4 = new LinkedList<>();
        v4.add(1);
        v4.add(5);
        v4.add(6);
        LinkedList<Integer> v5 = new LinkedList<>();
        v5.add(4);
        LinkedList<Integer> v6 = new LinkedList<>();
        v6.add(4);
        v6.add(7);
        LinkedList<Integer> v7 = new LinkedList<>();
        v7.add(6);

        // 构造图
        HashMap<Integer, LinkedList<Integer>> graph = new HashMap<>();
        graph.put(1, v1);
        graph.put(2, v2);
        graph.put(3, v3);
        graph.put(4, v4);
        graph.put(5, v5);
        graph.put(6, v6);
        graph.put(7, v7);

        // visited数组记录被访问的节点
        HashMap<Integer, Boolean> visited = new HashMap<>();

        dfs(graph, visited);

    }
}

输出结果：

当前进入节点为：1
当前进入节点为：2
当前进入节点为：3
当前离开节点为：3
当前离开节点为：2
当前进入节点为：4
当前进入节点为：5
当前离开节点为：5
当前进入节点为：6
当前进入节点为：7
当前离开节点为：7
当前离开节点为：6
当前离开节点为：4
当前离开节点为：1

更多文章，请扫描二维码关注『算法半岛』