目录

数据结构和算法 | 图的讲解【3】

1. 基本概念

图的基本概念中我们需要掌握的有这么几个概念:无向图、有向图、带权图;顶点(vertex);边(edge);度(degree)、出度、入度。下面我们就从无向图开始讲解这几个概念。

如图所示是一个无向图,图中的元素(A、B、C、D、E、F)被称为顶点(vertex),顶点可以与任意顶点建立连接关系,这种关系叫做边(edge),无向图中边是没有方向的。顶点相连接的边的条数就被称为度(degree),图中顶点 A 的度就是 3 。

https://img.dawnguo.cn/Algorithm/df85dc345a9726cab0338e68982fd1af.jpg

还有一种图,图中的边是有方向的,如图所示,则将这种图称为有向图。度这种概念在有向图中又被扩展为入度和出度。顶点的入度是指有多少条边指向这个顶点;顶点的出度指有多少条边以这个顶点为起点。

https://img.dawnguo.cn/Algorithm/c31759a37d8a8719841f347bd479b796.jpg

上述的边都没有权重,假如我们要拿一个图来存储地图数据的话,图中的边还需要表示距离,那么这个图就变成了带权图(weighted graph)。在带权图中,每条边都有一个权重,这个权重可以表示距离。

https://img.dawnguo.cn/Algorithm/55d7e4806dc47950ae098d959b03ace8.jpg

综上来看的,图的类型主要是根据边的类型来决定的。

2. 图的存储

图的基本概念不多,那么在计算机中我们该如何存储图这种数据结构呢?主要有两种方式来存储图,一种是邻接矩阵的方法,另一种是邻接表的方式。

2.1. 邻接矩阵

邻接矩阵是图最直观的一种存储方式,底层依赖于二维数组。

  • 对于无向图来说,如果顶点 i 和顶点 j 之间有边那么则将 A[i][j]A[j][i] 标记为 1
  • 对于有向图来说,如果顶点 i 有一条边指向顶点 j,但是顶点 j 没有一条边指向顶点 i,那么则将 A[i][j] 标记为 1,但是 A[j][i] 不用标记为 1。
  • 对于带权图来说,只是从存储 1 变成存储具体的权重。

https://img.dawnguo.cn/Algorithm/625e7493b5470e774b5aa91fb4fdb9d2.jpg

  • 邻接矩阵的缺点是在表示一个图时通常很浪费存储空间。

    对于无向图来说,它是一个对称矩阵,即 A[i][j] 等于 1 的话,那么 A[j][i] 也等于 1。那么实际上只要存储一半就可以了。

    另外,假如存储的是稀疏图,也就是顶点很多,但是每个顶点的边不多的一种图。那么使用邻接矩阵存储将更浪费存储空间,因为很多位置的值都是 0,这些 0 其实都是没有用的。

  • 邻接矩阵的优点就是存储方式简单、直观,而且获取两个顶点的关系时非常高效。另外,使用邻接矩阵时,在计算上也很方便。因为很多图的运算实际上可以转换为矩阵的运算,比如求最短路径问题时会提到一个 Floyd-Warshall 算法,这个算法会利用到矩阵循环相乘若干次的结果。

2.2. 邻接表

图的另一种存储方法,是使用邻接表(Adjacency List)。如图所示,有向图中的每个顶点对应一个链表,该链表中存储的是该顶点指向的顶点。对于无向图来说是类似的,每个节点对应的链表中存储的是该节点所相连的顶点。

https://img.dawnguo.cn/Algorithm/039bc254b97bd11670cdc4bf2a8e1394.jpg

  • 邻接表相比邻接矩阵的一个优点就是节省空间,但是使用起来比较耗时间(时间换空间的设计思想)。在使用邻接矩阵判断无向图中 i 和 j 之间是否存在一条边,那么只需要判断 A[i][j] 是否为 1,而在邻接表中判断无向图中 i 和 j 之间是否存在一条边,那么需要判断 i 这个顶点对应的链表中是否存在 j。而且链表的方式对于缓存来说不太友好。所以,综上来说在邻接表中查询两个顶点的关系没有邻接矩阵那么高效了。
  • 但是,为了让查询变得更加高效。我们可以参考散列表中提到的那样,将链表换成平衡二叉查找树(比如红黑树),或者其他动态数据结构,比如跳表、散列表,有序动态数组(结合二分查找)等。

逆邻接表

邻接表中存储的是这个顶点指向的顶点,那么逆邻接表中存储的是指向这个顶点的顶点。比如要想查看 4 这个顶点指向了哪些节点就可以使用邻接表。但是想要查看有哪些节点指向了 4 这个顶点,那么就需要逆邻接表了。

https://img.dawnguo.cn/Algorithm/501440bcffdcf4e6f9a5ca1117e990a1.jpg

2.3. 总结

综上来说,邻接矩阵的缺点是比较浪费空间,但是优点是查询效率高,还方便矩阵运算。邻接表的优点是节省存储空间,但是不方便查找(查找效率肯定没邻接矩阵高)。对于此,我们可以将链表替换成查询效率较高的动态数据结构,比如平衡二叉树(红黑树)、跳表、散列表等。

3. 图的搜索

图上的搜索算法,最直接的理解就是,在图中找出从一个顶点出发,到另一个顶点的路径。具体方法有很多,比如有最简单、最“暴力”的深度优先、广度优先搜索,还有 A*、IDA* 等启发式搜索算法。深度优先、广度优先搜索即可以用在有向图,也可以用在无向图上。下面的实现以无向图和邻接表的存储方式为例。

广度优先搜索,简称 BFS。这种搜索方法是一层层的向外搜索,先从起点开始,然后再搜索离起点最近的顶点;之后再从离起点最近的顶点出发搜索离这些顶点最近的顶点。整个过程示意图如图所示,跟二叉树的层次遍历是一样的。

https://img.dawnguo.cn/Algorithm/002e9e54fb0d4dbf5462226d946fa1ea.jpg

相应的代码实现,如下代码所示。from 表示起点,to 表示终点。和层次遍历一样,广度优先搜索使用了队列这种数据结构。队列主要用来存储那些已经被访问,但是相邻的顶点还没有被访问的顶点。为什么使用队列这种数据结构呢?从应用场景出发,因为广度优先搜索方法是逐层访问的。也就是先访问 k 层的顶点,访问之后再去访问 k+1 层的顶点。但是,在访问第 k 层顶点的时候需要将 k+1 层的顶点也保存下来,而且 k+1 层顶点是在第 k 层顶点之后被访问并从队列中退出,也就相当于 “后来后出”。

但是,相比层次遍历又多一些内容,主要多出的是 visitedpaths 这两个数组,visited 数组主要是用来存储顶点是否已经被访问过了,因为图相比树更为复杂,有些顶点会有多个相邻顶点。为了避免顶点被重复访问,所以借用了一个数组。

paths 数组主要用来记录从 fromto 的广度搜索路径,但是每个数组元素(数组下标即顶点编号)只存储该顶点前面的那个顶点,比如 paths[3] 存储 2,则表示是先访问到 2 ,然后从 2 再访问到 3。这样的存储方式是逆向的,为了正向地输出搜索路径,可以使用递归的方式,递归的时候将输出放置到递归之后。因为只有等前面的顶点递归完成之后,再输出本顶点,才是正向的路径。

 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
public void bfsSearch(int from, int to) {
    if (this.v == 0 || from == to) {
        return;
    }

    boolean[] visited = new boolean[this.v];
    int[] paths = new int[this.v]; // 记录路径,记录该节点前面的节点是哪个   
    for (int i = 0; i < this.v; i++) {
        visited[i] = false;
        paths[i] = -1;
    }

    Queue<Integer> queue = new LinkedList<>();
    queue.offer(from);
    visited[from] = true;

    while (!queue.isEmpty()) {
        int w = queue.poll();

        for (Integer i : this.adj[w]) {
            if (!visited[i]) {
                queue.offer(i);
                visited[i] = true;
                paths[i] = w;

                if (i == to) {
                    printPath(paths, to);
                    break;
                }
            }
        }
    }
}

另外,需要明白的是在没有权重的图中,广度优先搜索的结果就是最短路径。这个是因为广度优先搜索的方式中,每次都是取最近的节点,那么当到达终点时,其实所需次数是最少的。

时间复杂度

广度优先搜索的时间复杂度最坏是遍历整个图,那么此时每个顶点都会被遍历到,每条边也会被访问一次。那么,假设边数为 E,顶点数为 V,此时时间复杂度为 O(V+E)(针对邻接表来说)。

空间复杂度

广度优先搜索时,空间复杂度主要来自于队列、visited 数组、paths 数组。这些数组的大小最大为 V,因为空间复杂度是 O(V)。

深度优先搜索,简称 DFS。怎么直观的理解呢?就是你从一个顶点出发,假如这个顶点有未被访问过的顶点则访问它,然后一个一个这么套下去。当一个顶点的相邻顶点都被访问过了,那么则退回上一个顶点,然后看一下上一个顶点是否有未被访问过的邻接顶点,有的话则访问它,然后一层一层下去。如果也都被访问过了,那么则再退。一个典型的生活中的例子就是走迷宫,先一条道走到“黑”,然后看不到出口了,上一个分叉口再换条道。

如图所示,这是在图上采用深度优先搜索之后的样子,实现表示搜索方向,虚线表示回退。

https://img.dawnguo.cn/Algorithm/8778201ce6ff7037c0b3f26b83efba85.jpg

深度优先搜索采用的思想是回溯思想,这种思想比较适合使用递归。我们使用递归的方式实现一下 DFS。相比 BFS,DFS 多了一个 find 变量,这个变量用于判断是否有找到顶点的。如果在没有遍历到一个顶点的最后一个邻接顶点之前就找到了终点,那么接下去的邻接顶点就可以不用遍历了,直接返回即可。

 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
public void dfsSearch(int from, int to) {
    if (this.v == 0 || from == to) {
        return;
    }

    boolean[] visited = new boolean[this.v];
    int[] paths = new int[this.v];
    for (int i = 0; i < this.v; i++) {
        visited[i] = false;
        paths[i] = -1;
    }

    visited[from] = true;
    reDFSS(from, to, visited, paths);

    if (this.FIND_DFS == true) {
        printPath(paths, to);
    }
}

public void reDFSS(int from, int to, boolean[] visited, int[] paths) {

    if (from == to) {
        this.FIND_DFS = true; 
        return;
    }

    for (Integer i : this.adj[from]) {
        if (this.FIND_DFS) {
            return;
        }
        if (!visited[i]) {
            visited[i] = true;
            paths[i] = from;

            reDFSS(i, to, visited, paths);
        }
    }
}

除了使用递归的方式实现之外,还可以将递归的方式转化成栈和循环结合的方式。在图的遍历这小节内容,你会看到非递归的方式。

深度优先搜索找到的并不是最短路径。

时间复杂度

采用同样的方法,从顶点和边的被访问次数出发,每条边最多被两次访问(一次遍历,一次回退),每个顶点被访问一次,那么时间复杂度是 O(V+E)(针对邻接表来说)。

空间复杂度

同样的,深度优先搜索的方式的空间复杂度主要来源栈、visited 数组和 paths 数组,栈的长度不可能超过顶点的个数,因此空间复杂度还是 O(V)。

3.3. 总结

  1. 广度和深度相比其他高级搜索算法(比如 A*算法)更简单粗暴,没有什么优化,也被称为暴力搜索算法。这两种算法适用于图不大的情况。
  2. 深度优先搜索主要借助了栈的方式,这个栈可以是函数调用栈也可以是栈这种数据结构(因为递归也可以转化为非递归的方式)。广度优先搜索主要使用队列。
  3. 图和树的比较,图的 DFS 类似于树的先序遍历;BFS 类似于树的层次遍历。
  4. 在没有权重的图中,BFS 搜索的路径结果就是最短路径;DFS 搜索的结果却不一定,因为 DFS 会“绕来绕去”,而 BFS 很直接每次都是最近的。
  5. 在求图的时间复杂度时,常用的方法是从顶点和边被遍历的次数出发。

4. 图的遍历

与图的搜索算法有点不同的是,图的遍历是指将图中的所有点都遍历一次。常见的遍历方法有深度优先遍历和广度优先遍历。这两种遍历方法的思想还是一样的,简单来说就是图的搜索方法就是加了一个节点判断,如果找到相应的节点就停止搜索。下面直接给出相应的代码,不再赘述。

4.1. 广度优先遍历

 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
public void bfsTraversal() {
    if (this.v == 0) {
        return;
    }

    boolean[] visited = new boolean[this.v];
    for (int i = 0; i < this.v; i++) {
        visited[i] = false;
    }
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(0);
    visited[0] = true;

    while (!queue.isEmpty()) {
        int w = queue.poll();
        System.out.print(w + "\t");

        for (Integer i : this.adj[w]) {
            if (visited[i] == false) {
                queue.offer(i);
                visited[i] = true;
            }
        }
    }
}

4.2. 深度优先遍历

 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
// 递归的方式
public void dfsTraversal() {
    if (this.v == 0) {
        return;
    }

    boolean[] visited = new boolean[this.v];
    for (int i = 0; i < this.v; i++) {
        visited[i] = false;
    }

    for (int i = 0; i < this.v; i++) {
        if (!visited[i]) {
            reDFST(i, visited);
        }
    }
}

public void reDFST(int f, boolean[] visited) {

    visited[f] = true;
    System.out.print(f + "\t");
    for (Integer i : this.adj[f]) {
        if(!visited[i]) {
            reDFST(i, visited);
        }
    }
}
 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
// 非递归的方式,使用了栈
public void dfsTraversalStack() {
    if (this.v == 0) {
        return;
    }

    boolean[] visited = new boolean[this.v];
    for (int i = 0; i < this.v; i++) {
        visited[i] = false;
    }

    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    visited[0] = true;
    System.out.print(0 + "\t");

    while (!stack.isEmpty()) {
        int w = stack.peek();
        int flag = 0;
        for (Integer i : this.adj[w]) {
            if (!visited[i]) {
                stack.push(i);
                visited[i] = true;
                System.out.print(i + "\t");
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            stack.pop();
        }
    }
}

巨人的肩膀

  1. 极客时间-《数据结构与算法》-王争老师