数据结构与算法 / 系统课时
图算法实现最易错在哪
图算法实现最易错在哪
图算法最棘手的错误往往不是主公式写错,而是输入边界没有被实现覆盖:重边改变最短路、断图留下不可达点、距离累加溢出,或上一组测试的数据残留到下一组。本节把这些高频问题压缩成一套可直接用于提交前检查的实现策略。
学习目标
- 识别重边、重复处理、断图和无解等常见图算法边界
- 用足够宽的整数类型和安全无穷大避免距离运算溢出
- 通过局部初始化和最小反例防止多测试用例互相污染
重边和重复访问要按算法语义处理
两点之间出现多条边并不一定是异常输入。最短路中可以保留全部非负重边,让松弛自然选择更短路径;也可以在建图时合并成最小权值,但只有确认后续算法不需要边的独立身份时才能这么做。最大流、多重图计数等问题则不能随意删掉重边。
重复进入队列同样不等于错误。Dijkstra 使用优先队列时,一个顶点可能以多个候选距离入堆;常见做法不是强行禁止重复入堆,而是在出堆时丢弃已经过期的条目。BFS 在无权图中则通常应在入队时立即标记访问,防止同一顶点被大量重复加入队列。
距离类型和无穷大必须一起设计
边权、路径长度和中间计算的上界要单独估算。即使单条边能放进 32 位整数,多条边累加后也可能溢出。因此 C++ 中处理大权值最短路时,距离通常使用 long long。
无穷大也不能简单设成类型最大值后直接参与加法。若 dist[u] 已接近上界,再计算 dist[u] + w 可能溢出。更稳妥的方式是使用明显大于合法答案、但仍给加法留下余量的哨兵值,并且只从已经可达的顶点执行松弛。
用一份实现同时覆盖关键边界
下面的完整程序运行两组图。第一组包含重边,并利用过期条目判断避免重复扩展;第二组包含断开的顶点,用 UNREACHABLE 明确表示无解。每次调用函数都重新创建邻接表和距离数组,因此两组测试不会互相污染。
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
using Edge = pair<int, ll>;
vector<ll> dijkstra(int n, const vector<tuple<int, int, ll>>& edges, int source) {
vector<vector<Edge>> graph(n);
for (auto [u, v, w] : edges) {
graph[u].push_back({v, w});
}
const ll INF = numeric_limits<ll>::max() / 4;
vector<ll> dist(n, INF);
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
// 同一顶点可以多次入堆,但旧距离不再继续扩展。
if (d != dist[u]) {
continue;
}
for (auto [v, w] : graph[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
void print_result(const vector<ll>& dist) {
const ll INF = numeric_limits<ll>::max() / 4;
for (ll d : dist) {
if (d == INF) {
cout << "UNREACHABLE ";
} else {
cout << d << ' ';
}
}
cout << '\n';
}
int main() {
vector<tuple<int, int, ll>> case1 = {
{0, 1, 10}, {0, 1, 3}, {1, 2, 4}, {0, 2, 20}
};
print_result(dijkstra(3, case1, 0));
// 第二组故意留下顶点 3 不可达,用于检查断图处理。
vector<tuple<int, int, ll>> case2 = {
{0, 1, 5}, {1, 2, 6}
};
print_result(dijkstra(4, case2, 0));
}预期输出
0 3 7
0 5 11 UNREACHABLE 第一组中 0 -> 1 有权值 10 和 3 两条边,最短路应选择 3,并得到到顶点 2 的距离 7。第二组的顶点 3 与源点不连通,因此不能把初始哨兵值误当成正常答案。
多测试用例最容易留下隐形状态
污染通常来自全局邻接表、访问数组、入度、并查集父节点或距离数组没有按当前规模重置。更安全的默认方案是把这些结构放进单次求解函数,让对象生命周期与一个测试用例一致;只有确认反复分配成为性能瓶颈时,再考虑复用内存并显式清理。
还要注意“清理到哪里”。如果上一组有 个顶点,下一组只有 个,而代码只重置后者范围,之后又错误访问旧编号,残留边仍可能参与计算。调试这类问题时,可以交换测试用例顺序:若单独运行都正确、组合后结果变化,应优先怀疑共享状态。
提交前用最小反例逐项验收
不要只用随机大图验证。针对实现边界准备几个极小输入通常更有效:只有一个顶点的图、两点之间存在重边、存在自环、源点与目标不连通、图由多个连通分量组成,以及路径和接近整数上界的情况。对于多测试用例,再把结构完全不同的两组数据连续执行一次。
最后把检查顺序固定下来:先确认题目是否允许重边和自环,再确认访问或过期状态的判定时机,随后检查距离类型与无穷大,验证不可达输出,最后检查所有跨测试共享的数据是否彻底重置。主算法正确之后,这些边界往往就是决定一次提交能否稳定通过的地方。