深度优先遍历（Depth First Select）

大家好，欢迎来到IT知识分享网。

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));
        }
    }
}