算法备忘录·搜索与图论

本文最后更新于 2024年5月15日凌晨

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

搜索与图论

图的搜索

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

DFS

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

BFS

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

有通用的框架

queue ← 初始状态
while (queue 不空){
    t ← 队头
    扩展队头
}

图的存储

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

邻接矩阵

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

邻接表

每个点有一个单链表，类似于拉链法
使用的邻接表的 TLE 极可能是没有初始化 h[]

模板

// 对每个节点 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)$ ， $n$ 表示点数， $m$ 表示边数

深度优先遍历

遍历不需要恢复现场

模板

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); //不需要恢复现场
    }
}

宽度优先遍历

模板

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);
        }
    }
}

有向图的拓扑序列

宽度优先搜索的应用
拓扑序列：所有的边都是从前指向后的
- 有向无环图一定存在拓扑序列——所以有向无环图称为拓扑图

模板

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;
}

最短路

图论最难的部分是实现

图中有 $n$ 个点、 $m$ 条边

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(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 次

模板

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)$ ，适合稀疏图
使用邻接表存储，是为了快速找到从每个点出发的所有邻边

模板

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)$ ，其中 $n$ 表示点数， $m$ 表示边数
因为有负权边，因此每个点都需要对每个边进行遍历，从而更新 dist[]
如果第 $n$ 次迭代仍然会松弛三角不等式，就说明存在一条长度是 $n+1$ 的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路
注意最后的 dist[n] > 0x3f3f3f3f / 2

模板

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(nm)$ 。因此时间不是很紧的题可以用 spfa 代替 Dijkstra。
为什么 spfa 最后说可以用 dist[n]==0x3f3f3f3f 进行判断？这是因为，Bellman-ford 在更新时，即便是没有通路从 1 到 n，但是与 n 相连的点 n - 1 也会让 dist[n] 更新；而 spfa 的话，如果没有连接有通路，那么 n - 1 是不会进入队列被更新到。因此 dist[n] 不会变化。

模板

spfa 求 1 到 n 的最短路

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];
}

判断图中是否存在负环

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(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]$ 时，需要依赖于 $f[k-1]$ ，所以 $k4 应该先被算出来。

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

模板

// 初始化
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(n^2)$
思路
1. dist[i] = + INF;
2. for i in 1 ~ n:
  t ← 不在 s 中的、距离最近的点（s 是当前已确定最短距离的点）;
  s ← t;
  用 t 更新其它点（1 ~ n）到集合的距离;（点到集合的距离：点所有连到集合的边的最小距离）
3. 执行 2 操作 n 次
模板

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(m\log n)$

Kruskal 算法

适用于稀疏图
时间复杂度是 $O(m\log m)$
思路
1. 按所有边按权重从小到大排序（瓶颈 $O(m\log m)$ ）
2. 枚举每条边 ab（权重为 c），如果 a、b 不连通，将这条边加入集合中
模板

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)$
用于判断一个图是不是二分图
- 二分图：图中不含奇数环
思路
for i in 1 ~ n:
if i 未染色：
dfs(i, 1)
模板

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)$
用于求二分图的最大匹配
思路
- 遍历第一个集合的点，找与其可以匹配的点。可以匹配的点满足这样的规则：
  1. 如果这个点没有被匹配，那么它俩匹配
  2. 如果这个点被匹配过了，那么考虑与它之前匹配的点能否匹配其它的点。如果可以，那么这个点与新点匹配；否则不可以匹配。

模板

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 ++;
}

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

笔记

#计算机 #算法

算法备忘录·搜索与图论

https://justloseit.top/算法备忘录·搜索与图论/

作者

Mobilis In Mobili

发布于

2021年8月21日

更新于

2024年5月15日

许可协议