数据结构与算法 / 系统课时

图算法实现最易错在哪

图算法实现最易错在哪

图算法最棘手的错误往往不是主公式写错,而是输入边界没有被实现覆盖:重边改变最短路、断图留下不可达点、距离累加溢出,或上一组测试的数据残留到下一组。本节把这些高频问题压缩成一套可直接用于提交前检查的实现策略。

学习目标

  • 识别重边、重复处理、断图和无解等常见图算法边界
  • 用足够宽的整数类型和安全无穷大避免距离运算溢出
  • 通过局部初始化和最小反例防止多测试用例互相污染

重边和重复访问要按算法语义处理

两点之间出现多条边并不一定是异常输入。最短路中可以保留全部非负重边,让松弛自然选择更短路径;也可以在建图时合并成最小权值,但只有确认后续算法不需要边的独立身份时才能这么做。最大流、多重图计数等问题则不能随意删掉重边。

重复进入队列同样不等于错误。Dijkstra 使用优先队列时,一个顶点可能以多个候选距离入堆;常见做法不是强行禁止重复入堆,而是在出堆时丢弃已经过期的条目。BFS 在无权图中则通常应在入队时立即标记访问,防止同一顶点被大量重复加入队列。

距离类型和无穷大必须一起设计

边权、路径长度和中间计算的上界要单独估算。即使单条边能放进 32 位整数,多条边累加后也可能溢出。因此 C++ 中处理大权值最短路时,距离通常使用 long long。

无穷大也不能简单设成类型最大值后直接参与加法。若 dist[u] 已接近上界,再计算 dist[u] + w 可能溢出。更稳妥的方式是使用明显大于合法答案、但仍给加法留下余量的哨兵值,并且只从已经可达的顶点执行松弛。

用一份实现同时覆盖关键边界

下面的完整程序运行两组图。第一组包含重边,并利用过期条目判断避免重复扩展;第二组包含断开的顶点,用 UNREACHABLE 明确表示无解。每次调用函数都重新创建邻接表和距离数组,因此两组测试不会互相污染。

cpp
#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));
}

预期输出

text
0 3 7 
0 5 11 UNREACHABLE 

第一组中 0 -> 1 有权值 10 和 3 两条边,最短路应选择 3,并得到到顶点 2 的距离 7。第二组的顶点 3 与源点不连通,因此不能把初始哨兵值误当成正常答案。

多测试用例最容易留下隐形状态

污染通常来自全局邻接表、访问数组、入度、并查集父节点或距离数组没有按当前规模重置。更安全的默认方案是把这些结构放进单次求解函数,让对象生命周期与一个测试用例一致;只有确认反复分配成为性能瓶颈时,再考虑复用内存并显式清理。

还要注意“清理到哪里”。如果上一组有 10510^5 个顶点,下一组只有 10310^3 个,而代码只重置后者范围,之后又错误访问旧编号,残留边仍可能参与计算。调试这类问题时,可以交换测试用例顺序:若单独运行都正确、组合后结果变化,应优先怀疑共享状态。

提交前用最小反例逐项验收

不要只用随机大图验证。针对实现边界准备几个极小输入通常更有效:只有一个顶点的图、两点之间存在重边、存在自环、源点与目标不连通、图由多个连通分量组成,以及路径和接近整数上界的情况。对于多测试用例,再把结构完全不同的两组数据连续执行一次。

最后把检查顺序固定下来:先确认题目是否允许重边和自环,再确认访问或过期状态的判定时机,随后检查距离类型与无穷大,验证不可达输出,最后检查所有跨测试共享的数据是否彻底重置。主算法正确之后,这些边界往往就是决定一次提交能否稳定通过的地方。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

图算法实现最易错在哪

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通