【图论】生成树问题合集

更新于 分类于 ， 阅读次数： 本文字数： 7.3k 阅读时长 ≈ 7 分钟

包括了最小生成树、次小生成树、斯坦纳树和最小树形图的模板

最小生成树

最小生成树（Minimum Spanning Tree，MST），字面意思，由连通图生成，包含所有节点，是一棵树，且边权和最小。

Kruskal

  • 对边排序，从小到大如果端点不在同一集合里就加边到生成树里
  • 复杂度O(mlog⁡m)O(m\log m) ，适用于稀疏图
  • 证明：归纳法证明任何时候该算法选择的边集都被某棵 MST 所包含
    • 基础：对于算法刚开始时，显然成立（最小生成树存在）
    • 假设某时刻成立，当前边集为FF ，令TT 为这棵 MST，考虑下一条加入的边ee
    • 如果e∈Te\in T 则成立
    • 鸽了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int kruskal()
{
	int ans = 0, cnt = 0;
	sort(edge, edge + m);
	for (int i = 0; i < m; i++)
	{
		int u = father(edge[i].u), v = father(edge[i].v); //并查集
		if (u == v)
			continue;
		fa[u] =v;
		ans += edge[i].w;
		cnt++;
		if (cnt == n - 1)
			break;
	}
	if (cnt < n - 1)
		return -1; //不连通
	return ans;
}

Prim

每次取到目前集合距离最小的点加入

暴力

每次遍历所有点到当前点集的距离，找到最小的加入（标记已访问），更新它到其他点的最小距离。

复杂度O(n2)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
bool vst[N];
int prim()
{
    int ans = 0;
    vst[1] = true;
    for (int i = 2; i <= n; i++) //点是从1开始编号的
        dis[i] = a[1][i];
    for (int i = 2; i <= n; i++)
    {
        int minc = INF;
        int pos = -1;
        for (int j = 1; j <= n; j++)
            if (!vst[j] && minc > dis[j])
                minc = dis[j], pos = j;
        if (minc == INF)
            return -1; //原图不连通
        ans += minc;
        vst[pos] = true;
        for (int j = 1; j <= n; j++) //更新其余点的最短距离
            if (!vst[j] && dis[j] > a[pos][j])
                dis[j] = a[pos][j];
    }
    return ans;
}

堆优化

O((n+m)log⁡n)O((n+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
priority_queue<pii, vector<pii>, greater<pii>> q;
int prim()
{
    dis[1] = 0;
    int cnt = 0, ans = 0;
    q.push(make_pair(0, 1));
    while (!q.empty() && cnt < n)
    {
        int d = q.top().first, u = q.top().second;
        q.pop();
        if (vst[u])
            continue;
        cnt++;
        ans += d;
        vst[u] = true;
        for (int i = head[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to, w = edge[i].val;
            if (w < dis[v])
            {
                dis[v] = w;
                q.push(make_pair(dis[v], v));
            }
        }
    }
    if (cnt < n - 1)
        return -1;
    return ans;
}

次小生成树

非严格次小生成树

  • 设MST的边集为EE ，剩余边集为E′E' ，则有∀(u′,v′,w′)∈E′，(u,v,w)∈E,有w≤w′\forall (u',v',w') \in E'，(u,v,w)\in E,\text{有} w\leq w'
  • 对于uu 到vv 的路径中最长的一条边，用(u′,v′,w′)(u',v',w') 替换它，得到一个权值和为M′=M−w+w′M'=M-w+w' ，对所有的替换取最小值
  • 其中最长的一条边用倍增lca来求就可以，板子里没用倍增
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
const int N = 1e3 + 10, INF = 0x7fffffff;
int n;
bool vst[N];
int dis[N];
int pre[N]; //记录路径
int Max[N][N];
int mp[N][N];
//Max[i][j] 表示在最小生成树中从 i 到 j 的路径中的最大边权
bool used[N][N]; //表示添加过i到j这条路了
int Prim()
{
    int ans = 0;
    memset(vst, false, sizeof(vst));
    memset(Max, 0, sizeof(Max));
    memset(used, false, sizeof(used));
    vst[0] = true;
    pre[0] = -1;
    for (int i = 1; i < n; i++) //0开始编号的
    {
        dis[i] = mp[0][i];
        pre[i] = 0;
    }
    dis[0] = 0;
    for (int i = 1; i < n; i++)
    {
        int tmp = INF, p = -1;
        for (int j = 0; j < n; j++)
            if (!vst[j] && tmp > dis[j])
                tmp = dis[j], p = j;
        if (tmp == INF)
            return -1;
        ans += tmp;
        vst[p] = true;
        used[p][pre[p]] = used[pre[p]][p] = true;
        for (int j = 0; j < n; j++)
        {
            if (vst[j] && j != p) //更新最长边长度
                Max[j][p] = Max[p][j] = max(Max[j][pre[p]], dis[p]);
            if (!vst[j] && dis[j] > mp[p][j])
            {
                dis[j] = mp[p][j];
                pre[j] = p;
            }
        }
    }
    return ans;
}

严格次小生成树

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
//使用：跑MST，加边的时候调用insedge，并将一个全局used[i]函数标记为真
class Tr
{
private:
    struct Edge
    {
        int to, nxt, val;
    } e[M << 1];
    int cnt, head[N];

    int fa[N][22];
    int dep[N];

    int maxx[N][22]; // 到祖先的路径上边权最大的边
    int minn[N][22]; // 到祖先的路径上边权次大的边，若不存在则为 -INF

public:
    void add_edge(int u, int v, int val)
    {
        e[++cnt].to = v;
        e[cnt].val = val;
        e[cnt].nxt = head[u];
        head[u] = cnt;
    }

    void insedge(int u, int v, int val)
    {
        add_edge(u, v, val);
        add_edge(v, u, val);
    }

    void dfs(int rt, int from)
    {
        dep[rt] = dep[from] + 1;
        fa[rt][0] = from;
        minn[rt][0] = -INF;
        for (int i = 1; i < 22; i++)
        {
            fa[rt][i] = fa[fa[rt][i - 1]][i - 1];
            int kk[4] = {maxx[rt][i - 1], maxx[fa[rt][i - 1]][i - 1],
                         minn[rt][i - 1], minn[fa[rt][i - 1]][i - 1]};
            sort(kk, kk + 4); //从四个值中取得最大值
            maxx[rt][i] = kk[3];
            int ptr = 2;
            while (ptr >= 0 && kk[ptr] == kk[3])
                ptr--;
            minn[rt][i] = (ptr == -1 ? -INF : kk[ptr]); // 取得严格次大值
        }

        for (int i = head[rt]; i; i = e[i].nxt)
        {
            if (e[i].to == from)
                continue;
            maxx[e[i].to][0] = e[i].val;
            dfs(e[i].to, rt);
        }
    }

    int lca(int x, int y) //求lca(x,y)
    {
        if (dep[x] > dep[y])
            swap(x, y);
        int tmp = dep[y] - dep[x];
        for (int i = 0; tmp; i++, tmp >>= 1)
            if (tmp & 1)
                y = fa[y][i];
        if (y == x)
            return x;
        for (int i = 21; i >= 0 && y != x; --i) //否则一起往上跳，优先跳大的
            if (fa[x][i] != fa[y][i])           //跳到lca下面，再往上跳
                x = fa[x][i], y = fa[y][i];
        return fa[x][0]; //注意这里返回的是父亲节点而不是本身
    }

    int query(int a, int b, int val)
    {
        int res = -INF;
        for (int i = 21; i >= 0; i--)
        {
            if (dep[fa[a][i]] >= dep[b])
            {
                if (val != maxx[a][i])
                    res = max(res, maxx[a][i]);
                else
                    res = max(res, minn[a][i]);
                a = fa[a][i];
            }
        }
        return res;
    }
} tr;

//主函数里
Kruskal();
ll ans = LINF;
tr.dfs(1, 0);
rep(i, 1, m)
{
    if (used[i])
        continue;
    int _lca = tr.lca(edge[i].u, edge[i].v); // 找到路径上不等于 e[i].val 的最大边权
    long long tmpa = tr.query(edge[i].u, _lca, edge[i].val);
    long long tmpb = tr.query(edge[i].v, _lca, edge[i].val);
    if (max(tmpa, tmpb) > -INF) // 这样的边可能不存在，只在这样的边存在时更新答案
        ans = min(ans, sum - max(tmpa, tmpb) + edge[i].val);
}
printf("%lld\n", ans == LINF ? -1 : ans);

斯坦纳树

定义

给定n个点，试求连接此n个点，总长最短的直线段连接系统，并且任意两点都可由系统中的直线段组成的折线连接起来。

分析

模板题：无向连通图，可能自环和重边，给定k个关键点，求一个子图使得边权和最小。

  • 子图一定是树，否则一定可以去环使得边权和变小。这棵树就是最小斯坦纳树。
  • 设dp(i,S)dp(i,S) 表示ii 为根，包含点集SS 中所有点的最小权值和
  • 设TT 是SS 的子集，则dp(i,S)dp(i,S) 由dp(i,T)+dp(i,S−T)dp(i,T)+dp(i,S-T) 转移而来。
  • 松弛操作，对于ii 的相邻节点jj ：f(i,S)=min(f(i,S),f(j,S)+w(j,i))f(i,S)=min(f(i,S),f(j,S)+w(j,i))

步骤

  • 将dpdp 初始化为0x3f3f3f3f0x3f3f3f3f
  • 枚举给定点的子集SS
    • 对于SS 枚举子集TT ，更新每个节点的dpdp
    • 如果权值和被更新，说明这个点可行，加入spfaspfa 的队列
    • 进行spfaspfa 更新队列中点的相邻点的答案
  • 答案是给定点中的任意点ii 的dpdp 值

代码

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
for (int i = 0; i < k; i++)
{
	read(p[i]);
	dp[p[i]][1 << i] = 0;
}
int up = (1 << k) - 1;
for (int s1 = 0; s1 <= up; s1++) //枚举给定点的子集递推
{
	for (int i = 1; i <= n; i++)
	{
		for (int s2 = s1 & s1 - 1; s2; s2 = s2 - 1 & s1)			//枚举当前点集的子集
			dp[i][s1] = min(dp[i][s1], dp[i][s2] + dp[i][s1 ^ s2]); //dp(i,S)<-dp(i,T)+dp(i,S_T)
		if (dp[i][s1] < INF)
		{
			q.push(i);
			vst[i] = true;
		}
	}
	spfa(s1); 
}
//spfa的松弛操作：
// if (dp[v][S] > dp[u][S] + w)
// {
// 	dp[v][S] = dp[u][S] + w;
// 	if (!vst[v]) //如果不在队列里就加入
// 		q.push(v), vst[v] = true;
// }

最小树形图

有向图的最小生成树，从根节点能到所有节点，且每条边权值和最小。

朱刘算法（Edmonds 算法），O(nm)O(nm) 。

模板题：给定包含n个结点，m条有向边的一个图。输出以结点r为根的最小树形图每条边的权值之和，如果没有以r为根的最小树形图，输出-1。

步骤

  • 统计每个点的最小入边，加入答案
  • 如果有一个点找不到入边，说明不能生成最小树形图，返回-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
int in[N], pre[N]; //in[i]记录每轮i点入边中最小的边权，pre[i]记录最小边权对应的端点编号
int vst[N], scc[N];
int Zhuliu()
{
	int ans = 0;
	while (1)
	{
		for (int i = 1; i <= n; i++)
			in[i] = INF; // 初始化
		for (int i = 1; i <= m; i++)
		{
			int u = edge[i].from, v = edge[i].to;
			if (u != v && edge[i].val < in[v]) // 遍历所有边，对每个点找到最小的入边
				in[v] = edge[i].val, pre[v] = u;
		}
		for (int i = 1; i <= n; i++)	   // 判定无解
			if (i != root && in[i] == INF) //有一个点找不到入边了
				return -1;
		int sc = 0;
		for (int i = 1; i <= n; i++)
			vst[i] = scc[i] = 0;
		for (int i = 1; i <= n; i++)
		{
			if (i == root)
				continue;
			ans += in[i];
			int v = i;
			while (vst[v] != i && !scc[v] && v != root) // 找环，找回自己/找到一个缩过点的/找到根节点了都退出
			{
				vst[v] = i;
				v = pre[v];
			}
			if (!scc[v] && v != root) //一定是找回自己
			{
				scc[v] = ++sc; // 缩点
				for (int u = pre[v]; u != v; u = pre[u])
					scc[u] = sc;
			}
		}
		if (sc == 0)
			break; // 无环，得到解
		for (int i = 1; i <= n; i++)
			if (!scc[i])
				scc[i] = ++sc;
		for (int i = 1; i <= m; i++) //重构图
		{
			int u = edge[i].from, v = edge[i].to;
			edge[i].from = scc[u], edge[i].to = scc[v];
			if (scc[u] != scc[v])
				edge[i].val -= in[v]; // 修改边权
		}
		root = scc[root];
		n = sc;
	}
	return ans;
}

注意

  • 给坐标的注意精度
  • 最小生成森林，可跑并查集，连通块个数tot，则最大生成森林的边数为n-tot
  • 给出一些已知边，跑MST时将这些边权值取0的处理方法