prim 算法#

时间复杂度： $O(n^2)$

特点：无向图，图中可能存在重边和自环，边权可能为负数。

假设已选择的点在集合 $V_1$ ，尚未选择的点在集合 $V_2$ 算法流程：

从 $V_2$ 中任意选择一个点 $v$ ，放入 $V_1$ ，然后更新集合 $V_1$ 到集合 $V_2$ 里面所有点的最小距离 $d$
然后依然从 $V_2$ 中选择点，但此时是选择 $d$ 值最小的点 2.1 如果这个时候选择的点的 $d$ 值是无穷大，说明没有最小生成树 2.2 如果没有 step 2.1，则将当前点放入 $V_1$ ，然后更新权值 cnt 2.3 更新集合 $V_1$ 到集合 $V_2$ 里面所有点的最小距离 $d$
重复 step 2 共 $n - 1$ 次

代码如下：

1
/*
2
存图：邻接矩阵
3
    while (m -- ) {
4
        int x, y, z; cin >> x >> y >> z;
5
        g[x][y] = g[y][x] = min(g[x][y], z);
6
    }
7
*/
8

9
const int N = 510, INF = 0x3f3f3f3f;
10

11
int n, m;
12
int g[N][N], d[N]; // d 数组表示 V1 到 V2 所有点的最小值
13
bool st[N]; // st 用来区别 V1:true 和 V2:false 集合
14

15
int prim() {
16

17
    memset(d, 0x3f, sizeof d);
18
    d[1] = 0; // 这里可以强行选择初始点 1，d[1] = 0 对答案累加也没有影响
19

20
    int cnt = 0;
21
    for (int i = 0; i < n; i ++ ) {
22
        int t = -1;
23
        for (int j = 1; j <= n; j ++ )
24
            if (!st[j] && (t == -1 || d[j] < d[t])) t = j;
25

26
        // 如果选择的点没有跟集合 V1 的点直接相连，则说明没有最小生成树
27
        if (d[t] == INF) return INF;
28

29
        cnt += d[t];
30
        st[t] = true;
31

32
        for (int j = 1; j <= n; j ++ )
33
            d[j] = min(d[j], g[t][j]);
34
    }
35
    return cnt;
36
}

kruskal 算法#

时间复杂度： $O(mlogm)$

特点：无向图，图中可能存在重边和自环，边权可能为负数。

图的存储：结构体存边，按照权值可比较

算法流程：

对边从小到大进行排序
然后从前往后遍历每条边 2.1 如果两点在一个集合，则跳过这条边 2.2 否则，加入这条边，然后把两个点的集合存到一起
最后判断并查集是否只有一个根，是则最后计算的权值是正确的，否则说明无最小生成树

代码如下：

1
const int N = 200010, INF = 0x3f3f3f3f;
2

3
struct edge {
4
    int from, to, w;
5
    bool operator < (const edge& a) const {
6
        return w < a.w;
7
    }
8
} g[N];
9
int n, m;
10
int fa[N];
11

12
// 并查集
13
int get(int x) {
14
    if (fa[x] != x) fa[x] = get(fa[x]);
15
    return fa[x];
16
}
17

18
int kruskal() {
19
    sort(g, g + m);
20
    for (int i = 1; i <= n; i ++ ) fa[i] = i;
21

22
    int res = 0;
23
    for (int i = 0; i < m; i ++ ) {
24
        int a = get(g[i].from), b = get(g[i].to);
25
        if (a == b) continue;
26
        res += g[i].w;
27
        fa[a] = b;
28
    }
29

30
    int cnt = 0;
31
    for (int i = 1; i <= n; i ++ ) cnt += fa[i] == i;
32

33
    return cnt > 1 ? INF : res;
34
}

次小生成树#

定理#

对于一个无向图，如果存在最小生成树和（严格）次小生成树，那么对于任意一棵最小生成树，都存在一棵（严格）次小生成树，使得这两棵树只有一条边不同

那么根据这里定理，假设已经利用 kruskal 算法求出最小生成树的所有边集，那么严格次小生成树一定是有一条边与最小生成树的一条边不同，因此，我们可以从未选择的边从小到大枚举，如果将生成树的某条边替换成这条边能得到的权值是最小的，那么便是次小生成树。

在考虑每一条未选择的边的时候，如果把这条边加上，一定是会形成一个环，因此，我们需要考虑从这个环上面寻找一条最大且不等于这条添加的边的权值的边将其删掉，这样得到的树才可能是次小生成树。

在这里面，问题转化成立寻找一个环里面最大值和次大值，

求一个环里面的最大值和次大值有两个方案：

让任意一个点作根，记录这个点到其任意孩子的最大值和次大值，从而假设未选择的边是 $(a,b)$ , 那么最小生成树一定有一条路径 $(a,b)$ ，因此从 $a$ 为根节点到 $b$ 的最大值和次大值能预处理出来，然后在枚举每一条未选择的边的时候进行计算。
利用 lca 进行计算，假设树根已经确定好了，那么 $(a,b)$ 一定有公共祖先，那么公共祖先到 $a$ 或者 $b$ 的最小值和次小值可以预处理，进而， $a$ 到 $b$ 的最小值和次小值可以计算

生成树的个数#

矩阵树定理#

构建拉普拉斯矩阵 $C$ ，计算是通过图的度对角矩阵减去图的邻接矩阵
拉普拉斯矩阵任意一个主子式的行列式值都等于生成树的数量

最小生成树的个数#

定理

最小生成树的权值以及相同权值的个数的边的数量是一致的
在每次处理完相同权值的边，无论这些权值相同的边怎么选择，最终此时图的连通块数量及其状态是一致的（意思是不仅连通块数量一样，而且连通块对应的点也是一样的）根据定理2，我们在每次处理完一类权值相同的边之后，都可能把这些连通块进行缩点（根据并查集），之后根据乘法原理求最小生成树的数量。注意：此做法要求相同权值的边的数量很少

矩阵树定理#

如果相同权值的点太多，这题便需要用到矩阵树定理进行优化。根据定理2，当我们处理到某一类权值相同的边权的时候，这个时候的连通块数量是相同的，并且此时同样要处理权值相同的一类边，因此可以将其理解为求生成树的个数，这样就完美利用到了矩阵树定理。最后利用乘法原理计算答案即可。