算法详解——图的深度优先遍历和广度优先遍历

一、图结构

  图结构指的是如下图所示的由节点和边组成的数据。

二、深度优先遍历

2.1 图的遍历

  图的遍历任务指的是从图中某个节点开始，遍历得到图中所有节点的过程。

2.2 深度优先遍历过程

  假设我们从1号节点开始进行深度优先遍历。遍历的步骤如下：首先，我们选择1号顶点作为起始点。从1号顶点开始，我们尝试沿着边访问尚未到达过的顶点。我们发现2号顶点是未到达过的，所以我们移动到2号顶点。现在，以2号顶点为起点，我们继续尝试访问其他未到达过的顶点。这样，我们又到达了4号顶点。接着，以4号顶点为起点，我们尝试访问其他未到达过的顶点。然而，此时我们无法再通过4号顶点的边访问其他未到达过的顶点，所以我们需要回到2号顶点。回到2号顶点后，我们发现沿着2号顶点的边也无法再访问其他未到达过的顶点。因此，我们需要继续回到1号顶点。现在，我们继续检查1号顶点的边，看看是否还有其他未到达过的顶点。这时我们到达了3号顶点，然后以3号顶点为起点继续访问其他未到达过的顶点，最后到达了5号顶点。此时，所有顶点都已经被访问过，遍历结束。遍历的顺序如下图所示：

2.3 深度优先遍历核心思想

  深度优先遍历的核心思想在于：首先选择一个未被访问过的顶点作为起始点，然后沿着当前顶点的边前进到未被访问过的顶点。当当前顶点没有未访问过的邻居顶点时，则回溯到上一个顶点，继续试探访问其他顶点，直到所有的顶点都被访问过为止。显然，深度优先遍历是沿着图的某一条分支遍历直到末端，然后回溯，再沿着另一条分支进行同样的遍历，直到所有的顶点都被访问过为止。

2.4 深度优先遍历实现

  如何将这一过程用代码实现呢？在讨论代码实现之前，我们需要先解决如何存储一个图的问题。最常用的方法是使用一个二维数组 $e$ 来表示，具体如下所示：

  上图中的二维数组中，第$i$行第$j$列表示从顶点$i$到顶点$j$是否存在一条边。其中，$1$表示存在边，$\infty$表示不存在边。我们将自己到自己的路径（即$i$等于$j$）设为$0$。这种图的存储方式被称为邻接矩阵存储法。

  注意观察的同学会发现，这个二维数组沿主对角线对称。这是因为上述图是无向图。无向图指的是图的边没有方向性，例如边1-5表示，1号顶点可以到达5号顶点，同时5号顶点也可以到达1号顶点。

  接下来，我们将解决如何使用深度优先搜索来实现图的遍历。

// C 代码

#include <stdio.h>

int book[101], sum, n, e[101][101];

void dfs(int cur) // cur 是当前所在的顶点编号
{
    int i;
    printf("%d ", cur);
    sum++; // 每访问一个顶点，sum就加1
    if (sum == n)
        return; // 所有的顶点都已经访问过则直接退出
    for (i = 1; i <= n; i++) // 从1号顶点到n号顶点依次尝试，看哪些顶点与当前顶点cur有边相连
    {
        // 判断当前顶点cur到顶点i是否有边，并判断顶点i是否已访问过
        if (e[cur][i] == 1 && book[i] == 0)
        {
            book[i] = 1; // 标记顶点i已经访问过
            dfs(i);      // 从顶点i再出发继续遍历
        }
    }
    return;
}

int main()
{
    int i, m, a, b;
    scanf("%d %d", &n, &m);
    // 初始化二维矩阵
    for (i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 999999999; // 我们这里假设99999999为正无穷
        }
    }
    // 读入顶点之间的边
    for (i = 1; i <= m; i++)
    {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1; // 这里是无向图，所以需要将e [b] [a]也赋为1
    }
    // 从1号城市出发
    book[1] = 1; // 标记1号顶点已访问
    dfs(1);      // 从1号顶点开始遍历
    getchar();
    getchar();
    return 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

# Python 代码

def dfs(cur):
    global sum
    print(cur, end=" ")
    sum += 1
    if sum == n:
        return
    for i in range(1, n + 1):
        if e[cur][i] == 1 and book[i] == 0:
            book[i] = 1
            dfs(i)

if __name__ == "__main__":
    book = [0] * 101
    sum = 0
    n, m = map(int, input().split())
    e = [[0] * 101 for _ in range(101)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                e[i][j] = 0
            else:
                e[i][j] = 999999999  # 我们这里假设99999999为正无穷
    for _ in range(m):
        a, b = map(int, input().split())
        e[a][b] = 1
        e[b][a] = 1  # 这里是无向图，所以需要将e [b] [a]也赋为1
    book[1] = 1
    dfs(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
26
27
28
29
30
31

  在上面的代码中变量cur存储的是当前正在遍历的顶点，二维数组e存储的就是图的边(邻接矩阵)，数组book用来记录哪些顶点已经访问过，变量sum用来记录已经访问过多少个顶点，变量n存储的是图的顶点的总个数。完整代码如下。

三、广度优先遍历

3.1 广度优先遍历过程

  广度优先遍历结果如下图所示：

  使用广度优先遍历这个图的过程如下：首先选择一个未被访问过的顶点作为起始顶点，例如以1号顶点为起点。将1号顶点放入队列中，然后将与1号顶点相邻的未访问过的顶点，即2号、3号和5号顶点依次放入队列中。如下图所示：

  接下来，将2号顶点相邻的未访问过的顶点4号顶点放入队列中。到此，所有顶点都被访问过，遍历结束。如下图所示：

3.2 广度优先遍历核心思想

  广度优先遍历的主要思想是：首先选择一个未被访问过的顶点作为起始顶点，然后访问其所有相邻的顶点。接着，对于每个相邻的顶点，再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。

3.3 广度优先遍历实现

// C 代码

#include <stdio.h>

int main() {
    int i, j, n, m, a, b, cur, e[101][101], book[101] = {0}, que[10001], head, tail;

    scanf("%d %d", &n, &m);

    // 初始化二维矩阵
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999; // 我们这里假设99999999为正无穷
        }
    }

    // 读入顶点之间的边
    for (i = 1; i <= m; i++) {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1; // 这里是无向图，所以需要将e[b] [a]也赋值为1
    }

    // 队列初始化
    head = 1;
    tail = 1;

    // 从1号顶点出发，将1号顶点加入队列
    que[tail] = 1;
    tail++;
    book[1] = 1; // 标记1号顶点已访问1

    // 当队列不为空的时候循环
    while (head < tail) {
        cur = que[head]; // 当前正在访问的顶点编号
        for (i = 1; i <= n; i++) { // 从1~n依次尝试
            // 判断从顶点cur到顶点i是否有边，并判断顶点i是否已经访问过
            if (e[cur][i] == 1 && book[i] == 0) {
                // 如果从顶点cur到顶点i有边，并且顶点i没有被访问过，则将顶点i入队
                que[tail] = i;
                tail++;
                book[i] = 1; // 标记顶点i已访问
            }
            // 如果tail大于n，则表明所有顶点都已经被访问过
            if (tail > n)
                break;
        }
        head++; // 当一个顶点扩展结束后，head++，然后才能继续往下扩展
    }

    for (i = 1; i < tail; i++)
        printf("%d ", que[i]);

    return 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

# Python 代码

def main():
    n, m = map(int, input().split())
    e = [[0] * 101 for _ in range(101)]
    book = [0] * 101
    que = [0] * 10001
    head = tail = 1

    # 初始化二维矩阵
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                e[i][j] = 0
            else:
                e[i][j] = 99999999  # 我们这里假设99999999为正无穷

    # 读入顶点之间的边
    for _ in range(m):
        a, b = map(int, input().split())
        e[a][b] = 1
        e[b][a] = 1  # 这里是无向图，所以需要将e[b][a]也赋值为1

    # 从1号顶点出发，将1号顶点加入队列
    que[tail] = 1
    tail += 1
    book[1] = 1  # 标记1号顶点已访问

    # 当队列不为空的时候循环
    while head < tail:
        cur = que[head]  # 当前正在访问的顶点编号
        for i in range(1, n + 1):  # 从1~n依次尝试
            # 判断从顶点cur到顶点i是否有边，并判断顶点i是否已经访问过
            if e[cur][i] == 1 and book[i] == 0:
                # 如果从顶点cur到顶点i有边，并且顶点i没有被访问过，则将顶点i入队
                que[tail] = i
                tail += 1
                book[i] = 1  # 标记顶点i已访问
            # 如果tail大于n，则表明所有顶点都已经被访问过
            if tail > n:
                break
        head += 1  # 当一个顶点扩展结束后，head++，然后才能继续往下扩展

    for i in range(1, tail):
        print(que[i], end=" ")

if __name__ == "__main__":
    main()
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

参考文献

[1]啊哈磊. 2014《啊哈！算法》, 人民邮电出版社