11.图结构与基本搜索

发表于 更新于 分类于 ，

图结构与基本搜索

本章介绍图的基本概念、存储方式以及两种基本图搜索算法——深度优先搜索（DFS）和广度优先搜索（BFS），涵盖图的定义、分类、存储结构及其在代码中的实现，并提供DFS和BFS的典型模板代码。

图

由顶点（节点）和边组成的一种非线性数据结构，用于表示对象之间的关系，顶点代表对象，边代表对象之间的连接或关系。

有向图与无向图

图的稀疏与稠密

概念大全：

  • 图：由顶点（V）与连接顶点的边（E）构成
  • 无向图：每条边没有方向的定义
  • 有向图：每条边有方向，例如表达路的话，一条边就表达一条单向车道
  • 完全图：任意两个顶点之间都有边（对于有向图则两个方向的边都有）
  • 稀疏图：边较少的图
  • 稠密图：边较多的图
  • 顶点的度：与该点关联的边的个数，如果是有向图则分“出度”和“入度”
  • 路径：连续的边构成的顶点序列
  • 路径长度：路径的边长度之和（如果没长度可以是边数量之和）
  • 回路（环）：第一个顶点和最后一个顶点相同的路径
  • 简单路径：除起点和终点外，其余顶点皆不相同
  • 简单回路：起点终点相同，其他顶点皆不相同
  • 连通图：图中任意两个顶点之间都能找到一个路径
  • 子图：如果图B的顶点和边都是图A的顶点和边的子集，则B是A的子图
  • 连通分量（强连通分量）：图B是图A的子图且图B是连通图（即A的连通子图），A中任意不在B中的顶点加入B后，B不再连通，这样的B是A的连通分量
  • 极小连通子图：图B是图A的连通子图，如果B任意删除一条边后都不再连通，则B是A的极小连通子图
  • 生成树：包含图 G 的所有顶点的极小连通子图，是图G的生成树
  • 生成森林：非连通图的各个连通分量的生成树的集合
  • 最小生成树：边有边权（或长度或其他量），边权之和最小的生成树

图的存储方式

在代码中存这个图：

顺序存储（邻接矩阵）

用一个二维数组存储点与点的关系

  • n 个顶点， e 条边
  • 对于无边权的图，g[i][j] == 1表示顶点 i 与顶点 j 有边，否则无边
  • 对于有边权的图，可以额外用 w[i][j] 表示边的权值
  • 无向图则 g[i][j] == g[j][i]
  • 适合稠密图

链式存储，竞赛通常用链式前向星

  • n 个顶点，e条边
  • 每一个顶点， 都用一个链表表示与其相连的边
  • 适合稀疏图
  • 对于无向图，则两个方向各建一条有向边

知识点：在面对一道图问题时，一定要先分析图的稠密程度，再决定用邻接矩阵还是链式前向星。 Tip：大多问题都可以用链式前向星，在一些显著稠密、卡常数的问题中，考虑用邻接矩阵，邻接矩阵代码也相对好写一些。

链式前向星模板参考

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
const int maxN = 1100;
const int maxM = 110000;
int first[maxN];    // 每个顶点发出的边的边链表头结点，该数组可初始化为 -1 表示每个顶点都还没有边
int nex[maxM];      // 同个顶点发出的边的边结点 next 域
int u[maxM];        // 边的发出顶点
int v[maxM];        // 边的收入顶点
int w[maxM];        // 边的权值
int tp;             // 全局“内存分配”“指针”，就是模拟分配内存时，tp从0开始逐个增加

// 比如 first[1]，表示顶点 V1 发出的第一条边的“指针”，这里就是数组编号
// nex[first[1]] 表示顶点 V1 发出的边的链表的第二个结点编号
// nex[nex[first[1]]] 表示顶点 V1 发出的边的链表的第三个结点编号 ...
// u[first[1]] 顶点 V1
// v[first[1]] 顶点 V1 发出的第一条边的另一端的顶点编号，比如 v[first[1]] == 3 就表示 V1 连着 V3
// w[first[1]] 顶点 V1 发出的第一条边的权值

void AddEdge(int s, int e, int weight)
{
    // 建图：表示顶点 s 向顶点 e 发出了一条权重为 weight 的有向边
    // 程序开始时 tp 初始为 0
    nex[tp] = first[s]; // 类似链表头插法
    first[s] = tp;
    u[tp] = s;
    v[tp] = e;
    w[tp] = weight;
    tp ++;
}
void DbEdge(int s, int e, int weight)
{
    // 如果表示无向图，那简单，两个方向都建一条有向边就好
    AddEdge(s, e, weight);
    AddEdge(e, s, weight);
    // 结合 tp 的属性，你会发现，可以很容易找到两个顶点之间成对的双向边
    // 比如 i 是 s 发向 e 的边的编号，那么 i^1 （异或操作） 就是 e 发向 s 的边
}

bool vis[maxN] = {0};
void DFS(int now)
{
    // 以深度优先搜索为例遍历全图，感受前向星的使用
    for(int i = first[now]; i != -1; i = nex[i])
    {
        // 类似链表访问过程，i = first[now] 从头结点获得第一条边的指针
        // i = nex[i] 即链表指针域往后遍历
        // i != -1 即判断是否到链表末尾
        // u[i]、v[i]、w[i] 都是链表结点的数据域，当然你可以把 nex、u、v、w 封装在 struct 里
        if(!vis[v[i]])
        {
            vis[v[i]] = true;
            DFS(v[i]);
        }
    }
}

棋盘类图问题

迷宫、下棋等问题，节点即格点或格子，与其相关的是上下左右四个方向，或者加上斜向共8个方向，用邻接矩阵或链式前向星建图就太麻烦了，可以直接用xy坐标来表达节点，增减xy来找相邻节点。

基本的搜索

深度优先搜索（Deep First Search, DFS）

深度优先搜索，用栈（递归的形式）

一条路走到底，往回一步，再一条路走到底，往回一步...一般用于求全部解、求一些很“深”的解

  1. 访问起始点v;
  2. 若v的第1个邻接点没访问过，深度遍历此邻接点；
  3. 若当前邻接点已访问过，再找v的第2个邻接点重新遍历；
  4. 如果所有邻接点都已访问，则返回上一个访问的顶点。

在网格上DFS典型模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int maxn = 110;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int graph[maxn][maxn];
bool visited[maxn][maxn];
int endX, endY;
int DFS(int x, int y) {
    if (x == endX && y == endY) return true;
    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i], nextY = y + dy[i];
        // 把 graph[0][各列] 和 graph[各行][0] 设为不能走的哨兵，让实际数据从 1 开始，就不用额外判断坐标范围了
        if (graph[nextX][nextY] && !visited[nextX][nextY]) {
            // 这里 graph[i][j] 为 1 表示能走，为 0 表示不能走
            visited[nextX][nextY] = true;
            if (DFS(nextX, nextY)) return true;
        }
    }
    return false;
}

在图上DFS典型模板

1
2
3
4
5
6
7
8
9
10
11
12
13
const int maxn;
int g[maxn][maxn];  // 邻接矩阵
bool vis[maxn];
void DFS(int now, int n) {
    // now: 当前顶点编号
    // n: 顶点个数
    if (vis[now]) return;
    vis[now] = true;
    for (int i = 0; i < n; i++) {
        if (g[now][i])  // now 与 i 之间有边
            DFS(i, n);
    }
}

广度优先搜索（Breath First Search, BFS）

广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况，因此，广度优先搜索不是一个递归的过程，其算法也不是递归的，就近访问，一圈圈外扩一般用于求最短的路、最近的解。

  1. 在访问了起始点v之后，将 v 的尚未访问的邻接点放入访问队列；
  2. 在队列中出队尚未访问的顶点，进行访问
  3. 直到所有顶点都被访问

在网格上BFS典型模板

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
struct Node {
    int x, y;
    Node() { x = y = 0; }
    Node(int x_, int y_) {
        x = x_;
        y = y_;
    }
};
int BFS(int startX, int startY) {
    std::queue<Node> q;
    q.push(Node(startX, startY));
    visited[startX][startY] = true;
    while (!q.empty()) {
        Node now = q.front();
        q.pop();
        if (now.x == endX && now.y == endY) return true;
        for (int i = 0; i < 4; i++) {
            int nextX = now.x + dx[i], nextY = now.y + dy[i];
            if (graph[nextX][nextY] && !visited[nextX][nextY]) {
                visited[nextX][nextY] = true;
                q.push(Node(nextX, nextY));
            }
        }
    }
    return false;
}

在图上BFS典型模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int maxn;
int g[maxn][maxn];  // 邻接矩阵
bool vis[maxn];
void BFS(int start, int n) {
    queue<int> q;
    q.push(start);
    vis[start] = true;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            if (g[now][i] && !vis[i]) {
                vis[i] = true;
                q.push(i);
            }
        }
    }
}