算法备忘录·搜索与图论

本文最后更新于:2021年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[k1][i][j],f[k1][i][k]+f[k1][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[k1]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(mlogn)O(m\log n)

Kruskal 算法

  • 适用于稀疏图
  • 时间复杂度是 O(mlogm)O(m\log m)
  • 思路
    1. 按所有边按权重从小到大排序(瓶颈 O(mlogm)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 ++;
    }

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!