算法备忘录·搜索与图论

本文最后更新于 2022年11月22日 下午

一直以来，没能系统学习算法，是我心中的痛；现在学了 y 总的算法基础课，做做笔记，希望能够有所收获。
这是第四节，搜索与图论。

搜索与图论

图的搜索

搜索 数据结构 空间 优劣
DFS stack O(h) 不具有最短性
BFS queue O(2^h) “最短路”

DFS

  • 顺序——搜索树
    • 递归（系统帮我们维护了栈）—— 回溯（从递归出来后还原现场）
      • 剪枝：递归过程中能够直接判断然后回溯
  • 一般无通用框架，关键是搜索的顺序

BFS

  • 能够搜索到最短（边的权重为 1）

  • 有通用的框架

    1
    2
    3
    4
    5
    queue ← 初始状态
    while (queue 不空){
        t ← 队头
        扩展队头
    }

图的存储

  • 有向图、无向图（无向图就当作双向有向图）

邻接矩阵

  • g[a][b] 存储边 a->b

邻接表

  • 每个点有一个单链表，类似于拉链法

  • 使用的邻接表的 TLE 极可能是没有初始化 h[]

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 对每个节点 k，开单链表，存储其能够走到的所有点。h[k] 存储单链表的头节点
    int h[N], e[N], ne[N], idx;

    //添加一条边 a -> b
    void add(int a, int b){
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
    }

    // 初始化
    idx = 0;
    memset(h, -1, sizeof h);

图的遍历

  • 时间复杂度为 O(n+m)O(n + m)，nn 表示点数，mm 表示边数

深度优先遍历

  • 遍历不需要恢复现场

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    int dfs(int u){
        st[u] == true; // st[u] 表示点 u 已经被遍历过
      
        for (int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];
            if (!st[j]) dfs(j); //不需要恢复现场
        }
    }

宽度优先遍历

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    queue<int> q;

    st[1];
    q.push(1);

    while(q.size()){
        int t = q.front();
        q.pop();
      
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (!st[j]){
              st[j] = true; // 表示点 j 已经被遍历过
              q.push(j);
            }
        }
    }

有向图的拓扑序列

  • 宽度优先搜索的应用

  • 拓扑序列：所有的边都是从前指向后的

    • 有向无环图一定存在拓扑序列——所以有向无环图称为拓扑图

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    bool tosort(){
        int hh = 0, tt = -1;

        // d[i] 存储点的入度
        for (int i = 1; i <= n; i ++ ){
            if (!d[i])
                q[++ tt] = i; // 加入所有入度为 0 的点
        }

        while (hh <= tt){
            int t = q[hh ++];
            // 对于队头 t，遍历其子节点，将子节点每个入度 - 1，如果入度为 0 则入队。
            for (int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if (--d[j] == 0)  
                    q[++ tt] = j;
            }
        }

        //如果所有点都入队了，说明存在拓扑序列；
        return tt = n - 1;
    }

最短路

图论最难的部分是实现

  • 图中有 nn 个点、mm 条边
graph LR
    A[最短路] -->B[单源最短路]
    A --> C[多源汇最短路]
    B --> D[所有边权都是正数]
    B --> E[存在负权边]
    D --> F[朴素 Dijstra 算法]
    D --> G[堆优化版的 Dijstra 算法]
    E --> H[Bellman-Ford]
    E --> I[SPFA]
    C --> J[Floyd 算法]

Dijkstra 算法

朴素 Dijkstra 算法

  • 时间复杂度 O(n2+m)O(n^2 +m)

  • 思路

    1. dist[1] = 0, dist[i] = + INF;
    2. for i in 1 ~ n:
      t ← 不在 s 中的、距离最近的点（s 是当前已确定最短距离的点）;
      s ← t;
      用 t 更新其它点（1 ~ n）到起点的距离;
    3. 执行 2 操作 n 次

  • 模板

    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
    int g[N][N]; // 存储每条边
    int dist[N]; // 存储 1 号点到每个点的距离
    bool st[N]; // 存储每个点的最短路是否已经确定

    // 求 1 号点到 n 号点的最短路，若不存在则返回 -1
    int dijkstra(){
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;

        for (int i = 0; i <n - 1; i ++ ){
            int t = -1;
            // 在未确定最短路的点中，寻找距离最小的点 t
            for (int j = 1; j <= n; j ++ )
                if (!st[j] &&(t == -1 || dist[t] > dist[j]))
                    t = j;
            
            st[t] = true;

            // 用 t 更新其他点的距离
            for (int j = 1; j <= n; j ++ ){
                dist[j] = min(dist[j], dist[t] + g[t][j]);
            }
        }

        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

堆优化版 Dijkstra

  • 我们发现，朴素 Dijkstra 每次需要寻找未确定最短路的点中距离最小的点，那么我们可以用小根堆来维护这个最小值点

  • 时间复杂度 O(mlogn)O(mlogn)，适合稀疏图

  • 使用邻接表存储，是为了快速找到从每个点出发的所有邻边

  • 模板

    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
    typedef pair<int, int> PII;

    int n; // 点的数量
    int h[N], w[N], e[N], ne[N], idx; // 邻接表存储
    int dist[N]; // 存储 1 号点到每个点的距离
    bool st[N]; // 存储每个点的最短路是否已经确定

    int dijkstra(){
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        heap.push({0, 1}); // first 存储距离，second 存储节点编号
        
        //  队列为空时，即没有点更新距离
        while (heap.size()){
            // 相比于朴素版，这里直接取了堆顶
            auto t = heap.top();
            heap.pop();

            int ver = t.second, distance = t.first;

            if (st[ver]) continue;
            st[ver] = true;

            for (int i = h[ver]; i != -1; i = ne[i]){
                int j = e[i];
                if (dist[j] > distance + w[i]){
                    dist[j] = distance + w[i];
                    heap.push({dist[j], j}); // 将更新了距离的点放入队列
                }
            }
        }
    }

Bellman-Ford 算法

  • 时间复杂度 O(nm)O(nm)，其中 nn 表示点数，mm 表示边数

  • 因为有负权边，因此每个点都需要对每个边进行遍历，从而更新 dist[]

  • 如果第 nn 次迭代仍然会松弛三角不等式，就说明存在一条长度是 n+1n+1 的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路

  • 注意最后的 dist[n] > 0x3f3f3f3f / 2

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int n, m;
    int dist[N];

    struct Edge{ 
        int a, b, w;
    }edges[M]; // 边，a表示出点，b表示入点，w表示边的权重

    // 求 1 号点到 n 号点的最短路，若不存在则返回 -1
    int bellman_ford(){
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;

        for (int i = 0; i < n; i ++ ){
            for (int j = 0; j < m; j ++ ){
                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                dist[b] = min(dist[b], dist[a] + w);
            }
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1; // 因为有负权边，所以即便是没有通路 dist[n] 也有可能减少了一些
    return dist[n];

spfa 算法

  • 队列优化的 Bellman-Ford 算法。仅更新队列中的点，这样就加快了速度。但是如果存在闭环，队列会不断更新从而不断循环。

    • 因此，判断负环的方法是引入 cnt[]，记录每个点最短距离更新的次数

  • 时间复杂度平均 O(m)O(m)，最坏情况下 O(nm)O(nm)。因此时间不是很紧的题可以用 spfa 代替 Dijkstra。

  • 为什么 spfa 最后说可以用 dist[n]==0x3f3f3f3f 进行判断？这是因为，Bellman-ford 在更新时，即便是没有通路从 1 到 n，但是与 n 相连的点 n - 1 也会让 dist[n] 更新；而 spfa 的话，如果没有连接有通路，那么 n - 1 是不会进入队列被更新到。因此 dist[n] 不会变化。

  • 模板

    • spfa 求 1 到 n 的最短路
    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
    int n;  // 总点数
    int h[N], w[N], e[N], ne[N], idx;  // 用邻接表存储所有边
    int dist[N];  // 存储 1 号点到每个点的距离
    bool st[N];  // 存储点是否在队列中

    int spfa(){
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;

        queue<int> q;
        q.push(1);
        st[1] = true;

        while (q.size()){
            auto t = q.front();
            q.pop();
            st[t] = false;

            for (int i = h[i]; i != -1; i = ne[i]){
                int j = e[i];
                if (dist[j] > dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    if (!st[j]){  // 如果队列中已存在 j，则不需要将 j 重复插入
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }

        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }
    • 判断图中是否存在负环
    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
    int n;
    int h[N], w[N], e[N], ne[N], idx;
    int dist[N], cnt[N];
    bool st[N];

    bool spfa(){
        queue<int> q;

        // 负环不一定要从点 1 出发，因此把所有点放入队列中
        for (int i = 1; i <= n; i ++ ){
            q.push(i);
            st[i] = true;
        }

        while (q.size()){
            auto t = q.front();
            q.pop();

            st[t] = false;

            for (int i = h[t]; i != -1; i = ne[i]){
                int j =e[i];
                if (dist[j] > dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1;
                    if (cnt[j] > n) return true;  // 说明最短路中至少含了 n + 1 个点
                    if (!st[j]){
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
        return false;
    }

FLoyd 算法

  • 时间复杂度是 O(n3)O(n^3)
  • Floyd 算法极其简洁，但是难以理解，因为是用了 DP 思想：核心是公式 f[k][i][j]=min(f[k−1][i][j],f[k−1][i][k]+f[k−1][k][j])f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])。在计算 f[k]f[k] 时，需要依赖于 f[k−1]f[k-1]，所以 $k4 应该先被算出来。

一个笑话：为什么 Dijkstra 不能提出 floyd 算法？因为他的名字是 ijk 而不是 kij。

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // 初始化
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
        }
    }

    // Floyd 算法结束后，d[a][b] 表示 a 到 b 的最短距离
    void floyd(){
        for (int k = 1; k <= n; k ++ ){
            for (int i = 1; i <= n; i ++ ){
                for (int j = 1; j <= n; j ++ ){
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }

最小生成树

graph LR
    A[最小生成树] -->B[Prim 算法]
    A --> C[Kruskal 算法]
    B --> D[朴素 Prim 算法]
    B --> E[堆优化版的 Prim 算法]

Prim 算法

朴素 Prim 算法

  • 适用于稠密图

  • 时间复杂度是 O(n2)O(n^2)

  • 思路

    1. dist[i] = + INF;
    2. for i in 1 ~ n:
      t ← 不在 s 中的、距离最近的点（s 是当前已确定最短距离的点）;
      s ← t;
      用 t 更新其它点（1 ~ n）到集合的距离;（点到集合的距离：点所有连到集合的边的最小距离）
    3. 执行 2 操作 n 次

  • 模板

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
int n;          // n 表示点数
int g[N][N];        
int dist[N];    // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中

// 如果图不连通，则返回 INF，否则返回最小生成树的树边权重之和

int prim(){
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ ){
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

堆优化版的 Prim 算法

  • 适用于稀疏图【不常用，因为不好写】
  • 时间复杂度是 O(mlog⁡n)O(m\log n)

Kruskal 算法

  • 适用于稀疏图
  • 时间复杂度是 O(mlog⁡m)O(m\log m)
  • 思路
    1. 按所有边按权重从小到大排序（瓶颈 O(mlog⁡m)O(m\log m)）
    2. 枚举每条边 ab（权重为 c），如果 a、b 不连通，将这条边加入集合中
  • 模板
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
int n, m;
int p[N];

struct Edge{
    int a, b, w;

    bool operator< (const Edge &W)const{
        return w < W.w
    }
}edges[M];

int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal(){
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;


    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ){
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b){
            p[a] = b;
            res += w;
            cnt ++;
        }
    }
    if (cnt < n - 1) return INF;  // 最小生成树最后有 n - 1 条边
    return res;
}

二分图

染色法

  • 时间复杂度 O(n+m)O(n+m)
  • 用于判断一个图是不是二分图
    • 二分图：图中不含奇数环
  • 思路
    for i in 1 ~ n:
    if i 未染色：
    dfs(i, 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
int n;
int h[N], e[M], ne[M], idx;
int color[N];  // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色


// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c){
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if (color[j] == -1){
            if (!dfs(j, !c)) return false;
        }else if (color[j] == c) return false;
    }
    return true;
}


bool check(){
    memset(color, -1 sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ ){
        if (color[i] == -1){
            if(!dfs(i, 0)){
                flag = false;
                break;
            }
        }
    }
    return flag;
}

匈牙利算法

  • 时间复杂度 O(mn)O(mn)，实际运行时间远小于 O(mn)O(mn)

  • 用于求二分图的最大匹配

  • 思路

    • 遍历第一个集合的点，找与其可以匹配的点。可以匹配的点满足这样的规则：
      1. 如果这个点没有被匹配，那么它俩匹配
      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
    int n1, n2;   // n1 表示集合 1 中的点数，n2 表示集合 2 中的点数
    int h[N], e[M], ne[M], idx;  // 匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
    int match[M]; // 存储集合 2 中每个点当前匹配集合 1 中对应的点
    bool st[N];   // 表示集合 2 中的点是否被遍历过，为了避免 find(x) 做深搜无限循环

    bool find(int x){
        for (int i = h[x]; i != -1; i = ne[i]){
            int j = e[i];
            if (!st[j]){
                st[j] = true;
                if (match[j] = 0 || find(match([j]))){
                    match[j] = x;
                    return true;
                }
            }
        }
        return false;
    }

    // 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
    int res = 0;
    for (int i = 1; i <= n1; i ++ ){
        memset(st, false, sizeof st);  // 每次都要刷新 st[]
        if (find(i)) res ++;
    }

算法备忘录系列目录：
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·STL
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析

笔记
#计算机 #算法
算法备忘录·搜索与图论
https://justloseit.top/算法备忘录·搜索与图论/
作者
Mobilis In Mobili
发布于
2021年8月21日
更新于
2022年11月22日
许可协议