Czj's Blog

算法设计与分析-第四章

发表于 更新于 分类于
本文字数： 8.8k 阅读时长 ≈ 8 分钟

单源最短路径

最小生成树

哈夫曼树

单源最短路径

题目大意

给定一个有向图，包含\(n\)个点、\(m\)条有向边以及一个出发点\(s\)。图中每条边从点\(u\)指向点\(v\)，长度为\(w\) 。要求计算并输出从出发点\(s\)到图中其余\(n - 1\)个点的最短路径长度，若无法从\(s\)到达某个点，则输出\(2^{31}-1\)（即 INT_MAX ）。

解法描述

Dijkstra 算法

  1. 算法思想

    采用贪心策略。从源点\(s\)出发，维护一个距离源点最近的顶点集合。每次从集合外选取距离源点最近的顶点加入集合，利用该顶点更新其邻接顶点到源点的距离。由于边权非负，一旦某个顶点加入集合，其到源点的最短距离就确定下来，后续不会再改变。

  2. 实现方式

    利用邻接表来存储图结构，通过 add函数添加边。定义 dist数组记录源点到各顶点的最短距离，初始时将所有距离设为 INT_MAX，dist[s]设为 0；st数组用于标记顶点是否已确定最短路径。借助优先队列（小根堆）heap，按距离源点的距离从小到大存储顶点。在 dijkstra函数中，持续从优先队列取出距离最小的顶点 u，若 u已确定最短路径则跳过。遍历 u的邻接顶点 v，若通过 u到 v的距离小于当前 dist[v]，则更新 dist[v]，并将 v加入优先队列。最后输出 dist数组中的结果。

  3. 复杂度分析

    • 时间复杂度：使用邻接表和二叉堆实现时，每次从优先队列取出顶点的时间复杂度为\(O(\log n)\)，总共处理\(n\)个顶点，遍历边的时间复杂度为\(O(m)\)，所以时间复杂度为\(O((n + m)\log n)\)。若使用斐波那契堆，可优化到\(O(n\log n + m)\)。
    • 空间复杂度：邻接表存储图需要\(O(n + m)\)的空间；优先队列（二叉堆）存储顶点需要\(O(n)\)空间；dist和 st数组各需\(O(n)\)空间。因此，总空间复杂度为\(O(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
45
46
47
48
//堆优化dijkstra，邻接表存
#include <bits/stdc++.h>
using namespace std;
int n, m, s;
typedef pair<int, int> PII;
const int N = 1e5 + 9, M = 5e5 + 9;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int dist[N];//s到所有点的最小距离
bool st[N];//防止重复入队
void dijkstra() {
	for (int i = 1; i <= n; i++) dist[i] = INT_MAX;
	dist[s] = 0;
	priority_queue<PII, vector<PII>, greater<PII> > heap; //小根堆
	heap.push({0, s}); //入队
	while (heap.size()) {
		auto t = heap.top();
		heap.pop();
		int index = t.second, distance = t.first;
		if (st[index]) continue; //如果这个点已经检查过了，那就跳过
		st[index] = 1;//标记
		for (int i = h[index]; i != -1; i = ne[i]) { //检查出边
			int j = e[i];
			if (dist[j] > distance + w[i]) {
				dist[j] = distance + w[i];
				if (!st[j]) {
					heap.push({dist[j], j});
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%d ", (dist[i] == INT_MAX ? INT_MAX : dist[i]));
	}
}
int main() {
	scanf("%d %d %d", &n, &m, &s);
	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);
	}
	dijkstra();
	return 0;
}

SPFA 算法

  1. 算法思想

    是 Bellman - Ford 算法的队列优化版本。借助队列优化松弛操作，不断取出队首顶点，更新其邻接顶点的距离。若邻接顶点距离更新且未在队列中，则将其加入队列，直至队列为空。理论上边权可为负，但本题边权非负时也可使用。

  2. 实现方式

    同样用邻接表存储图，addedge函数用于建图。dis数组记录源点到各顶点的距离，初始化为极大值，dis[s]设为 0；vis数组标记顶点是否在队列中。在 spfa函数里，将源点入队，在队列不为空时，取出队首顶点 u，标记其出队，遍历 u的邻接顶点 v，若通过 u到 v的距离小于当前 dis[v]，则更新 dis[v]，若 v不在队列中则将其入队并标记。最后输出 dis数组中的结果。 3. 复杂度分析：

  3. 复杂度分析

    • 时间复杂度：最坏情况下，每个顶点入队\(n\)次，每次入队遍历其出边，时间复杂度为\(O(nm)\)。在随机图中，平均时间复杂度接近\(O(km)\)（\(k\)为常数且\(k \lt n\) ）。本题边权为正，其时间复杂度比 Dijkstra 算法高。
    • 空间复杂度：邻接表存储图需要\(O(n + m)\)空间；队列存储顶点最多需要\(O(n)\)空间；dis和 vis数组各需要\(O(n)\)空间。所以总空间复杂度为\(O(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
45
46
47
48
49
50
51
#include <bits/stdc++.h>
const int maxn = 100005;
const int maxm = 500005;
using namespace std;
int n, m, s = 1, num_edge = 0;
int dis[maxn], vis[maxn], head[maxm];
struct edge {
	int next, to, dis;
} edge[maxm]; //结构体表示静态邻接表
void addedge(int from, int to, int dis) { //邻接表建图
	edge[++num_edge].next = head[from]; //连式存储下一条出边
	edge[num_edge].to = to; //当前节点编号
	edge[num_edge].dis = dis; //本条边的距离
	head[from] = num_edge; //记录下一次的出边情况
}
void spfa() {
	queue<int> q;//sqfa用队列，这里用了stl标准队列
	memset(dis, 0x3f, sizeof dis);
	q.push(s);
	dis[s] = 0;
	vis[s] = 1; //第一个顶点入队，进行标记
	while (!q.empty()) {
		int u = q.front(); //取出队首
		q.pop();
		vis[u] = 0; //出队标记
		for (int i = head[u]; i; i = edge[i].next) { //邻接表的遍[历
			int v = edge[i].to;
			if (dis[v] > dis[u] + edge[i].dis) {
				dis[v] = dis[u] + edge[i].dis;
				if (vis[v] == 0) {
					vis[v] = 1; //标记入队
					q.push(v);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%d ", (dis[i] == 0x3f3f3f3f ? INT_MAX : dis[i]));
	}
}
int main() {
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++) {
		int f, g, w;
		cin >> f >> g >> w;
		addedge(f, g, w);
	}
	spfa();

	return 0;
}

最小生成树

题目大意

给定一个图，图中包含顶点集合和边集合，每条边都有一个权重代表连接两个顶点的成本或距离。要求使用合适的算法找到该图的最小生成树，并计算最小生成树的总权重。

最小生成树（Minimum Spanning Tree，MST）是在一个连通无向图中，由所有顶点和连接这些顶点的部分边构成的一棵树，这棵树满足以下两个关键特性：

  • 包含所有顶点：最小生成树包含图中的全部顶点。以城市交通图为例，每个城市是一个顶点，最小生成树必须涵盖所有城市，确保每个城市都能通过树中的边与其他城市相连通。
  • 边权总和最小：在所有能够连接图中所有顶点的树中，最小生成树的边的权重之和是最小的。继续以城市交通图来说，边的权重可代表城市间建设道路的成本，最小生成树就表示用最低的总成本在所有城市间建立道路连接的方案，能避免不必要的高成本连接，达到资源的最优利用。

解法描述

Kruskal

  1. 算法思想

    采用贪心策略，先将图中所有边按权重从小到大排序。然后依次选取最短的边，若选取的边不会使已选边形成环，则将其加入最小生成树中，直到所有顶点都被包含在生成树中。

  2. 实现方式

    首先读取图的顶点数 \(n\) 和边的权重信息，将有效边（权重不为-1）存储到数组 e中。使用并查集数据结构（find函数和数组 p）来检测加入某条边是否会产生环。对边数组 e进行排序后，遍历每条边，判断边的两个端点是否在不同的集合（即不会形成环），若是，则合并这两个集合，并将边的权重累加到结果 ans中。

  3. 复杂度分析

    • 时间复杂度：主要取决于边的排序，时间复杂度为 \(O(E log E)\)，其中 \(E\) 是边的数量。
    • 空间复杂度：使用邻接表存储图，空间复杂度是 \(O(V + E)\)，\(V\) 是顶点的数量。
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 9, MOD = 100007, M = 6e7 + 9;
int n, g[N][N], idx, p[N], ans;
typedef struct node {
	int a, b, w;
} edge;
edge e[M];
bool cmp(edge x, edge y) {
	return x.w < y.w;
}
int find(int x) {
	if (p[x] != x) {
		p[x] = find(p[x]);
	}
	return p[x];
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> g[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (g[i][j] != - 1) e[idx++] = {i, j, g[i][j]};
		}
	}
	for (int i = 0; i < n; i++) p[i] = i;
	sort(e, e + idx, cmp);
//	for (int i = 0; i < idx; i++) {
//		auto t  = e[i];
//		cout << t.a << " " << t.b << " " << t.w << endl;
//	}
	for (int i = 0; i < idx; i++) {
		int a, b, w;
		a = e[i].a, b = e[i].b, w = e[i].w;
		if (find(a) != find(b)) {
//			cout << find(a) << " " << find(b) << endl;
			p[find(a)] = find(b);
			ans = (ans + w) % MOD;
		}
	}
	cout << ans << endl;
	return 0;
}

Prim

  1. 算法思想

    从任意一个顶点开始，逐步扩展生成树。每次选择连接已在生成树中的顶点和不在生成树中的顶点的最短边，直到所有顶点都被包含在生成树中。

  2. 实现方式

    初始化距离数组 dist为无穷大，标记数组 st为未访问。通过循环 n次，每次在未访问的顶点中选择距离当前生成树最近的顶点 t，将其距离累加到结果 ans中，然后用该顶点更新其他顶点到生成树的距离，标记该顶点已访问。

  3. 复杂度分析

    • 时间复杂度：时间复杂度为 \(O(E + V log V)\)，其中 \(V\) 是顶点的数量，这通常发生在使用优先队列（如二叉堆）选择最小边时。
    • 空间复杂度：使用邻接矩阵存储图，空间复杂度是 \(O(V^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
#include <bits/stdc++.h>
using namespace std;
//选点
int n;
const int N = 1e4 + 9, MOD = 100007;
int g[N][N], dist[N], st[N], ans; //dist表示点到集合的距离，st表示点有没有被选过

int prim() {
	for (int i = 1; i <= n; i++) dist[i] = INT_MAX;
	for (int i = 0; i < n; i++) { //遍历n次，选择n个点
		int t = -1;
		for (int j = 1; j <= n; j++) {
			if ((!st[j]) && (t == -1 || dist[t] > dist[j])) t = j; //选择到集合最近的点
		}
		if (i) { //这里用于跳过第一次遍历，因为第一次还没有更新dist，距离都是无穷大。也不能提前选点来初始化dist，因为不知道哪些点是不可用的
			ans = (ans + dist[t]) % MOD;
		}
//		if (i && dist[t] == 0x3f3f3f3f) return INT_MAX; //如果在某一循环中，找不到可以到达的点，说明不连通

		for (int j = 1; j <= n; j++) {
			//用找到的点来优化dist
			dist[j] = min(dist[j], g[t][j]);//t已经加入了集合，g[t][j]是从t到j的新距离
		}
		st[t] = 1;//标记
	}
	return ans % MOD;
}

int main() {
	int x;
	cin >> n;
	for (int i = 1; i <= n; i++) g[i][i] = INT_MAX;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> x;
			if (x == -1)g[i][j] = INT_MAX;
			else g[i][j] = x;
		}
	}

	cout << prim();
	return 0;
}

哈夫曼树

题目大意

题目给定 26 个小写字母 a - z 的非归一化概率以及一个由 26 个小写字母组成的序列。需要根据这些字母的概率构建霍夫曼树，再使用该霍夫曼树对给定的字母序列进行压缩，最后计算压缩后该序列占用的总比特数。

解法描述

霍夫曼编码

  1. 算法思想

    霍夫曼编码是一种用于数据压缩的贪心算法。其核心思想是根据字符出现的频率构建一棵二叉树，频率较低的字符离根节点较远，频率较高的字符离根节点较近。在构建树的过程中，每次选取频率最小的两个节点合并成一个新节点，新节点的频率为这两个节点频率之和，重复这个过程直到只剩下一个根节点。这样，每个字符的编码长度就由其在霍夫曼树中的深度决定，出现频率高的字符编码短，出现频率低的字符编码长，从而实现数据的压缩。

  2. 实现方式

    • 输入处理：使用 for 循环读取 26 个小写字母 a - z 的非归一化概率，并将每个概率及其对应的索引（idx 从 0 开始递增）以 pair<int, int> 的形式存入优先队列 huf 中，优先队列按概率从小到大排序。
    • 构建霍夫曼树：当优先队列 huf 中的元素数量大于 1 时，取出队首的两个元素 t1 和 t2，将它们合并成一个新节点，新节点的概率为 t1.first + t2.first，索引为 idx 并递增。同时记录新节点的两个子节点为 t1.second 和 t2.second 到 son 数组中，再将新节点重新插入优先队列 huf 中。
    • 计算字符编码长度：定义深度优先搜索函数 dfs，对于每个非叶子节点（索引大于等于 26），递归地对其左右子节点调用 dfs 函数；对于叶子节点（索引小于 26），对应字符的编码长度计数器 cnt[p] 加 1。通过遍历所有节点调用 dfs 函数，计算出每个字母的编码长度。

  3. 复杂度分析

    • 时间复杂度：

      构建优先队列的时间复杂度为 \(O(n log n)\)，其中 \(n = 26\) 是字母的数量。构建霍夫曼树的过程中，每次从优先队列中取出两个元素并插入一个新元素，共进行 \(n - 1\) 次操作，每次操作的时间复杂度为 \(O(log n)\)，所以构建树的总时间复杂度为 \(O(n log n)\)。计算字符编码长度的深度优先搜索过程需要遍历所有节点，时间复杂度为 \(O(n)\)。计算总比特数需要遍历输入的字符串，设字符串长度为 \(m\)，时间复杂度为 \(O(m)\)。综合起来，总的时间复杂度为 \(O(n log n + m)\)。

    • 空间复杂度：

      优先队列 huf 最多存储 \(n\) 个元素，空间复杂度为 \(O(n)\)。son 数组用于存储霍夫曼树的节点关系，空间复杂度为 \(O(n)\)。cnt 数组用于存储每个字母的编码长度，空间复杂度为 \(O(n)\)。因此，总的空间复杂度为 \(O(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
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;


typedef pair<int, int> PII; //占比，序号，编码长度

int x, ans, idx;
const int MOD = 100007;
string s;
int cnt[1000] = {0};
priority_queue<PII, vector<PII>, greater<PII>> huf;
PII son[1000];//每个父节点对应两个子节点，对于26个字母，开1000个足够

//新节点对应的原始节点需要用dfs来取得，即依次向下深挖，找到原有节点

void dfs(int p) {
	if (p < 26) { //检查是否为叶节点
		cnt[p] ++;
		return ;
	}
	dfs(son[p].first), dfs(son[p].second);
}


int main() {
	for (int i = 0; i < 26; i++) {
		cin >> x;
		huf.push({x, {idx++}});
	}
	while (huf.size() > 1) {
		auto t1 = huf.top();
		huf.pop();
		auto t2 = huf.top();
		huf.pop();
		//自下而上建立新节点
		son[idx] = {t1.second, t2.second};
		huf.push({t1.first + t2.first, idx++});
	}
	//从非叶子节点开始，因为高度是h-1
	for (int i = 0; i < idx; i++) {
		dfs(i);
	}
//	dfs(idx - 1, 0);
	cin >> s;
	for (auto item : s) {
		ans = (ans + cnt[item - 'a'] - 1) % MOD;
	}
	cout << ans << endl;
//	for (int i = 0; i < idx; i++) {
//		cout << cnt[i] << " ";
//	}
	return 0;
}