DFS（Depth First Search）深度优先搜索，为每个顶点设立一个“访问标志”。首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行遍历。

若当前访问的顶点的邻接顶点有未被访问的，则任选一个访问之。反之，退回到最近访问过的顶点；直到与起始顶点相通的全部顶点都访问完毕；

在使用DFS时,可能有两种情景,一种是使用邻接矩阵,一种是使用邻接链表;

使用邻接矩阵的表示形式,其实只需要一半的空间就可以了,因为edges[i][j]和edges[j][i]的值是相同的(这里只考虑无向图)

情景一:

给出了一个图,图中有九个顶点,分别为A~I,那么用深度遍历的方法,得到A到I的一条路径;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
   private int number = 9;  //其实是个9*9的数组;
   private boolean[] flag;
   private String[] vertexs = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};

//联通图,如果为1,表示二者相连,为0表示不相连;
   private int[][] edges = {
           {0, 1, 0, 0, 0, 1, 1, 0, 0},
           {1, 0, 1, 0, 0, 0, 1, 0, 1},
           {0, 1, 0, 1, 0, 0, 0, 0, 1},
           {0, 0, 1, 0, 1, 0, 1, 1, 1},
           {0, 0, 0, 1, 0, 1, 0, 1, 0},
           {1, 0, 0, 0, 1, 0, 1, 0, 0},
           {0, 1, 0, 1, 0, 1, 0, 1, 0},
           {0, 0, 0, 1, 1, 0, 1, 0, 0},
           {0, 1, 1, 1, 0, 0, 0, 0, 0}
   };

   //DFS深度优先递归
   void DFSTraverse() {
       flag = new boolean[number];  //标记数组,用来标记是否有
       for (int i = 0; i < number; i++) {
           if (flag[i] == false) {// 当前顶点没有被访问
               DFS(i);
           }
       }
   }

   void DFS(int i) {
       flag[i] = true;// 第i个顶点被访问
       System.out.print(vertexs[i] + " ");
       for (int j = 0; j < number; j++) {
           if (flag[j] == false && edges[i][j] == 1) {
               DFS(j);
           }
       }
   }

结果:

A B C D E F G H I

分析:通过连通图矩阵分析可知,顺序是:A->B->C->D->E->F->G->H 到了H之后走不下去了,回溯,G,F,E,D,到D的时候才有了直指I的路径;

情景二:走迷宫问题;

给出一个二维数组,用来表示一个迷宫,如果dp[i][j]=1则表示前是一面墙,如果是0,则表示是一条路,那么求从左上角到右下角的最短路径;

解决思路依然是使用深度优先遍历,但是要注意的是,现在的节点数不是在一维的,而是二维的,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
static int[][] arr = {
        {0, 1, 1, 1, 1},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 1, 0},
        {1, 1, 1, 0, 0},
};

static boolean[][] dp = new boolean[arr.length][arr[0].length]; //默认全是false;如果访问过标记为true;

static int min = Integer.MAX_VALUE;

static ArrayList<Pair> path = new ArrayList<Pair>();
static ArrayList<Pair> path0 = new ArrayList<Pair>();

//如果你想要找路径的的长度,并且把路径打印出来,那么就使用深度优先;
static void dfs(int i, int j, int count) {
    path.add(new Pair(i, j));
    //深度优先
    dp[i][j] = true;//先将自己设置为true;然后再找四周的;
    count++;
    if (i == arr.length - 1 && j == arr[0].length - 1) {
        min = Math.min(min, count);
        path0.clear();
        path0.addAll(path);
        return;
    }

    //上
    if (i > 0 && !dp[i - 1][j] && arr[i - 1][j] == 0) {
        dfs(i - 1, j, count);
        path.remove(path.size() - 1);
        dp[i - 1][j] = false;
    }

    //下
    if (i + 1 < arr.length && !dp[i + 1][j] && arr[i + 1][j] == 0) {
        dfs(i + 1, j, count);
        path.remove(path.size() - 1);
        dp[i + 1][j] = false;
    }

    //左
    if (j > 0 && !dp[i][j - 1] && arr[i][j - 1] == 0) {
        dfs(i, j - 1, count);
        path.remove(path.size() - 1);
        dp[i][j - 1] = false;
    }

    //右
    if (j + 1 < arr[0].length && !dp[i][j + 1] && arr[i][j + 1] == 0) {
        dfs(i, j + 1, count);
        path.remove(path.size() - 1);
        dp[i][j + 1] = false;
    }
}


static class Pair {
    int i;
    int j;

    public Pair(int i, int j) {
        this.i = i;
        this.j = j;
    }

    @Override
    public String toString() {
        return i + "<>" + j;
    }
}

public static void main(String[] args) {
    dfs(0, 0, 0);
    System.out.println(min);
}

要注意的是:这里使用了大量的static的全局变量path0,还有一个临时的全局变量path,临时的path是每次走时的路径,如果走到了终点,就和之前的最短路径比较,如果本次路径更短,那么就将path0设置为本次路径;

还有在遍历了一个位置之后,要把其标志位还原为false,这是因为你按照某个方向进行深度遍历下去,发现此路不通,或者不是最优解,那么你就需要按照原路回退,回退的意思就是把之前访问的flag设置为flase;同时临时路径path也要将本次访问的节点删除;