搜索与图论

DFS 深度优先搜索

数据结构 空间复杂度 特性
DFS stack $O(h)$ 不具有“最短路”特性
BFS queue $O(2^h)$ 具有“最短路”特性

DFS俗称“暴搜”，思考问题时最重要的是想清楚搜索的顺序，要确定用什么样的顺序来把问题的所有方案全部遍历一遍比较方便。

每个DFS都对应一个搜索树，当比较难思考时，就从搜索树的角度来思考。通过画图可以帮助我们理解。

DFS是一种递归，不用将DFS和递归区分

DFS的两个重要概念是是回溯、剪枝

回溯是指从深层回退的过程，回溯时的关键是回溯时必须“恢复现场”，会到原有的状态。

算法思路比较奇怪的或对空间要求比较高的一般用DFS而不用BFS

深搜会一条路走到黑，往深层搜索。

深搜空间复杂度低的原因，是因为深搜只需要同时存储一条路径。

DFS+存储即记忆化搜索

AcWing 842. 排列数字

本题的搜索顺序是对空着的位置从左到右一个一个填。第k层对应于第k个位置。限制条件是当前位填写的数不能和前面的数相同，可以使用标记数组记录好已经用过的数。

回溯使用系统栈实现。回溯时要考虑是否需要恢复现场，如果递归时状态发生改变，下一轮递归需要用到原状态，就要恢复现场。

每层递归中要遍历所有子节点，并对每个子节点进行递归深入。

image-20230402151231043

朴素算法

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
// DFS——AcWing 842. 排列数字
// 搜索顺序：本题的搜索顺序是对空着的位置从左到右一个一个填。第k层对应于第k个位置。
#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N]; // 存储路径
bool st[N];
// 传递u标记当前深度
void dfs(int u){
    if (u == n){ // u == n时为叶子节点
        for (int i = 0; i < n ; ++ i)
            printf("%d ", path[i]);
        puts("");
    }

    for (int i = 1; i <= n ; ++ i)
    // 遍历所有可能
        if (!st[i]){
            path[u] = i;
            st[i] = true;
            // 进入递归前修改状态，标记已用过
            dfs(u + 1);
            st[i] = false;
            // 在从递归里出来后，即为回溯，要恢复现场
            // p[u]会被覆盖，因而不用恢复
        }
}

int main(){
    scanf("%d", &n);

    dfs(0); // 从根节点开始
    return 0;
}

优化：使用状态压缩表示

组合问题的状态可以用二进制压缩

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
// DFS + 状态压缩——AcWing 842. 排列数字
// 搜索顺序：本题的搜索顺序是对空着的位置从左到右一个一个填。第k层对应于第k个位置。
#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N];

void dfs(int u, int state){
    if (u == n){
        for (int i = 0; i < n; ++ i)
            printf("%d ", path[i]);
        puts("");
        return ;
    }
    // 使用state状态压缩，每一位表示对应的数是否被用过
    // 初始时state为0，表示没有任何数被选过

    for (int i = 0; i < n; ++ i)
        if (!(state >> i & 1)){
            // 取state的第i+1位，为i+1说明已经用过
            path[u] = i + 1;
            dfs(u +1, state + ( 1 << i));
            // 1 << i 使第i + 1 位为1，也相当于求2^i
            // state加上 1 << i即使state第i + 1位变为1
            // state的值没有变，因而回溯时不用恢复现场
        }
}

int main(){
    scanf("%d", &n);
    dfs(0, 0);
    return 0;
}

AcWing 843. n-皇后问题

第一种搜索顺序：一个方格一个方格地搜索（先左后右，先上后下）

需要注意约束条件，标记每一行、每一列、每一对角线是否存在皇后（是否能摆放）。

注意如何表示对角线: 注意到每条线的截距不同，因为可用截距来表示对角线，两侧的对角线分别用一个数组存。

  • y = x + b –> b = y - x – > b = y - x + n
    (由于数组下标不能为负数，所以增加一个偏移量n，仍满足一一对应)

  • y = -x + b --> b = x + y

image-20230402153641062

每层递归内部要枚举子节点的所有选择情况。

这种搜索顺序枚举了每个格子的两种可能状态，比较麻烦费时。

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
54
// DFS——AcWing 843. n-皇后问题
// 搜索顺序：一个方格一个方格地搜索（先左后右，先上后下）
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int n;
bool row[N], col[N], dg[N * 2], udg[N * 2];
// 标记每一行、每一列、每一对角线是否存在皇后（是否能摆放）
char g[N][N];

void dfs(int x, int y , int s){
    if (s > n) return ;

    if ( y == n) y = 0, x ++; // 处理越界问题

    if (x == n){
        if (s == n){
            for (int i = 0; i < n; ++ i) puts(g[i]);
                puts("");
        }
        return;
    }
    
    g[x][y] = '.';
    // 此方案中会枚举每个格子，所以在枚举时初始化即可，不用提前初始化
    
    // 枚举当前格子的两种可能的选择状态
    // 不放皇后
    dfs(x, y + 1, s);
    
    // 放皇后，需判断可不可以
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]){
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        g[x][y] = 'Q';
        // 更新标记

        dfs(x, y + 1, s + 1);

        g[x][y] = '.';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        // 回溯时要恢复现场
    }
}
int main(){
    cin >> n;

    dfs(0, 0, 0);

    return 0;
}

第二种搜索顺序

搜索顺序的选取和状态的选取是相关的，每个状态都对应一个节点，所有状态构成了搜索树。对于内部搜索问题，每个状态节点都对应于题目二维图中的真实方格。对于外部搜索为题，每个状态节点对应于通过操作变换的状态图中得到的状态。题目的限制条件除了显式的限制搜索顺序（如八连通、四连通等），还通过对合法状态的限制影响状态的选取和表示，并间接影响搜索顺序。这也可以理解成一种预先的可行性剪枝。

由题意，每一行最多只能放一个皇后且必须放一个皇后，因此可以将每行整体视为一个状态而不用一个一个方格取讨论。这时候对于每个状态，讨论的不再是每个方格是否放了皇后而是每行皇后放在第几个位置，状态只用记录当前行皇后所在列位置。这相当于按照全排列的思路进行搜索。因而只用按照行序一行一行进行搜索。此时按照约束枚举每一位的可能的值。将二维降成一维。

搜索树的每个节点对应于一个具体状态，每一层则对应一个抽象状态——即操作和讨论对象。

搜索时要注意剪枝。剪枝分为最优性剪枝和可行性剪枝，提前判断当前方案一定不是最优或一定不合法，直接回溯。

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
// DFS——AcWing 843. n-皇后问题
// 搜索顺序：类似全排列的搜索思想，按照行序一行一行进行搜索
// 整体的搜索是一维，但每次具体的搜索也是一个一维枚举
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u){
    if (u == n){
        for (int i = 0; i < n; ++ i) puts(g[i]);
        puts("");
        return;
    }

    for (int i = 0; i < n; ++ i)
    // 枚举所有子节点——枚举每行的位置所有选择情况
        if (!col[i] && !dg[u + i] && !udg[n - u + i]){
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true; 
            // 更新标记
            dfs(u + 1); 
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
            // 回溯时要恢复现场
        }
}

int main(){
    cin >> n;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < n; ++ j)
            g[i][j] = '.';
    
    dfs(0);
    return 0;
}

BFS 广（宽）度优先搜索

BFS是一层一层来搜的，当图的路径权值相同时，BFS具有“最短路”特性（边权相同时才能用BFS求解最短路问题）。此时涉及最小步数、最短距离、最少操作次数的问题基本上都可以用BFS

dp问题和最短路问题是互通的，dp问题可以看成一种特殊的最短路问题，是没有环存在的最短路问题。

记忆化搜索即深搜+存储。

最短路问题包括用最短路算法求解的题，BFS求解的题，dp求解的题。

BFS的基本框架：

1
2
3
4
5
queue <- 初始状态（入队列）
while queue不空{
    取出队头
    拓展队头
}

AcWing 844. 走迷宫

自己手写队列

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// AcWing 844. 走迷宫
// 当图的路径权值相同时，BFS具有“最短路”特性。
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N]; // 存图（01状态）
int d[N][N]; // 存到起点的距离
PII q[N * N]; 
// 入队列元素有两个属性x, y，注意元素总个数为N*N

int bfs(){

    int hh = 0, tt = -1;
    // 分别标记队列要取出结点的位置，存取结点的前一个位置
    
    memset(d, -1, sizeof d);
    // 初始化为-1，可用于标记是否已经走过

    d[0][0] = 0;// 初始化起始点

    q[++ tt] = {0, 0};// 初始状态入队列

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    // 常用技巧：使用偏移量表示向四个方向的移动
    // 本质上是用向量提前表示出所有移动方向，再枚举（因为移动方向是固定的）

    while (hh <= tt) // 队列不为空
    {
        auto t = q[hh ++]; // 取出队头元素


        // 拓展队列元素
        // 枚举所有可能的移动方向
        for (int i = 0; i < 4; ++ i)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            // 要判断该点是否能走，是否已经被走过，是否越界了
            if (g[x][y] == 0 && d[x][y] == -1 && x >= 0 && x < n && y >= 0 && y < m){
                d[x][y] = d[t.first][t.second] + 1;
                q[++ tt] = {x, y};
                // 更新状态并入队列
            }
        }
    }
    return d[n-1][m-1];
}

int main(){
    cin >> n >> m;

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            cin >> g[i][j];
    
    cout << bfs() << endl;
}

int bfs(){
    int hh = 0, tt = -1;

    memset(d, -1, sizeof d);

    d[0][0] = 0;

    q[++ tt] = {0, 0};

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (hh <= tt){
        auto t = q[hh ++];

        for (int i = 0; i < 4; ++ i)
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (g[x][y] == 0 && d[x][y] == -1 && x >= 0 && x < n &&  y >= 0 && y < m){
                d[x][y] = d[t.first][t.second] + 1;
                q[++ tt] = {x, y};
            }
        }
    }
    return d[n - 1][m - 1];
}

int bfs(){
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (hh <= tt){
        auto t = q[hh ++];

        for (int i  = 0; i < 4; ++ i){
            int x = t.first + dx[i], y = t.second + dy[i];

            if (g[x][y] == 0 && d[x][y] == -1 && x >= 0 && x < n && y >= 0 && y < m){
                d[x][y] = d.[t.first][t.second] + 1;
                q[++ tt] = {x, y};
            }
        }
    }
}

int bfs(){
    int hh = 0, tt = -1;

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q[++ tt] = {0, 0};
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while (hh <= tt){
        auto t = q[hh ++];

        for (int i = 0; i < 4; ++ i){
            int x = t.first + dx[i], y = t.second + dy[i];

            if (g[x][y] == 0 && d[x][y] == -1 && x >= 0 && x < n && y >= 0 && y < m){
                d[x][y] = d[t.first][t.second] + 1;
                q[++ tt] = {x, y};
            }
        }
    }
    return d[n - 1][m - 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// BFS——内部搜索——AcWing 844. 走迷宫
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N]; // 存图（01状态）
int d[N][N]; // 存到起点的距离
queue<PII> q; 
// 入队列元素有两个属性x, y，注意元素总个数为N*N

int bfs(){
    memset(d, -1, sizeof d);
    // 初始化为-1，可用于标记是否已经走过

    d[0][0] = 0;// 初始化起始点

    q.push(make_pair(0, 0));// 初始状态入队列
    // q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    // 常用技巧：使用偏移量表示向四个方向的移动
    // 本质上是用向量提前表示出所有移动方向，再枚举（因为移动方向是固定的）

    while (q.size()) // 队列不为空
    {
        auto t = q.front(); // 取出队头元素
        q.pop();

        // 拓展队列元素
        // 枚举所有可能的移动方向
        for (int i = 0; i < 4; ++ i)
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            // 要判断该点是否能走，是否已经被走过，是否越界了
            if (g[x][y] == 0 && d[x][y] == -1 && x >= 0 && x < n && y >= 0 && y < m){
                d[x][y] = d[t.first][t.second] + 1;
                q.push(make_pair(x, y));
                // 更新状态并入队列
            }
        }
    }
    return d[n-1][m-1];
}

int main(){
    cin >> n >> m;

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            cin >> g[i][j];
    
    cout << bfs() << endl;
}

AcWing 845. 八数码

本题是一个重点要掌握的外部搜索的的题。外部表示往往涉及状态表示和状态转移。

本题的两大难点：

  1. 状态表示

  • 如何把状态放到队列里

  • 如何记录每个状态的距离

  1. 状态转移

本题状态表示比较复杂，每个状态都是一个3 X 3的小矩阵。一种比较简单的方式是使用字符串来表示状态，将二维矩阵转化为一维字符串（展成一行）。入队时使用queue queue，记录距离时使用哈希表unorrdered_map<string, int> dist。

在进行状态转移时，首先将字符串变回矩阵（可以是想象的），然后进行转移——枚举上下左右，最后将矩阵再变回字符串。

这里要用到一个常用技巧：二维坐标与一维坐标的转换。设矩阵大小为n X m，元素二维坐标为(x, y)(x为行号，y为列号)，一维坐标是k，则：$$x = k / n, y = k % n$$
$$ k = x * n + y$$

注意这里要求一维序列和二维矩阵都要从0开始计数。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// BFS——外部搜索——AcWing 845. 八数码
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

int bfs(string state)
{
    queue<string> q; // 队列
    unordered_map<string, int> d; // 存储距离的哈希表

    q.push(state); // 初始状态入栈
    d[state] = 0; // 标记

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    // 偏移量表示四种移动方向

    string end = "12345678x";
    // 终止状态
    // 注意使用字符串表示状态，将二维矩阵转化为一维来表示

    while (q.size()) // 队列不为空
    {
        auto t = q.front();
        // 注意t是字符串，用于表示状态
        q.pop();
        // 取出队头元素

        if (t == end) return d[t];
        // 判断是否为终止状态

        int distance = d[t];
        int k = t.find('x');
        // 使用string的find函数找到x的一维坐标位置
        int x = k / 3, y = k % 3;
        // 转换二维矩阵中的二维坐标

        // 遍历所以移动方向
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            // 判断是否越界
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[a * 3 + b], t[k]);
                // 求出待移动元素的一维坐标，并进行交换，得到新的状态
                if (!d.count(t)) // 判断是否被搜索过，使用map的count函数
                {
                    d[t] = distance + 1;
                    q.push(t);
                    // 入队
                }
                swap(t[a * 3 + b], t[k]);
                // 由于当前状态已被改变，需要恢复现场
            }
        }
    }

    return -1;
}

int main()
{
    char s[2];// 应对空格和换行

    string state; 
    for (int i = 0; i < 9; i ++ )
    {
        cin >> s;
        state += *s;
        // 注意这种读取string 的方法
    }

    cout << bfs(state) << endl;

    return 0;
}



树和图的存储

树是一种特殊的图，是无环连通图，与图的存储方式相同。对于无向图中的边ab，存储两条有向边a->b, b->a。因此我们可以只考虑有向图的存储。

有向图存储：

  1. 邻接矩阵：开个二维数组，g[a, b]存储是否有边或边权，适合稠密图不能存储重边，空间复杂度为$O(N^2)$

  2. 邻接表：头结点数组 + n个单链表每个节点都对应一个单链表，单链表中存储当前结点直接指向的所有结点（有边），顺序可任意

image-20230402161436289

1
2
3
4
5
6
7
8
9
10
11
12
13
// 对于每个点k，开一个单链表，存储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$ 表示边数

1
2
3
4
5
6
7
8
9
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);
    }
}

树的深度优先遍历的一大优点是能够可以算出每个子树的大小

AcWing 846. 树的重心

本题的难点在于充分研究连通块，挖掘其性质和规律，并由此确定搜索的顺序。这种涉及复杂思路的问题显然一般用DFS。

经研究，我们发现删除某节点后，其父节点往上的部分会做成一个连通块，以其子节点为根节点的子树会各自形成一个连通块。而父节点往上的部分又等于总结点数减去以当前结点为根节点的子树的所有节点数，即等于以当前结点子节点为根节点的所有子树结点数加1。

由此我们只需要计算每个结点子节点为根节点的子树各自的结点数即可。

考虑到DFS会按路径遍历，且从叶子节点递归回溯时可以求出路径上的结点数，故采用DFS遍历树。

树的深度优先遍历可以算出每个子树的大小，这得益于深度优先遍历会一个一个子树地遍历。

深度优先遍历的一个重点是在递归的过程中传递和存储信息。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// DFS遍历树和图——AcWing 846. 树的重心
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 100010, M = N * 2; 
// 注意无向边需要两倍的空间

int n;
int h[N], e[M], ne[M], idx;  // 邻接表
int ans = N; // 存储结果：各个连通块中点数的最大值的最小值
bool st[N]; // 标记是否走过，防止从子节点走到父节点

// 图的存储
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
    // 插入到头节点之后
}

int dfs(int u){
    st[u] = true; 
    // 递归即入栈，要进行标记

    int size = 0, sum = 0;
    // 这里也是边界条件，即当结点为叶节点时，size = 0, sum = 1（返回的是sum + 1）
    // 注意从递归的角度理解dfs的代码

    // 枚举所有子节点
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i]; 

        if (st[j]) continue;

        int s = dfs(j); 
        // 深入搜索，
        // 递归后更新相关量
        // s为以子节点为根节点的所有子树中结点数
        size = max(size, s);
        // size保留以子节点为根节点的所有子树中结点数最大者
        // 即断开本结点后，各子节点所在各个连通块中点数的最大值
        sum += s;
        // sum计算以当前结点为根节点的子树的所有结点数，但不包括根节点自身
        
    }

    // 
    size = max(size, n - sum - 1);
    ans = min(ans, size); // 更新各个连通块中点数的最大值的最小值

    return sum + 1; 
    // 返回以当前结点为根节点的子树的结点数，注意包括自身结点
    // 叶子节点时返回1
}

int main(){
    scanf("%d", &n);

    memset(h, -1, sizeof h);
    // 注意对头节点数组初始化为-1


    // 对图进行存储
    for (int i = 0; i < n - 1; ++ i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
        // 注意对于无向图要添加双向边
    }

    dfs(1);// 注意题目中结点的值至少为1

    printf("%d\n", ans);

    return 0;
}

这道题目边的方向是不确定的，所以还是需要将两个方向的边都建出来。在输入时，由于我们并不能确定DFS时搜索的方向，因此两个方向都需要创建出来。否则如果我们从1号点开始搜，但是建立边的时候，选择的方向是 2 -> 1，那么在DFS时就搜索不到2号点了。

在遍历一棵树的时候，即使是无向边，也可以将st[]数组去掉，只需要在dfs时传入父节点这个参数就可以了，这样就可以避免重新搜回父节点。

只要题目指明了父子关系，就可以省略st[]数组。无向树当根节点确定之后，每条边就有了方向，另一个方向就被忽略掉了。如果出现子节点循环到了父节点，会直接contine，不会再次访问到父节点从而出现死循环的。

树和图的广度优先遍历

注意树和图的深度优先和宽度优先搜索对于每个节点都只会搜索一层，需要标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
// 初始状态入队列

while (q.size()){
    // 取出队头
    int t = q.front();
    q.pop();

    // 拓展队头——拓展当前节点t的所有相邻点
    for (int i = h[t]; i != -1; i = ne[i]){
        int j = e[i]; // 取出结点的值
        if (!st[j]){
            st[j] = true; // 表示点j已经被遍历过
            更新信息， 如d[x] = d[t] + 1
            q.push(j); // 节点入队
        } 
    }
}

AcWing 847. 图中点的层次

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
54
55
56
57
58
59
60
61
62
// BFS遍历树和图AcWing 847. 图中点的层次
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];


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

void bfs(){
    int hh = 0, tt = -1;

    memset(d, -1, sizeof d);
    d[1] = 0;
    // 初始化
    
    q[++ tt] = 1;
    // 初始状态入队列

    while(hh <= tt){
        int t = q[hh ++];
        // 取出队头

        int j;
        // 遍历所有子节点，拓展队列
        for (int i = h[t]; i != -1; i = ne[i]){
            j = e[i];
            if (d[j] == -1){
                d[j] = d[t] + 1;
                if (j == n) break;
                q[++ tt] = j;
            }
        }
        if (j == n) break;
    }
    printf("%d\n", d[n]);
}

int main(){
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    for (int i = 0; i < m; ++ i){
        int a, b;
        scanf("%d%d",&a, &b);
        add(a, b);
    }

    bfs();
    return 0;
}

拓扑序列

拓扑序列是针对有向无环 图而言的。

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边$<u,v>∈E(G)$，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。

一个有向无环图至少存在一个入度为0的结点（指向该节点的边数为0）。可简单用反证法和抽屉原理证明。

因而有向无环图一定存在拓扑序列，称为拓扑图。不是有向无环图的一定不存在拓扑序列，因而拓扑排序也用来判断一个图是否存在环。

算法

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

  1. 先拿出所有入度为0的点入队

  2. 在原图中将它们删除此顶点及所有出边。改变子节点的度数。循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

拓扑序列不唯一。有时会要求输出字典序最小的方案，这时把queue改成priority_queue即可

所有边都是从前指向后的。

求有向图的拓扑序的图的宽度优先遍历的经典应用，使用BFS实现

时间复杂度 $O(n+m)$, n表示点数，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
bool topsort(){
    int hh = 0, tt = -1;
    // tt分别表示存入结点的前一个位置
    // hh表示取出结点的位置
    
	// 初始状态入队列——入度数为零的结点全部入队
    // 需预先求出所有点的入度，d[i] 存储点i的入度，在存边时直接更新即可
    for (int i = 1; i <= n; ++ i)
        if (!d[i]) 
            q[ ++ tt] = i; 

    while (hh <= tt){ // 队列不为空
        int t = q[hh ++]; 
        // 取出队头结点

        // 拓展队列中存入的结点
        // 枚举节点t的所有出边（相邻节点）
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];// 取出结点的值
            // 更新入度数——删除父节点——所有相邻节点度数减一
            d[j]--;
            // 度数为零则存入队列
            if (d[j] == 0) 
                q[ ++ tt] = j;
        }
    }

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

AcWing 848. 有向图的拓扑序列

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 拓扑排序——AcWing 848. 有向图的拓扑序列
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;// 邻接表
int d[N]; // 存储入度
int q[N];

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

bool topsort(){
    int hh = 0, tt = -1;
    // tt分别表示存入结点的前一个位置
    // hh表示取出结点的位置

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; ++ i)
        if (!d[i]) 
            q[ ++ tt] = i; 
        // 初始状态入队列
        // 入度数为零的结点全部入队

    while (hh <= tt){ // 队列不为空
        int t = q[hh ++]; 
        // 取出队头结点

        // 拓展队列中存入的结点
        // 枚举子节点
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];// 取出结点的值
            d[j]--;
            if (d[j] == 0) 
                q[ ++ tt] = j;
            // 先删除父节点（子节点度数减一）
            // 度数为零则存入队列
        }
    }

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

int main(){
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    for (int i = 0; i < m; ++ i){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b); // 添加边
        ++ d[b]; // 更新入度
    }

    if (topsort()){
        for (int i = 0; i < n; ++ i) printf("%d ", q[i]);
        puts("");
    }
    else puts("-1");

    return 0;
}

最短路问题

常见的最短路问题可分为两大类：

  1. 单源最短路问题求从一个点到其他所有点的最短距离。可以分为两类

    • 所有边的权重都是正数常用算法：
      • 朴素Dijkstra算法：$O(n^2)$，时间复杂度与边数无关，适用于稠密图。基于贪心
      • 堆优化版的Dijkstra算法：$O(mlogn)$，适用于稀疏图(如n和m相同数量级时，n表示点数，m表示边数)
    • 存在权重为负的边常用算法:
      • Bellman-Ford算法: $O(nm)$，基于离散数学知识
      • SPFA算法：平均复杂度为$O(m)$，最坏复杂度为$O(nm)$
        SPFA算法是对Bellman-Ford算法的优化，一般效率更高，但有些情况下无法使用，如对最短路经过的边数进行限制m <= k等时，只能用Bellman-Ford。

  2. 多源汇最短路源指源点，即起点。汇指汇点，即终点。多源汇即多个起点和终点。多源汇最短路问题会有多个询问，每次起点和终点不同，求最短距离。常用算法：

    • Floyd算法：时间复杂度为$O(n^3)$，基于动态规划

最短路问题的侧重点和难点在于建图，如何定义点和边，把原问题抽象成最短路问题，套用什么模板来做。

image-20230402173115379

朴素Dijkstra算法

稠密图用邻接矩阵来存

时间复杂是 $O(n^2+m)$, $n$表示点数，$m$表示边数

image-20230402174808904

image-20230402180923011

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

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra(){
    // 初始化
    // 最初将所有点距离初始为无穷大
    memset(dist, 0x3f, sizeof dist);
    // 起点到本身的距离为0
    dist[1] = 0;
    
    // 注意：st[1] = true; 这句代码不能写，否则后面执行会出问题；需要用起点去更新和它连通的点的距离

    // 迭代n次，求出所有点到起点的最短距离
    // 每次都确定一个点t到起点的最短距离，执行n-1次即可求出所有点到起点的最短距离
    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 == -1时dist[t] > dist[j]不会执行，从而会读取第一个没确定的点，而不用提前赋值
                t = j;
	    // if (t == n) break;
        // 用t更新其他点的距离
        for (int j = 1; j <= n; ++ j)
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

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

AcWing 849. Dijkstra求最短路 I

最短路问题中重边只保留最短的边，自环则直接删掉

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
54
55
56
57
58
59
// 单源最短路问题——朴素dijkstra算法——AcWing 849. Dijkstra求最短路 I  
// 所有边的权重都是正数，稠密图，使用朴素dijkstra算法，时间复杂度为O(n^2+m)
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];  // 存储每条边
// 稠密图用邻接矩阵来存
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    // 最初将所有点距离初始为无穷大
    dist[1] = 0;
    // 到本身的距离为0
    // 注意：st[1] = true;这句代码不能写，否则后面执行会出问题；需要用起点去更新和它连通的点的距离

    // 迭代n次，求出所有点到起点的最短距离
    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 == -1时dist[t] > dist[j]不会执行，从而会读取第一个没确定的点，而不用提前赋值
                t = j;
        // if (t == n) break;
        // 用t更新其他点的距离
        for (int j = 1; j <= n; ++ j)
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
        // dijkstra算法每次循环都能确定一个最短点，此点后续不用再更新
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
int main(){
    memset(g, 0x3f, sizeof g);
    // 初始化邻接矩阵
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m ;++ i){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        g[a][b] = min(g[a][b], w);
        // 重边只保留最短的边，自环则直接删掉
    }
    
    printf("%d\n", dijkstra());
    return 0;
}

Python

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
def main():
    n, m = map(int, input().split())
    # 为了处理重边问题，先初始化为无穷大
    g = [[float('inf')] * (n + 1) for _ in range(n+1)]
    
    def dijkstra():
        d = [float('inf')] * (n + 1)
        d[1] = 0
        st = set()
        
        for _ in range(n):
            t = -1
            for i in range(1, n + 1):
                if i not in st and (t == -1 or d[i] < d[t]):
                    t = i
            st.add(t)
            
            for i in range(1, n + 1):
                d[i] = min(d[i], d[t] + g[t][i])
            
        return d[-1] if d[-1] != float('inf') else -1
        
    for _ in range(m):
        a, b, w = map(int, input().split())
        g[a][b] = min(g[a][b], w)
        
    print(dijkstra())
    
if __name__ == "__main__":
    main()

堆优化版的Dijkstra算法

时间复杂度 $O(mlogn)$, $n$表示点数，$m$表示边数。适用于稀疏图，使用邻接表存储。

朴素版Dijkstra需要遍历所有点来找剩余点中到起点距离最小的点，这一步可以用堆来优化。

注意直接使用STL优先队列时，优先队列中不支持修改/删除任意元素，因此每次直接插入新的数而不进行删除，堆中会存在冗余，堆中可能存在个元素，导致复杂度变为$ O(mlogm) $ 。且需要判重。手写堆则不会出现这种状况（可以删除任意节点），保证堆中至多存在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
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <queue>
typedef pair<int, int> PII;
// 存储距离和节点编号，之所以存储编号是因为在堆中不存储则无法获知

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

// 求1号点到n号点的最短距离，如果不存在，则返回-1
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];
                // 用当前点更新其他点
                // 注意w是和邻接表一起存的，因为下标是i不是j
                heap.push({dist[j], j});
                // 更新后要入堆，更新说明还没确定，不更新则说明已经确定了
                // 会在多次迭代中重复入堆，产生冗余
            }
        }
    }

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

AcWing 850. Dijkstra求最短路 II

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// 单源最短路问题——堆优化版dijkstra算法——AcWing 850. Dijkstra求最短路 II
// 所有边的权重都是正数，稀疏图，使用堆优化版dijkstra算法，时间复杂度为O(mlogn)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N = 150010;

typedef pair<int, int> PII;
// 存储距离和节点编号，之所以存储编号是因为在堆中不存储则无法获知

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

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

// 求1号点到n号点的最短距离，如果不存在，则返回-1
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];
                // 用当前点更新其他点
                // 注意w是和邻接表一起存的，因为下标是i不是j
                heap.push({dist[j], j});
                // 更新后要入堆，更新说明还没确定，不更新则说明已经确定了
                // 会在多次迭代中重复入堆，产生冗余
            }
        }
    }

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

int main(){
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; ++ i){
        int a, b, c;
        scanf("%d%d%d", &a, & b, &c);
        add(a, b, c);
    }
    
    printf("%d\n", dijkstra());
    return 0;
}

Python

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
import heapq

def main():
    n, m = map(int, input().split())
    head = [-1] * (n+1)
    e = [0] * m
    ne = [0] * m
    w = [0] * m
    idx = 0
    st = set()

    def add(a, b, c):
        nonlocal idx
        e[idx] = b
        w[idx] = c
        ne[idx] = head[a]
        head[a] = idx
        idx += 1
        
    def dijksta():
        d = [float('inf') for _ in range(n+1)]
        d[1] = 0
        heap = []
        heapq.heappush(heap, (0, 1))
        while heap:
            dist, node = heapq.heappop(heap)
            if node in st:
                continue
            st.add(node)
            
            i = head[node]
            while i != -1:
                j = e[i]
                if d[j] > dist + w[i]:
                    d[j] = dist + w[i]
                    heapq.heappush(heap, (d[j], j))
                i = ne[i]
        if d[-1] == float('inf'):
            print(-1)
        else:
            print(d[-1])
                
    for _ in range(m):
        a, b, c = map(int, input().split())
        add(a, b, c)
    dijksta()
    
if __name__ == "__main__":
    main()

Python

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
# More Pythonic code:
from collections import defaultdict
from heapq import heappush, heappop

if __name__ == '__main__':
    n, m = map(int, input().split())
    graph = defaultdict(lambda: defaultdict(lambda: float('inf')))
    for _ in range(m):
        a, b, weight = map(int, input().split())
        graph[a][b] = min(graph[a][b], weight)
    dist = [float('inf')] * (n+1)
    dist[1] = 0
    heap = []
    heappush(heap, (0, 1))
    set_min = set()

    while heap:
        d, node = heappop(heap)
        if node in set_min:
            continue
        set_min.add(node)
        for adj_v in graph[node]:
            if dist[adj_v] > d + graph[node][adj_v]:
                dist[adj_v] = d + graph[node][adj_v]
                heappush(heap, (dist[adj_v], adj_v))

    res =  dist[-1] if dist[-1] != float('inf') else -1
    print(res)

Bellman-Ford算法

用于求带负权边的最短路问题。使用两重循环进行求解，不用显式存储整个图，只用把每个边及两端点存储即可。

求最短路问题的图中不能有负权回路，当存在负权回路时，会出现死循环，不存在最短路径（最短路径负无穷）。

Bellman-Ford算法可用来判断是否存在负权回路，如果当迭代n次后还有更新，由抽屉原理，说明存在负权回路。第k次迭代含义是从起点经过不超过k条边走到每个点的最短距离，n次迭代还有更新说明有路径存在n条边n+1个节点，说明有负权回路。

虽然Bellman-Ford算法可以判断负权回路，但复杂度比较高，因此一般不用此算法而是用SPFA算法判断负环。

对于有边数限制的最短路问题，只能用Bellman-Ford算法，而不能用SPFA算法。

时间复杂度 $O(nm)$, n表示点数，m表示边数

image-20230402234558495

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
int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge{     // 边，a表示出点，b表示入点，w表示边的权重
    int a, b, w;
}edges[M];
// 由于算法中只涉及边的两个端点和边权，只关心每条边，而不涉及图的路径问题，所以可以直接用结构体存边即可，不需要关心边之间的联系

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    // 最初将所有点距离初始为无穷大
    dist[1] = 0;

    // 由于我们只给出了起点的距离值dist[1]，其余都为无穷大，因而第i次迭代时都会更新到起点距离为i条边的所有结点
    // 所以迭代k次即可求出从起点点到任意点的最多经过 k 条边的最短距离

    // 迭代n-1次后即可求出任意点到起点最多经过n-1条边的最短距离。此时只要1和n是连通的，且路径上不存在负权回路，一定能求出两者间最短距离
    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。

    // 迭代n次，表示最多经过n条边
    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;
            // 每次更新所有边的尾端的距离
            // 如果距离大于就更新
            // 跟新的过程称为松弛操作
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }
    // 迭代n * m次，即得到起点到所有点的最短距离
    // 循环完后，对所有的边都满足dist[b] <= dist[a] + w，称为三角不等式


    if (dist[n] > 0x3f3f3f3f / 2) return -1;

    // 除以2的原因:
    // bellman_ford算法会对所有边都尝试进行更新，而由于图中存在负边，就可能出现一种情况——边的两端都是正无穷（距离起点无限远，不连通），但由于是负边，也会对尾端的正无穷进行更新，使其值减小
    // 而本题中由于数据范围k < 500，边权的绝对值 < 10000，所以正无穷至多减小5e6，
    // 因而除2即可保证识别出并连通的情况

    return dist[n];
}

AcWing 853. 有边数限制的最短路

本题因为有步数限制，所以即使有负权回路也会存在最短路径。所以可以使用Bellman-Ford算法，但有负环一定不能用SFPA算法

image-20230404162303138

串联问题

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 单源最短路径——bellman_ford算法——AcWing 853. 有边数限制的最短路
// 存在负权边，对边数有限制时，使用bellman_ford算法
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;// n表示点数，m表示边数
int dist[N], backup[N]; // dist[x]存储1到x的最短路距离
// backup用于备份上一次迭代时的所有dist
struct Edge{// 边，a表示出点，b表示入点，w表示边的权重
    int a, b, w;
}edges[M];
// 由于算法中只涉及边的两个端点和边权，只关心每条边，而不涉及图的路径问题，所以可以直接用结构体存边即可，不需要关心边之间的联系

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
void bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    // 最初将所有点距离初始为无穷大
    dist[1] = 0;

    // 枚举所有结点
    // 由于我们只给出了起点的距离值dist[1]，其余都为无穷大，因而第i次迭代时都会更新到起点距离为i条边的所有结点
    // 所以迭代k次即可求出从起点点到任意点的最多经过 k 条边的最短距离

    // 迭代n-1次后即可求出任意点到起点最多经过n-1条边的最短距离。此时只要1和n是连通的，且路径上不存在负权回路，一定能求出两者间最短距离
    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。

    // 迭代k次
    for (int i = 0; i < k; ++ i ){ 
        memcpy(backup, dist, sizeof dist); // 之所以进行备份是为了防止出现更新的串联

        // 虽然要求距离只能小于k条边（更新小于k次）但可能出现其他点在上一次迭代时已经更新了距离（每次迭代至少更新步长增加1的结点，但可能会更新更远的点，是更短的路径，但不满足步长限制）
        // 如1连接了2和3，边权分别为1、3，2也连接了3，边权为1，限制步长为1，则只能1->3。但由于会枚举所有边，所以在一次迭代中可能会多次更新，如1更新完2后，2又用更新完的距离去更新3
        // 为了防止这种多次更新的问题，我们就不直接使用dist()来更新，而是用迭代前的备份来更新，保证至多更新一步。
        
        // 为了满足边数的限制，必须保证每次迭代，各点都从上一轮直接相连的点的基础上更新，避免串联问题。为此更新时使用备份的上一轮的距离

        // 枚举所有边
        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], backup[a] + w);
            //backup[a]使更新后的dist[a]不会对dsit[b]产生影响，保证至多更新一步。
        }
    }
    // 迭代n * m次，即得到起点到所有点的最短距离
    // 循环完后，对所有的边都满足dist[b] <= dist[a] + w，称为三角不等式
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    
    for (int i = 0; i < m; ++ i){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }

    bellman_ford();
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);
    
    // 除以2的原因:
    // bellman_ford算法会对所有边都尝试进行更新，而由于图中存在负边，就可能出现一种情况——边的两端都是正无穷（距离起点无限远，不连通），但由于是负边，也会对尾端的正无穷进行更新，使其值减小
    // 而本题中由于数据范围k < 500，边权的绝对值 < 10000，所以正无穷至多减小5e6，
    // 因而除2即可保证识别出并连通的情况
    
    return 0;
}

Python

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
def main():
    n, m, k = map(int, input().split())
    edge = []
    dist = [float('inf')] * (n + 1)
    
    
    def Ballman_Ford():
        dist[1] = 0
        for _ in range(k):
            back_up = dist.copy()
            for j in range(m):
                a, b, w = edge[j]
                dist[b] = min(dist[b], back_up[a] + w)
                
            if back_up == dist:
                break
            
        if dist[n] == float('inf'):
            return "impossible"
        else:
            return dist[n]
            
    for i in range(m):
        a, b, w = map(int, input().split())
        edge.append([a, b, w])
        
    print(Ballman_Ford())
        
if __name__ == '__main__':
    main()

SPFA 算法

时间复杂度 平均情况下 $O(m)$，最坏情况下 $O(nm)$，$n$表示点数，$m$表示边数

SPFA算法使用队列优化Bellman-Ford算法。Bellman-Ford算法每次循环会尝试更新所有节点，但实际上只有上一轮被更新过的节点才会更新其他相邻点的距离，二没有更新过的节点不会更新其他相邻点。基于这一点，使用队列存储所有这一轮被更新的节点，并每次从队列取出已被更新的节点用于更新其他点。因此需要标记每个节点是否在队列中，初始时起点入队。

一定不能用于有负环的问题，也不能用于有边数限制的问题。

可以用于判断是否存在负环。

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

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
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[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                // 用当前节点距离更新子节点距离
                // 注意w是和邻接表一起存的，因为下标是i不是j
                if (!st[j]){   
                // 如果队列中已存在j，则不需要将j重复插入
                    q.push(j);
                    st[j] = true;
                    // 只有被更新过的结点才会入队
                    // 避免了无效的遍历和更新
                }
            }
        }
    }

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

AcWing 851. spfa求最短路

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// spfa算法——AcWing 851. spfa求最短路
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 100010;

int n, m; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中

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

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
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[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                // 用当前节点距离更新子节点距离
                // 注意w是和邻接表一起存的，因为下标是i不是j
                if (!st[j]){    
                // 如果队列中已存在j，则不需要将j重复插入
                    q.push(j);
                    st[j] = true;
                    // 只有被更新过的结点才会入队
                    // 避免了无效的遍历和更新
                }
            }
        }
    }
    return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m;++ i){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int t = spfa();
    if (t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);
    // 这个不需要因为队列里都是由起点更新到的点，不存在bellman-ford算法中未更新的点同样被边更新的情况。
    // spfa遵循了一个拓扑顺序，而bellman-ford算法没有
    return 0;
}

Python

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
from collections import deque

def main():
    n, m = map(int, input().split())
    dist = [float('inf')] * (n + 1)
    head = [-1] * (n + 1)
    e = [0] * m
    ne = [0] * m
    w = [0] * m
    idx = 0
    st  = [False] * (n + 1)
    
    def add(a, b, c):
        nonlocal idx
        e[idx] = b
        w[idx] = c
        ne[idx] = head[a]
        head[a] = idx
        idx += 1
        
    def spfa():
        q= deque()
        dist[1] = 0
        q.append(1)
        st[1] = True
        
        while q:
            t = q.popleft()
            st[t] = False
            
            i = head[t]
            while i != -1:
                j = e[i]
                if dist[j] > dist[t] + w[i]:
                    dist[j] = dist[t] + w[i]
                    if not st[j]:
                        st[j] = True
                        q.append(j)
                i = ne[i]
        if dist[n] == float('inf'):
            return "impossible"
        else:
            return dist[n]
    
    for _ in range(m):
        a, b, c = map(int, input().split())
        add(a, b, c)
    print(spfa())
            
if __name__ == "__main__":
    main()

SPFA判断图中是否存在负环

时间复杂度是$O(nm)$, n表示点数，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
40
41
42
43
44
int n, m;// 总点数
int h[N], w[M], e[M], ne[M], idx;// 邻接表存储所有边
int dist[N], cnt[N];// dist[x]存储1号点到x的最短距离
// cnt[x]存储1到x的最短路中经过的点数
bool st[N];// 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa(){
    // 不需要初始化dist数组（默认为0），因为有负权边和负环的化一定会更新相关路径
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在负环。

    queue<int> q;
    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; // 主要不是自身加1，而是在前一个点基础上加1
                // 更新路径结点数
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j]){
                    q.push(j);
                    st[j] = true;
                    // 入队列
                }
            }
        }
    }
    return false;
}

AcWing 852. spfa判断负环

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// spfa算法判断图中是否存在负环——AcWing 852. spfa判断负环
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

const int N = 2010, M = 10010;

int n, m;// 总点数
int h[N], w[M], e[M], ne[M], idx;// 邻接表存储所有边
int dist[N], cnt[N];// dist[x]存储1号点到x的最短距离
// cnt[x]存储1到x的最短路中经过的边数，当边数为n时说明经过n+1个点，说明有负环
bool st[N];// 存储每个点是否在队列中

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

// 如果存在负环，则返回true，否则返回false。
bool spfa(){
    // 不需要初始化dist数组（默认为0），因为有负权边和负环的化一定会更新相关路径
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在负环。

    queue<int> q;
    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;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j]){
                    q.push(j);
                    st[j] = true;
                    // 入队列
                }
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; ++ i){
        int a, b, c;
        scanf("%d%d%d", &a, &b,&c);
        add(a, b, c);
    }
    
    if (spfa()) puts("Yes");
    else puts("No");
    return 0;
}

Python

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
54
from collections import deque

def main():
    n, m = map(int, input().split())
    d = [0] * (n + 1) # 注意不要初始化为负无穷，因为判断的是有无负环，而不是求绝对距离
    # 要初始化为0，保证可更新
    head = [-1] * (n + 1)
    e = [0] * m
    ne = [0] * m
    w = [0] * m
    st = [False] * (n + 1)
    cnt = [0] * ( n + 1)
    idx = 0
    
    def add(a, b, c):
        nonlocal idx
        e[idx] = b
        ne[idx] = head[a]
        w[idx] = c
        head[a] = idx
        idx += 1
        
    def spfa():
        q = deque()
        # 主要所有节点都要入队列，还是因为负环的特殊性
        for i in range(1, n + 1):
            q.append(i)
            st[i] = True
        
        while q:
            t = q.popleft()
            st[t]= False
            
            i = head[t]
            while i != -1:
                j = e[i]
                if d[j] > d[t] + w[i]:
                    d[j] = d[t] + w[i] 
                    cnt[j] = cnt[t] + 1
                    if cnt[j] >= n:
                        return True
                    if not st[j]:
                        st[j] = True
                        q.append(j)
                i = ne[i]
        return False
        
    for _ in range(m):
        a, b, c = map(int, input().split())
        add(a, b, c)
    print("Yes" if spfa() else "No")
        
if __name__ == "__main__":
    main()

Floyd算法

时间复杂度是 $O(n^3)$, n表示点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
初始化：
    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;

// 算法结束后，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]);
                // 其实质是利用了动态规划和滚动数组
                // d[k, i, j] = d[k-1, i, k]  + d[k-1, k, j]
                // d[k,i,j]表示从i到j经过k的距离
}

AcWing 854. Floyd求最短路

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
54
55
56
// Floyd算法——AcWing 854. Floyd求最短路
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, M = 40010, INF = 0x3f3f3f3f;
int n, m, k;
int d[N][N];
// 算法结束后，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]);
                // 其实质是利用了动态规划和滚动数组
                // d[k, i, j] = d[k-1, i, k]  + d[k-1, k, j]
                // d[k,i,j]表示从i到j经过k的距离
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    
    // 初始化，将不同点之间的距离初始为正无穷
    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 = 0; i < m; ++ i){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        d[a][b] = min(d[a][b], w);
        // 注意重边问题
    }
    
    floyd();
    
    while(k--){
        int a, b;
        scanf("%d%d", &a, & b);
        
        int t = d[a][b];
        
        if (t > INF / 2) puts("impossible");
        else printf("%d\n", t);

        // 除以2的原因:
        // floyd算法会对所有边都尝试进行更新，而由于图中存在负边，就可能出现一种情况——边的两端都是正无穷（距离起点无限远，不连通），但由于是负边，也会对尾端的正无穷进行更新，使其值减小
        // 而本题中由于数据范围k < 40000，边权的绝对值 < 10000，所以正无穷至多减小4e8，
        // 因而除2即可保证识别出并连通的情况
    }
    return 0;
}

重边只保留最短的边，自环则直接删掉

Python

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
def main():
    n, m, k = map(int, input().split())
    # 注意有重边，需要初始化为inf
    g = [[float('inf')] * (n + 1) for _ in range(n + 1)]
    
    def Floyd():
        # 到自身的距离要赋值为0
        for i in range(1, n + 1):
            g[i][i] = 0
            
        for k in range(1, n + 1):
            for i in range(1, n + 1):
                for j in range(1, n + 1):
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    
    for _ in range(m):
        a, b, c = map(int, input().split())
        g[a][b] = min(g[a][b], c)
        
    Floyd()
    
    for _ in range(k):
        a, b = map(int, input().split())
        if g[a][b] == float('inf'):
            print("impossible")
        else:
            print(g[a][b])
            
if __name__ == "__main__":
    main()

最小生成树

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边(n-1条)。

最小生成树一般考察无向图，有向图一般不会用到，存边的时候需要存两次

难点也在于建图

常用算法

  • 普利姆算法（Prim)
    包括两个版本：

    • 朴素版Prim算法：用于稠密图，$O(n^2)$
    • 堆优化版的Prim算法：用于稀疏图，$O(mlogn)$。不常用，稀疏图更常用Kruskal算法

  • 克鲁斯卡尔算法（Kruskal）：$O(mlogm)$

朴素版prim算法

时间复杂度是 $O(n^2+m)$, n表示点数，m表示边数

算法流程：

  1. 输入：一个加权连通图，其中顶点集合为V，边集合为E；

  2. 初始化：$V_{new} = {x}$，其中x为集合V中的任一节点（起始点），$E_{new} = {}$,为空；

  3. 重复下列操作，直到$V_{new} = V$：

  • 在集合E中选取权值最小的边$<u, v>$，其中u为集合Vnew中的元素，而v不在$V_{new}$集合当中，并且$v∈V$（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

  • 将v加入集合$V_{new}$中，将$<u, v>$边加入集合$E_new$中；

  1. 输出：使用集合$V_{new}$和$E_{new}$来描述所得到的最小生成树。

Prim算法和Dijkstra算法非常相似，区别在于Dijkstra算法每次找到不在集合内的距离起点最近的点，并用其更新其他点到起点的距离。而Prim算法每次找到不在集合内的距离起点最近的点，并用其更新其他点到集合的距离。Dijkstra算法起始时默认起点已经在集合中，只需迭代n-1次。Prim算法初始时集合为空，所有点到集合距离初始化为正无穷，要迭代n次，且起点可以随机取。

注意Prim算法可以用于有负权边的图，而Dijkstra算法不能。

全局贪心

image-20230404173346134

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

// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){
    memset(dist, 0x3f, sizeof dist);

    int res = 0;// 记录距离之和
    // 初始时选择任意一点——这里默认最开始选择编号为1的点
    // 注意i从0开始，要迭代n次，且会用到0的特殊性
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        // 找到到集合的距离最近的点
        for (int j = 1; j <= n; j ++ )
        // 注意j编号从1开始——节点标号从1开始
            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;
        // 加入到集合中
        // 先累加再更新，防止有负自环时，先更新会改变dist[t]的值（自己更新自己）

        // 用t更新其他点到集合的距离，注意不是到某个特定点的距离
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
        // 所谓到集合的距离即到集合中的所有点的距离的最小值，即最小的边长
        // 由于点是迭代加入集合的，所以每加入一个点，只用多考虑其和其他点之间的边，取最小即可
    }

    return res;
}

AcWing 858. Prim算法求最小生成树

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// 朴素版prim算法——AcWing 858. Prim算法求最小生成树
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510;
const int INF = 0x3f3f3f3f;

int n, m;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){
    memset(dist, 0x3f, sizeof dist);

    int res = 0;// 记录距离之和
    // 初始时选择任意一点——这里默认最开始选择编号为1的点

    for (int i = 0; i < n; i ++ ){
    // 注意i从0开始，要迭代n次，且会用到0的特殊性
        int t = -1;
        // 找到到集合的距离最近的点
        for (int j = 1; j <= n; j ++ )
        // 注意j编号从1开始——节点标号从1开始
            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;
        // 加入到集合中
        // 先累加再更新，防止有负自环时，先更新会改变dist[t]的值（自己更新自己）

        // 用t更新其他点到集合的距离，注意不是到某个特定点的距离
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
        // 所谓到集合的距离即到集合中的所有点的距离的最小值，即最小的边长
        // 由于点是迭代加入集合的，所以每加入一个点，只用多考虑其和其他点之间的边，取最小即可
    }

    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    
    memset(g, 0x3f, sizeof g);
    // 邻接矩阵初始化
    
    for (int i = 0; i < m; ++ i){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        g[a][b] = g[b][a] = min(g[a][b], w);
        // 注意是无向图
    }
    int t = prim();
    if ( t == INF) puts("impossible");
    else printf("%d\n", t);
    return 0;
}

Python

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
def main():
    n, m = map(int, input().split())
    g = [[float('inf')] * (n + 1) for _ in range(n + 1)]
    st = [False] * (n + 1)
    dist = [float('inf')] * (n + 1)
    
    def Prim():
        res = 0
        dist[1] = 0
        for i in range(n):
            t = -1
            for j in range(1, n + 1):
                if not st[j] and (t == -1 or dist[t] > dist[j]):
                    t = j
            # 判断孤立点
            if dist[t] == float('inf'):
                return print("impossible")
            
            res += dist[t]
            st[t] = True
        
            for i in range(1, n + 1):
                dist[i] = min(dist[i], g[t][i])
        
        return print(res)
        
    for _ in range(m):
        a, b, c = map(int, input().split())
        # 注意本题是无向图，需要同时添加两条边
        g[b][a] = g[a][b] = min(g[a][b], c)
    Prim()
    
if __name__ == "__main__":
    main()

堆优化版的Prim算法

把求最小值这一步从遍历变成由堆来优化

克鲁斯卡尔算法（Kruskal）：

从小到大排序，时间主要花在排序上

时间复杂度是$O(mlogm)$, n表示点数，m表示边数

基本思想是：假设连通网G=(V,E)，令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，概述图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。

步骤：

  1. 将所有边按权重从小到大排序($O(mlogm))

  2. 枚举每条边<a, b>，如果a，b不连通，则将这条边加入集合中

第二步可以使用并查集来实现

image-20230404173241962

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
int n, m;       // 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;
    // res存储最小生成树所有树边的权重之和，cnt存储当前加入集合的边数

    // 从小到大枚举所有边
    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;
}

AcWing 859. Kruskal算法求最小生成树

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// 克鲁斯卡尔算法（Kruskal）——AcWing 859. Kruskal算法求最小生成树
// 排序 + 并查集合并集合
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010, M = 200010;
const int INF = 0x3f3f3f3f;

int n, m;       // 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;    
    // 初始化并查集（每个结点一个集合）
    // 注意节点编号从1开始

    int res = 0, cnt = 0;
    // res存储最小生成树所有树边的权重之和，cnt存储当前加入集合的边数

    // 从小到大枚举所有边
    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;
}
int main(){
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < m; ++ i){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }
    
    int t = kruskal();
    if (t == INF) puts("impossible");
    else printf("%d\n", t);
    return 0;
}

Python

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
def main():
    n, m = map(int, input().split())
    edge = []
    p = [0] * (n + 1)
    
    def find(x):
        if x != p[x]:
            p[x] = find(p[x])
        return p[x]
        
    def Kruskal():
        nonlocal edge
        res = 0
        cnt = 0
        
        edge = sorted(edge, key=lambda s: s[2])
        
        for i in range(m):
            a, b, c = edge[i]
            a = find(a)
            b = find(b)
            if a != b:
                res += c
                # 合并集合
                p[b] = a
                cnt += 1
        if cnt != n - 1:
            return "impossible"
        else:
            return res
            
    for _ in range(m):
        a, b, c = map(int, input().split())
        edge.append([a, b, c])
    # 注意并查集的初始化    
    for i in range(1, n + 1):
        p[i] = i
        
    print(Kruskal())
            
if __name__ == "__main__":
    main()

二分图

常用算法：

  • 染色法：$O(n+m)$，用于判别是否为二分图，实质就是dfs

  • 匈牙利算法：$O(mn)$，实际运行时间一般远小于$O(mn)$，用于求二分图的最大匹配

染色法判别二分图

时间复杂度是 $O(n+m)$, n表示点数，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
40
41
int n;// n表示点数
int h[N], e[M], ne[M], idx;// 邻接表存储图
// 注意e[]和ne[]存的是边数，大小为M
int color[N];// 表示每个点的颜色，0表示未染色，1表示白色，2表示黑色

// 参数：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]){
            if (!dfs(j, 3 - c)) return false;
            // 进行染色，注意染相反的颜色
            // 这里由于两种颜色分别为1、2，所以用3 - c来表示相反颜色
        }
        else if (color[j] == c) return false;
        // 已经被染色，且染的相同颜色，则染色失败，不是二部图
    }

    return true;
}

bool check(){
    // 枚举所有节点，进行染色
    for (int i = 1; i <= n; i ++ )
    // 注意点的编号从1开始
        if (!color[i])
            if (!dfs(i, 1))
            // 这里注意每个结点所在路径上的点都会被染色
            // 仍未被染色一定在不连通的其他路径上
            // 因而起点都可默认染为1
            {
                return false
            }
    return true;
}

AcWing 860. 染色法判定二分图

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 染色法判别二分图——AcWing 860. 染色法判定二分图
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;// 邻接表存储图
// 注意e[]和ne[]存的是边数，大小为M
int color[N];// 表示每个点的颜色，0表示未染色，1表示白色，2表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
// 深度优先遍历对节点进行染色

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

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]){
            if (!dfs(j, 3 - c)) return false;
            // 进行染色，注意染相反的颜色
            // 这里由于两种颜色分别为1、2，所以用3 - c来表示相反颜色
        }
        else if (color[j] == c) return false;
        // 已经被染色，且染的相同颜色，则染色失败，不是二部图
    }

    return true;
}

bool check(){
    // 枚举所有节点，进行染色
    for (int i = 1; i <= n; i ++ )
    // 注意点的编号从1开始
        if (!color[i])
            if (!dfs(i, 1)){
            // 这里注意每个结点所在路径上的点都会被染色
            // 仍未被染色一定在不连通的其他路径上
            // 因而起点都可默认染为1
                return false;
            }
    return true;
}

int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    // 邻接表初始化
    
    for (int i = 0 ;i < m; ++ i){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    
    if (check()) puts("Yes");
    else puts("No");
    return 0;
}

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

时间复杂度是 $O(nm)$, n表示点数，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
int n1, n2;// n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;// 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];// 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];// 表示第二个集合中的每个点是否已经被遍历过

// 进行每个节点的匹配
bool find(int x){
    for (int i = h[x]; i != -1; i = ne[i]){
    // 枚举所有有可能进行匹配的点
        int j = e[i];
        if (!st[j]){
        // st数组可用于防止在结点匹配成功后，find无限递归匹配同一个结点（防止先匹配者自己挖自己墙脚）；
            st[j] = true;
            if (match[j] == 0 || find(match[j])){
            // 如果没有进行过匹配或已匹配的结点还有其他可以匹配的点（可以挖墙脚）就可进行匹配
            // 注意这里如果没有st数组，在查找先匹配者的其他匹配对象时，仍会匹配原对象，导致无限递归自身的死循环
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
// 记录匹配数
for (int i = 1; i <= n1; i ++ ){
    memset(st, false, sizeof st);
    // 初始化
    // 必须每次要全部更新为false，否则无法挖墙脚
    if (find(i)) res ++ ;
}

AcWing 861. 二分图的最大匹配

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
54
55
56
57
58
59
60
61
// 匈牙利算法求二分图的最大匹配——AcWing 861. 二分图的最大匹配
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;// n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;// 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];// 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];// 表示第二个集合中的每个点是否已经被遍历过

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

// 进行每个节点的匹配
bool find(int x){
    for (int i = h[x]; i != -1; i = ne[i]){
    // 枚举所有有可能进行匹配的点
        int j = e[i];
        if (!st[j]){
        // st数组可用于防止在结点匹配成功后，find无限递归匹配同一个结点（防止先匹配者自己挖自己墙脚）；
            st[j] = true;
            if (match[j] == 0 || find(match[j])){
            // 如果没有进行过匹配或已匹配的结点还有其他可以匹配的点（可以挖墙脚）就可进行匹配
            // 注意这里如果没有st数组，在查找先匹配者的其他匹配对象时，仍会匹配原对象，导致无限递归自身的死循环
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d%d", &n1, &n2, &m);
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; ++ i){
        int a, b;
        scanf("%d%d",&a, &b);
        add(a, b);
    }
    
    // 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
    int res = 0;
    // 记录匹配数
    for (int i = 1; i <= n1; i ++ ){
        memset(st, false, sizeof st);
        // 初始化
        // 必须每次要全部更新为false，否则无法挖墙脚
        if (find(i)) res ++ ;
    }

    printf("%d\n", res);
    return 0;
}