vlambda博客
学习文章列表

在讲深度优先遍历之前，先来回顾一下图这种数据结构。

1. 是什么？

图，也是一种数据结构，其节点可以具有零个或者多个相邻元素，两个节点之间的连接称为边，节点也称为顶点，图表示的是多对多的关系。

2. 图的常用概念：

• 顶点：就是节点，上图中的ABCDEFGH都是顶点；

• 边：每个节点之间的连线叫做边；

• 路径：从一个顶点到另一个顶点的通路，比如从A到G的路径有：A ---> B ---> G和A ---> F ---> G；

• 无向图：上面的就是无向图，就是节点之间的连线是没有方向的，A可以到B，B也可以到A；

• 有向图：节点之间的连线是有方向的；

• 带权图：边具有权值的图叫做带权图，也叫网。

3. 图的表示方式：

• 邻接矩阵：也就是用二维数组表示。假如总共有n个顶点，那么就需要一个 n*n 的二维数组。两个顶点之间如果是连通的就用1表示，反之用0表示。这种方式的缺点就是，假如n很大，但是相互连通的顶点却很少，即一个二维数组中真正有用的数据特别少，那么就会造成空间的浪费；

• 邻接表：邻接表只关心存在的边，即只关注能相互连通的顶点，因此没有空间浪费。邻接表用数组和链表组合实现。数组下标表示顶点编号，数组中存的值是一条链表，链表中的数据就是数组该下标对应顶点连通的顶点编号。比如顶点0可以和顶点2，3，6连通，那么数组第一个位置存放的就是2 ---> 3 ---> 6这条链表。

4. 无向图的创建(邻接矩阵)：

开篇所示的无向图，怎么用邻接矩阵代码实现呢？思路如下：

• 创建一个List<String>，用来保存各个顶点；

• 创建一个二维数组，用来保存顶点之间的边，顶点与顶点之间有连线的用1表示，反之用0。所以这个二位数组就是：

  A  B  C  D  E  F  G  H
A[0, 1, 0, 0, 0, 1, 0, 1]
B[1, 0, 1, 0, 0, 0, 1, 0]
C[0, 1, 0, 1, 1, 0, 0, 0]
D[0, 0, 1, 0, 0, 0, 0, 1]
E[0, 0, 1, 0, 0, 0, 1, 0]
F[1, 0, 0, 0, 0, 0, 1, 0]
G[0, 1, 0, 0, 1, 1, 0, 0]
H[1, 0, 0, 1, 0, 0, 0, 0]

• 所以，创建图也就是创建这个邻接矩阵，代码如下：

public class UnDirectionGraph {

    private List<String> vertexList; // 存放顶点
    private int[][] edges; // 邻接矩阵，存放图的边
    private boolean[] isVisited; // 顶点是否被访问

    /**
     * 构造器
     * @param vertexCount 顶点的个数
     */
    public UnDirectionGraph(int vertexCount, List<String> vertex){
        this.vertexList = vertex;
        this.edges = new int[vertexCount][vertexCount];
        this.isVisited = new boolean[vertexCount];
    }

    /**
     * 构建无向图
     * @param vertex1 顶点1
     * @param vertex2 顶点2
     * @param isConnected 顶点1和顶点2是否连通，0:未连通 1:已连通
     */
    public void buildGraph(String vertex1, String vertex2, int isConnected){
        edges[vertexList.indexOf(vertex1)][vertexList.indexOf(vertex2)] = isConnected;
        edges[vertexList.indexOf(vertex2)][vertexList.indexOf(vertex1)] = isConnected;
    }

   /**
     * 打印邻接矩阵
     */
    public void printGraph(){
        for(int[] arr : edges){
            System.out.println(Arrays.toString(arr));
        }
    }
}

测试代码：

public static void main(String[] args) {
        int vertexCount = 8;
        List<String> vertexList = new ArrayList<>();
        vertexList.add("A");
        vertexList.add("B");
        vertexList.add("C");
        vertexList.add("D");
        vertexList.add("E");
        vertexList.add("F");
        vertexList.add("G");
        vertexList.add("H");

        UnDirectionGraph graph = new UnDirectionGraph(vertexCount, vertexList);
        graph.buildGraph("A", "B", 1);
        graph.buildGraph("A", "H", 1);
        graph.buildGraph("A", "F", 1);
        graph.buildGraph("B", "G", 1);
        graph.buildGraph("B", "C", 1);
        graph.buildGraph("C", "D", 1);
        graph.buildGraph("C", "E", 1);
        graph.buildGraph("D", "H", 1);
        graph.buildGraph("E", "G", 1);
        graph.buildGraph("F", "G", 1);
        graph.printGraph();
    }

5. 无向图的遍历：

(1). 遍历分类：

图的遍历分为两种：

• 深度优先：depth first search，简称DFS。先从初始顶点出发，访问第一个邻接顶点，然后再以这个被访问到的邻接顶点作为初始顶点，访问它的第一个邻接顶点。可以理解为一条路走到底，而不是把一个顶点的所有邻接顶点先进行横向访问，而是纵向优先，所以也叫深度优先。

• 广度优先：broad first search，简称BFS。类似于二叉树的层序遍历，具体的本文不做介绍。

(2). 深度优先算法步骤：

以开篇中的图为例：

• 访问A，并将A标记为已访问；

• 找到A的第一个未被访问邻接顶点，怎么找？看矩阵：

  A  B  C  D  E  F  G  H
A[0, 1, 0, 0, 0, 1, 0, 1]

第一个1对应的是B，所以A的第一个邻接顶点是B，所以第二个遍历出来的是B，并且标记B为已访问；

• 找到B的第一个未被访问的邻接顶点，方式一样，看矩阵：

  A  B  C  D  E  F  G  H
B[1, 0, 1, 0, 0, 0, 1, 0]

找到的是C，所以第三个遍历出来的是C，并且标记C为已访问；

• 找到C的第一个未被访问的邻接顶点，是D，打印D，并标记为已访问；

• 找到D的第一个未被访问的邻接顶点，是H，打印H，并标记为已访问；

• 找到H的第一个未被访问的邻接顶点，发现没有，也就是这条路走到底了，那么开始往回走；

• 回到D，没有未被访问的，再往回，直到回到C；

• 回到C，找到C的第一个邻接顶点D的后一个邻接顶点：

  A  B  C  D  E  F  G  H
C[0, 1, 0, 1, 1, 0, 0, 0]

说白了就是这一行的D后面的那个1，就是E，打印E，并标记为已访问；

• 找到E的第一个未被访问的邻接顶点G，打印G；

• 找到G的第一个未被访问的邻接顶点F，打印F；

• 到了F，发现F的所有邻接顶点都被访问过了，往回走，发现所有顶点的邻接顶点都被访问过了，就遍历完了，所以遍历的结果就是：

A --- B --- C --- D --- H --- E --- G --- F

其实概括地说就是：从第一个顶点开始，每次都选择该顶点的第一个邻接顶点往下走，走到死胡同的时候，就往回走，回到最后一次有岔路的地方，换另一条岔路走，又走到死胡同继续往回走……

(3). 深度优先遍历代码：

首先得在UnDirectionGraph类中加一个变量，用来表示该顶点有没有被访问过，如下：

private boolean[] isVisited; // 顶点是否被访问

然后在UnDirectionGraph中再增加如下方法：

   /**
     * 查找顶点vertex的第一个邻接顶点
     * @param vertex
     */
    public int findFstNeighbor(String vertex){
        // 拿到vertex的索引
        int vertexIndex = vertexList.indexOf(vertex);
        // 遍历二维数组的第 vertexIndex 行
        int[] arr = edges[vertexIndex];
        for (int i = 0; i < arr.length; i++) {
            // 如果arr[i] = 1，说明i对应的顶点就是vertex的邻接顶点
            if (arr[i] == 1){
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据vertex的前一个邻接顶点priorVertexIndex，找到下一个邻接顶点
     * @param vertex
     * @param priorVertexIndex
     * @return
     */
    public int findNeighborByPriorNeighbor(String vertex, int priorVertexIndex){
        // 拿到vertex的索引
        int vertexIndex = vertexList.indexOf(vertex);
        // 从(priorVertexIndex + 1)开始遍历二维数组的第 vertexIndex 行
        int[] arr = edges[vertexIndex];
        for (int i = priorVertexIndex + 1; i < arr.length; i++) {
            if (arr[i] == 1){
                return i;
            }
        }
        return -1;
    }

    /**
     * 深度优先遍历
     * @param vertex
     */
    private void dfs(String vertex, boolean[] isVisited){
        // 打印当前顶点
        System.out.print(vertex + " --- ");
        // 标记当前顶点已经访问
        isVisited[vertexList.indexOf(vertex)] = true;
        // 找到当前顶点第一个邻接顶点
        int neighbor = findFstNeighbor(vertex);
        // 不等于-1，就打印，并且把第一个邻接顶点当成当前顶点，再去找它的第一个邻接顶点
        while (neighbor != -1){
            // 如果neighbor没有被访问过
            if (!isVisited[neighbor]){
                dfs(vertexList.get(neighbor), isVisited);
            } else {
                // 如果neighbor被访问过了，就找下一个邻接顶点
                neighbor = findNeighborByPriorNeighbor(vertex, neighbor);
            }
        }
        // 跳出循环，说明一条路走到底了，就应该开始回溯，怎么回溯？
        // 其实外面再写个方法，循环vertexList，让每个未被访问过的顶点都调用这个方法就好了
    }

    public void dfs() {
        for (String str : vertexList){
            if (!isVisited[vertexList.indexOf(str)]){
                dfs(str, isVisited);
            }
        }
    }

深度优先遍历的方法都写了详细注释，这里不再赘述。说一说找某个顶点的第一个邻接顶点(findFstNeighbor)和找某个顶点指定邻接顶点后面的那个邻接顶点(findNeighborByPriorNeighbor)这两个方法。

• findFstNeighbor：我们构建好了二维数组，即邻接矩阵，所以找某个顶点的邻接顶点直接在矩阵中找就可以。比如我要找 A的第一个邻接顶点，那就遍历 A所在的那一行，找到第一个 1出现位置的索引，该索引对应的就是 A的第一个邻接顶点。如下：

  A  B  C  D  E  F  G  H
A[0, 1, 0, 0, 0, 1, 0, 1]

A对应的就是这一行，第一个1出现的位置的索引是1，1在vertexList中对应的是B，所以A的第一个邻接顶点就是B。

• findNeighborByPriorNeighbor：这个方法是什么意思呢？比如我传入的参数是 A， 1，意思就是我要找 A的邻接顶点，找什么要的邻接顶点？就是在

  A  B  C  D  E  F  G  H
A[0, 1, 0, 0, 0, 1, 0, 1]

这一行中，找到位置1后面的那个邻接顶点，即找到位置1后面的1第一次出现的位置的索引，显然对应的索引是5，在vertexList中对应的是F。