数据结构与算法学习笔记（4）——图的遍历

发表于   |   分类于   |  

图论是一个新的知识点，也是数据结构中很重要的一部分。

本文仅供个人记录和复习，不用于其他用途

什么是图

简单来说，就是一些小圆点和连接他们的线组成，上一章最后一张图片显示的就是图。我们已经通过这张图片，学习到了深度优先和广度优先的不同之处。但是有一个问题，我们为什么要创建图这个概念？或者说它能够解决什么样的问题？

图的深度优先遍历

小明想去旅游，可是他并不知道应该怎么去。看看下面的地图，你能够帮助小明找出最短的路线吗？

首先我们能够确定，这是一个有向图。例如，1可以直接到2，但是2不能够反过来到1，只能通过其他的路线到达。至于路线上面的数字，就是代表着这个路线的长度。那么，这些数据应该如何存储呢？

事实上一个二维数组就能够存储。比如第一行，就是代表着1号城市到达其他城市的距离。注意，这里是直接到达，而不是通过其他的线路到达。我们规定所有城市到自己的距离为0，不能直接到达的城市距离为无穷大，可以直接到达的就写上相应的数据。

接下来我们要寻找从1号城市到5号城市的最短路径。这里我们使用深度优先算法，按照自然数的顺序，可以得到一下三条路径：

  • 1-2-3-4-5，路径长为14
  • 1-2-5，路径长为9
  • 1-5，路径长为10

很显然，1-2-5就是最短路径。关于代码的实现，有几个需要注意的地方：

  • 用一个变量min来记录每次找到的最小值
  • 用book数组标记哪些城市已经搜索过，避免死循环
  • 前一步探索完毕后，记得取消标记，为下一次探索做准备
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
#include <stdio.h>
const int wuxian = 99999999;
int book[101];
int map[101][101];
int n;  // 城市数量
int min = 999999999;
void dfs(int cur, int dis)  // 第几个城市，累计路程
{
    int i;
    if(dis > min)  // 如果循环到这里时dis已经大于了最小路径，往下循环没有意义，直接退出
        return;
    if(cur == n)  // 如果到达了目标城市，就判断该路径是否最短
    {
        if(dis < min)
            min = dis;
        return;
    }
    for(i = 1; i <= n; i++)
    {
        if(map[cur][i] != wuxian && book[i] == 0)  // 如果当前城市cur到下一个城市i有路，且还没有走过
        {
            book[i] = 1;
            dfs(i, dis + map[cur][i]);
            book[i] = 0;  // 该点探索完毕后要取消标记
        }
    }
    return;
}
int main()
{
    int i, j, m, a, b, c;  // m表示公路数
    printf("请输入城市数量和公路数量：");
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            if(i == j)
                map[i][j] = 0;  // i == j表示自己，距离自然为0
            else
                map[i][j] = wuxian;  // 否则将赋值为无穷大，也就是无法达到
        }
    for(i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);  // 输入从第a号城市到第b号城市需要走的路程c
        map[a][b] = c;
    }
    book[1] = 1;  // 从1号城市出发
    dfs(1, 0);
    printf("最短路程为%d", min);
}

这里简要的解释一下dfs()。首先，得判断目前的路径长有没有超过最短路径，如果超过，剩下的探索没有意义，直接返回。如果到达了目标城市，就判断目前的路径是不是更短，是的话就将min值替换。再往下，就是深度优先中比较重要的循环。对于当前的节点，我们往下探索的条件有两个：

  • 必须能够直接到达
  • 之前没有走过

假如满足以上两个条件，就往下探索那个节点，否则就换下一个。那么呢，我们就将可以被探索的节点标记，对这个节点也进行深度探索，在探索完这个节点所有的可能后，取消标记。

图的广度优先遍历

说完深度，自然要说说广度。当然，有向图我就不提了，大家可以根据前一章的知识自行编写代码。这里我们来学习如何用广度优先算法来遍历无向图。

比如上面这个就是无向图，1表示起点城市，5表示目标城市，假设所有边的长度是一样的，那么最短的路径是多少？

这里存储的方式还是二维数组（一般被称作邻接矩阵），然后按照自然数的顺序，将城市依次入队。同样的，能够直接到达的城市才有资格入队。那么，当队列进行到5号城市时，探索完毕，得到最短路径。

可能有的人会问，为什么到达5号城市就是最短路径。上一章我们已经讲过它们的区别，那就是深度优先搜索只会探索纵深，你得到的答案并不一定就是最短的。但是呢，广度优先搜索每一次入队都是同一深度的点入队，当这一深度探索完了之后，才会轮到下一深度。因此，只要到达5号城市，那么这个路径一定就是最短的。

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
#include <stdio.h>
struct note
{
    int x;  // 城市编号
    int s;  // 转机次数
};
int main()
{
    struct note que[2501];
    int e[51][51] = {0}, book[51] = {0};
    int head, tail;
    int i, j, n, m, a, b, cur, start, end, flag = 0;
    scanf("%d %d %d %d", &n, &m, &start, &end);
    // 初始化二维矩阵
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if(i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;
        }
    }
    // 读入城市之间的航班
    for(i = 1; i <= m; i++)
    {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1;
    }
    // 队列初始化
    head = 1;
    tail = 1;
    // 从start号城市出发，将start号城市加入队列
    que[tail].x = start;
    que[tail].s = 0;
    tail++;
    book[start] = 1;
    // 当队列不为空时循环
    while(head < tail)
    {
        cur = que[head].x;  //当前队列中首城市的编号
        for(j = 1; j <= n; j++)
        {
            if(e[cur][j] != 99999999 && book[j] == 0)
            {
                // 从城市cur到城市j有航班并且城市j不在队列中，则将j号城市入队
                que[tail].x = j;
                que[tail].s = que[head].s + 1;  // 转机次数+1
                tail++;
                // 标记城市j已经在队列中
                book[j] = 1;
            }
            // 如果到达目标城市，停止扩展，任务结束，退出循环
            if(que[tail - 1].x == end)
            {
                // 注意下面两句话的位置千万不要写颠倒了
                flag = 1;
                break;
            }
        }
        if(flag == 1)
            break;
        head++;
    }
    // 打印队列中末尾最后一个（目标城市）的转机次数
    // 注意tail是指向队列队尾（即最后一位）的下一个位置，所以这需要-1
    printf("%d", que[tail - 1].s);
    return 0;
}

可以输入下面这组数据进行验证，结果为2则正确：

5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5

注意，当一个点扩展完后，一定要head++让队首出队。

选择哪种算法

相比较而言，广度优先搜索更加适用于所有的边距离相同的情况。对于这个问题，广度优先搜索会更快一些。