文章

Acwing算法基础课：搜索与图论

发表于 更新于
作者 lizhengxiao 21 分钟阅读

DFS

搜索树：由状态构成的树状结构

DFS：深度优先遍历搜索树。使用栈存储历经的路径，故使用空间$O(h)$；而BFS可能使用$O(2^h)$的空间，故一般使用DFS占空间较小。

对于状态信息的存储，可在函数局部（栈中）存储，也可在全局存储（全局变量）：

  • 可使用全局变量存储回溯时易于恢复现场的信息，同时在状态转移时免于频繁复制（适合数组类）
  • 可使用局部变量存储回溯时不方便恢复现场的信息，以及较小的信息（循环变量等）

编码方式的选择上，可选择调用者保存/被调用者保存，即在函数调用前、后保存、恢复现场，或是在函数开头、结尾处保存、恢复现场。

如何写dfs()函数

  • 定义好dfs()函数、参数的意义，即明确这个（递归）函数要干什么？：要填第x个空，要填第x行……
  • 考虑清楚边界情况
  • 维护好状态（状态的设置、恢复）
  • 可上手写代码后再考虑

题目：排列数字

dfs(x)的意义：准备填下标为x的数

题目：n-皇后问题

两种搜索方式：

  • dfs(x)：准备填第x行的皇后
  • dfs(x, y, s)：准备填下标为(x, y)的皇后，目前已经填了s个皇后

实际效率前者比后者更优，因为前者经过分析，搜索方式更充分地利用了性质（每行只有1个皇后）；从状态数来说，前者为$O(n!)$量级，而后者为$O(2^{n^2})$​量级。

另外，主对角线和副对角线坐标到截距的映射函数：

对于坐标(x, y)的点，主对角线编号：dg[x-y+n]，副对角线编号： udg[x+y]

BFS

使用”队列“数据结构。对于简单的、可预估大小的队列，可以手写队列，优点是常数小、有对数据更底层的控制；对不可预估数量的队列可使用STL。

题目：八数码

难点：

  • 状态的设计：一个二维数组？用一个string？
  • 状态中距离的表示：距离d放在状态结构体中？专门开一个unordered_map？

经验：考虑更多地利用标准库（string、unordered_map），可少写很多代码、代码更简洁；缺点是常数较大。涉及哈希？用string表示状态的话，自己就不用写哈希函数了（标准库支持std::hash<string>）。

树与图的存储

  • 邻接表：一般的选择
  • 邻接矩阵：占用空间大，仅适用于稠密图，对于随机访问边权有性能优势（$O(1)$​）；*不能存重边

邻接表：

1
2
3
4
5
6
7

const int N = 100005, M = 2* N; // 树：有向边数 = 2*(n-1)

int h[N], e[M], ne[M], idx;

void add(int a, int b) { // 建边： a -> b
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

拓扑排序

  • 可以用来判断图中是否有环（包括自环）
  • 可以生成一个DAG的拓扑序

步骤：

  1. 所有入度为0的点入队
  2. 进行BFS（仅当入度减为0时入队）
  3. BFS中队列入队顺序就是拓扑序

最短路

图论题：

  1. 抽象为图论问题，建图 *难点
  2. 利用算法模板求解

最短路算法的选择

image-20240221125709394

经测试，在稠密图数据下，堆优化/朴素Dijkstra时间差别不大；当然还是选最合适的用更好。

Floyd虽然复杂度较高，但常数很小（仅一条语句）。

朴素Dijkstra

时间复杂度$O(n^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

const int N = 510, INF = 0x3f3f3f3f;

int g[N][N]; // 邻接矩阵存图
int d[N];
bool st[N]; // 点是否在集合s中
int n, m;

int dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i=1; i<=n; i++) {
        int t = -1;
        for (int j=1; j<=n; j++) { // 找当前最小距离的节点
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        }
        st[t] = true;
        for (int j=1; j<=n; j++) // 松弛
            d[j] = min(d[j], d[t] + g[t][j]);
    }
    
    if (d[n] == INF) return -1;
    return d[n];
}

堆优化的Dijkstra

时间复杂度$O(m \log 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

const int N = 150010;

typedef pair<int, int> PII;

int h[N], e[N], w[N], ne[N], idx; // 使用邻接表存图
int d[N];
bool st[N];
priority_queue<PII, vector<PII>, greater<PII>> q; // 存pair，第一分量存距离，第二分量存节点编号
int n, m;

int dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    q.push({0, 1});
    while (q.size()) {
        auto t = q.top(); // 取距离最近的点（可能有先前的冗余记录）
        q.pop();
        int ver = t.second, dis = t.first;
        if (st[ver]) continue; // 跳过先前的冗余记录
        st[ver] = true;
        for (int i=h[ver]; i!=-1; i=ne[i]) { // 松弛
            int u = e[i];
            if (dis+w[i] < d[u]) {
                d[u] = dis + w[i];
                q.push({d[u], u});
            }
        }
    }
    
    if (d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

Dijkstra算法假设图中没有负权边，只能处理非负权的情况。

Bellman-Ford

$n-1$次迭代，每次对所有边进行松弛操作。

可以实现求“最多经过k条边的最短路”。（SPFA也可以实现，只要维护好路径长度即可）

题目：有边数限制的最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

const int N = 510, M = 10010;

struct {
    int a, b, w;
} edges[M]; // 由于算法只单纯枚举边，不需拓扑信息，可使用结构体数组存图

int n, m, k;
int d[N], backup[N]; // backup[] 保存上次迭代结果，防止在一次迭代内部发生“串联”

int bellman_ford() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i=1; i<=k; i++) { // k 次迭代
        memcpy(backup, d, sizeof d); // 保存上次迭代结果
        for (int j=0; j<m; j++) {
            int a=edges[j].a, b=edges[j].b, w=edges[j].w;
            d[b] = min(d[b], backup[a]+w);
        }
    }
    return d[n];
}

SPFA

优化的Bellman-Ford算法，基于每次迭代实际上不会松弛所有边，只可能会松弛上次更新节点的邻接边。

时间复杂度一般$O(m)$，若被卡最坏$O(nm)$​（网格状图）。如果不被卡，有时甚至比Dijkstra还快。

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

const int N = 100010;

int h[N], w[N], e[N], ne[N], idx; // 不同于BF算法，需使用邻接表存图
int dist[N];
int n, m;
queue<int> q;
bool st[N]; // 节点是否已在队列中，若已在则不需重复加入

int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q.push(1);
    st[1] = true;
    
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        
        for (int i=h[t]; i!=-1; i=ne[i]) {
            int u = e[i];
            if (dist[u] > dist[t] + w[i]) { // 仅当更新的点，才放入松弛队列
                dist[u] = dist[t] + w[i];
                if (!st[u]) {
                    q.push(u);
                    st[u] = true;
                }
            }
        }
    }
    
    return dist[n];
}

与Dijkstra的对比

SPFA与Dijkstra有些类似，都是类似于BFS的操作。但不同之处在于：

  • Dijkstra基于贪心策略，每次迭代选择一个距离最近的点进行标记，然后松弛它的所有邻接边；且一旦被标记，最小距离就不再改变
  • SPFA逐层进行松弛，之前松驰过的点还可能再次被松弛

SPFA求负环

添加一虚拟源点，向其他所有点连一权重为0的边，则该图存在负环等价于原图存在负环。

同时设置一cnt[]数组，统计虚拟源点到该节点的跳数。若cnt[x]>=n，则说明最短路上至少有n+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
32
33

const int N = 2010, M = 10010;

int h[N], e[M], w[M], ne[M], idx;
queue<int> q;
bool st[N];
int dist[N], cnt[N]; // dist[] 存储各个节点到虚拟源点的最短路距离，初始值全为0
int n, m;

bool spfa() {
    for (int i=1; i<=n; i++) {
        q.push(i);
        st[i] = true;
    }
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        
        for (int i=h[t]; i!=-1; i=ne[i]) {
            int u = e[i];
            if (dist[u] > dist[t] + w[i]) { // 在一开始，只有负权边会使该条件成立，故减少了队列中节点数，提高判断负环速度
                dist[u] = dist[t] + w[i];
                cnt[u] = cnt[t] + 1; // 维护最短路径跳数
                if (cnt[u] >= n) return true;
                if (!st[u]) {
                    q.push(u);
                    st[u] = true;
                }
            }
        }
    }
    return false;
}

Floyd

基于动态规划思想。

d[k, i, j] 表示只经过点1~k，i与j间的最短距离。

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

const int N = 210, INF = 0x3f3f3f3f;

int d[N][N];
int n, m, Q;

void floyd() {
    for (int k=1; k<=n; k++) // 第 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]);
}

int main() {
    scanf("%d%d%d", &n, &m, &Q);
    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;
    
    for (int i=1; i<=m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        d[x][y] = min(d[x][y], z);
    }
    
    floyd();
    
    while (Q --) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (d[x][y] > INF / 2) puts("impossible"); // 对不可到达的点，可能有负边，导致距离稍微小于INF
        else printf("%d\n", d[x][y]);
    }
}

最小生成树

image-20240222182341271

最小生成树问题只考虑无向图，故存图需存双向边。

朴素Prim算法

从一个节点开始，“逐渐生长”成一棵树。时间复杂度$O(n^2)$，适合稠密图。

dist[]数组的意义：点到“集合”的距离

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

const int N = 510, INF = 0x3f3f3f3f;

int g[N][N];
int dist[N];
bool st[N];
int n, m;

int prim() {
    int ans = 0;
    memset(dist, 0x3f, sizeof dist);
    for (int i=0; i<n; i++) {
        int t = -1;
        for (int j=1; j<=n; j++) 
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        if (i && dist[t] == INF) return INF; // 不连通，无最小生成树
        st[t] = true;
        if (i) ans += dist[t]; // 在更新距离前更新答案，以正确处理自环
        
        for (int j=1; j<=n; j++)  // 维护点到集合的距离
            dist[j] = min(dist[j], g[t][j]);
    }
    return ans;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g); // 全部初始化为INF
    for (int i=0; i<m; i++) {
        int a,  b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c); // !! 无向图存双向边
    }
    
    int ans = prim();
    if (ans == INF) puts("impossible");
    else printf("%d", ans);
}

对于重边和自环的处理：

  • 重边在邻接矩阵中存最小值即可
  • 自环可以选择：不存（默认值INF）；或在Prim算法中注意顺序，先累加答案，再更新邻接点距离

Kruskal算法

“逐渐合并”成一棵树。时间复杂度$O(m \log m)$，适合稀疏图。

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

const int N = 100010, M = 200010;

int p[N];
struct Edge{ // 使用结构体数组存边
    int a, b, w;
    bool operator<(const Edge &e) {
        return w < e.w;
    }
} edges[M];
int n, m;

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

int main(){
    cin >> n >> m;
    for (int i=0; i<m; i++)
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    for (int i=1; i<=n; i++)
        p[i] = i;
    
    // Kruskal:
    sort(edges, edges+m); // 从小到大排序边
    
    int ans = 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) {
            ans += w;
            p[b] = a;
            cnt ++;
        }
    }
    if (cnt == n-1) printf("%d", ans);
    else puts("impossible");
}

重边和自环的处理：并查集自动判断。

二分图

显然：一个图是二分图，当且仅当图可被2-染色。

定理：一个图是二分图，当且仅当图中不存在奇数环。

证明

必要性：反证。假设存在奇数环，可画图发现，一定有在同一半边的边。

充分性：想象对图进行DFS 2-染色，若不存在奇数环，则在DFS过程中一定不存在矛盾。可以反证：假设存在矛盾，则图中一定有奇数环。

染色法判断二分图

使用color[]数组标记节点：0-未染色，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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

const int N = 100010, M = 200010;

int h[N], e[M], ne[M], idx;
int n, m;
int color[N];

bool dfs(int x, int c) {
    color[x] = c;
    for (int i=h[x]; i!=-1; i=ne[i]) {
        int u = e[i];
        if (!color[u]) {
            if (!dfs(u, 3-c)) return false;
        } else if (color[u] == c) 
            return false;
    }
    return true;
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    
    for (int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    bool flag = true;
    for (int i=1; i<=n; i++) {
        if (!color[i]) {
            if (!dfs(i, 1)) {
                flag = false;
                break;
            }
        }
    }
    
    if (flag) puts("Yes");
    else puts("No");
}

题目：关押罪犯

二分+染色法判断二分图

  • 思路一：先对边排序，对边的序号二分
  • 思路二：直接对答案二分（yxc）

技巧：dfs时枚举临界点时可限制权重，以达到“删边”的效果。

正确性证明：考虑二分边界，反证法

心得：

  • 有时候很可惜，思路对了就差一小步做不出来（无向图忘加双向边）
  • 代码比较复杂的情况下，可能不好分辨、调试：是思路错了，还是代码有bug？
  • 写代码要细心，优先级：正确性、可读性 » 效率
  • 在对思路有自信的情况下（可以证明），若结果仍不对，可以沉下心来一行一行地检查、思量代码，或许能发现bug

匈牙利算法求二分图的最大匹配

可以用只有单向边（左到右）的邻接表表示二分图，左、右两边的节点编号均从1开始。

st[]数组表示一轮匹配中，右侧已经被考虑过的节点。递归过程中，上层考虑过的节点不再进行考虑，因为上层可能正考虑匹配该节点，同时防止死循环。

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

const int N = 510, M = 100010;

int h[N], e[M], ne[M], idx; // 仅存储左侧指向右侧的边
int match[N]; // 当前右侧节点匹配的左侧节点
bool st[N];
int n1, n2, m;

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

void add(int x, int y) {
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

int main(){
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h);
    
    for (int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }
    
    int ans = 0;
    for (int i=1; i<=n1; i++) {
        memset(st, false, sizeof st);
        if (find(i)) ans++;
    }
    cout << ans << endl;
}

练习：棋盘覆盖

笔记
Acwing算法基础课
本文由作者按照 CC BY 4.0 进行授权