图的深度优先遍历（Depth First Search）_深度优先算法流程图

14.2.1 深度优先遍历(Depth First Search)

1. 深度优先遍历，从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先遍历的策略就是首先访问第一个邻接节点，然后再以这个被访问的邻接节点作为初始节点，反问他的第一个邻接节点，可以这样理解： 每次都在访问完当前节点后首先访问当前节点的第一个邻接节点。
2. 我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个节点的所有邻接节点进行横向访问
3. 显然深度有限搜索时一个递归的过程

深度优先遍历算法步骤

1. 访问初始节点V，并标记节点V已访问
2. 查找节点V的第一个邻接节点W
3. 若W存在，则继续执行 4，如果W不存在，则返回第一步，将从V的下一个节点继续
4. 若W未被访问，对W进行深度优先遍历递归（即把W当做另一个V，然后进行步骤123)
5. 查找节点V的W邻接节点的下一个了邻接节点，转到步骤 3

拿上图当个例子，我们是按照A，B，C，D，E这个顺序来创建的数组，所以，我们需要按照这个顺序来进行遍历。

首先看A，他的下一个节点是B，我们发现存在B节点，且未被访问过以及与A存在直接连接关系，因此我们往下走，到B。

我们继续按照顺序来，B节点的下一个是C，我们发现C存在，它没有被访问过，且C与B存在直接连接关系，因此，我们往下走，来到C

我们来到C节点，继续按照顺序来，下一个是D，我们发现C与D节点没有直接连接，因此无法从C到达D节点，因此我们需要返回到B，然后，看看B能不能到达D，我们发现，D存在，未被访问过，而且与B存在直接连接关系，所以我们往下走，来到D。

D接下来是E，虽然E存在且没有被访问过，但是E与D没有直接连接关系，因此我们返回上一层（从哪里来回到那里去），回到B，发现B与E存在直接连接，因此我们向下走，到达E，发现没有需要到达的节点了，完成遍历。

A - B - C (= B) - D (= B) - E // - 表示到达的意思，而 = 表示返回上一层的意思，括号里的是帮助理解的，而最终结果是（A - B - C - D -E）

package graph;

import java.util.ArrayList;
import java.util.Arrays;

public class Graph {

    private ArrayList<String> vertexList; // 存储定点集合
    private  int[][] edges; // 存储图对应的邻接矩阵
    private int numOfEdges; // 表示边的数目
    // 定义一个数组 boolean[] ，记录某个节点是否被访问
    private  boolean[] isVisited;

    public static void main(String[] args) {
        int n = 5; // 节点的个数
        String[] vertexs = {"A","B","C","D","E"};
        // 创建图对象
        Graph graph = new Graph(n);
        // 循环添加顶点
        for (String vertex : vertexs){
            graph.insertVertex(vertex);
        }
        // 手动添加边
        // A - B / A - C / B - C / B - D/ B - E
        graph.insertEdge(0,1,1); // A - B
        graph.insertEdge(0,2,1); // A - C
        graph.insertEdge(1,2,1); // B - C
        graph.insertEdge(1,3,1); // B - D
        graph.insertEdge(1,4,1); // B - E

        // 显示邻接矩阵
        graph.showGraph();
        // 深度优先遍历
        System.out.println("Depth First Search 深度优先遍历");
        graph.dfs();

    }

    // 构造器
    private Graph(int n){// 这个n是指有多少个节点或顶点
        // 初始化矩阵和vertexList
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0; // 因为我们不知道边有多少条，所以我们初始化为零
        isVisited = new boolean[n];
    }

    // 先写一个方法，得到第一个邻接节点的下标
    /**
     *
     * @param index
     * @return  如果存在就返回对应的下标，否则返回-1
     */
    public int getFirstNeighbor(int index){
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0){ // 大于零，表示两个节点存在直接连接关系
                return i;
            }
        }
        return -1;
    }
    // 根据前一个邻接节点的下标来获取下一个邻接节点
    // 就是当V2没有能够到达未遍历的节点的情况，执行该方法，例如 ：v1就是B节点下标，v2就是C节点下标，与c直接连接的都被访问过了，所以，我们要找C以外的节点，因此是（C）v2+1在（B）v1的周围找
    public int getNextNeighbor(int v1, int v2){
        for (int j = v2 + 1; j < vertexList.size(); j++){
            if (edges[v1][j] > 0){
                return j;
            }
        }
        return -1;
    }

    // 深度优先遍历算法

    /**
     *
     * @param isVisited 用来判断是否被访问
     * @param i 访问节点下标，第一次就是0
     */
    public void dfs(boolean[] isVisited, int i){
        // 首先我们访问该节点。输出
        System.out.println(getValueByIndex(i) + "->");
        // 将这个节点设置为已经访问
        isVisited[i] = true;
        // 查找节点i的第一个邻接节点
        int w = getFirstNeighbor(i);
        while(w != -1){ // 说明存在该节点
            if (!isVisited[w]){ //  说明没有被访问过
                    dfs(isVisited, w);
            }
            // 如果 W这个节点被访问过了，我们就该查找下一个的下一个
            // i 是当前节点，而w是当前节点的下一个节点
            w = getNextNeighbor(i, w);
        }
    }
    // dfs 进行重载，遍历我们所有的节点，并进行dfs
    public void dfs(){
        // 遍历所有的节点，进行dfs[回溯]
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }
    
    // 插入节点
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }
    // 添加边

    /**
     *
     * @param v1    表示第一个点的对应的下标，即是第几个顶点
     * @param v2    表示第二个点的对应的下标，即是第几个顶点
     * @param weight    认为规定 1 是表示两个顶点有直接关联，0 表示没有直接关联
     */
    public void insertEdge(int v1,int v2, int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight; // 因为我们这个图是无向图，所以反过来也要赋值
        numOfEdges++;
    }

    // 图中常用的方法
    // 返回节点的个数
    public int getNumOfVertex(){
        return vertexList.size();
    }
    // 得到边的个数
    public int getNumOfEdges(){
        return numOfEdges;
    }
    // 返回节点i（下标）对应的数据
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }
    // 返回v1和v2的权值
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    // 显示图对应的矩阵
    public void showGraph(){
        for (int[] link : edges){
            System.out.println(Arrays.toString(link));
        }
    }
}

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148