CodeBrick 博客

Appearance

2021·41 EL 路径判定：看着像图算法，一趟扫度就够 ​

本文属于「从暴力解到最优解」专题的第二组。第一组讲的是「怎么把暴力解优化掉」；第二组反过来，讲怎么认出一道题根本不用优化——直观写法就是满分解，力气要花在别的地方。

题目 ​

已知无向连通图 G 由顶点集 V 和边集 E 组成，|E| > 0，当 G 中度为奇数的顶点个数为不大于 2 的偶数时，G 存在包含所有边且长度为 |E| 的路径（称为 EL 路径）。设图 G 采用邻接矩阵存储，类型定义如下：

c
typedef struct {
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char VerticesList[MAXV];        // 顶点表，MAXV 为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

请设计算法 int IsExistEL(MGraph G)，判断 G 是否存在 EL 路径，存在返回 1，否则返回 0。要求：(1) 设计思想；(2) C/C++ 代码；(3) 时间与空间复杂度。总分 13 分。

先注意一件事：题面没有出现「尽可能高效」。按总纲的分类，这属于第二组——没有悬在头顶的最优性要求。但这不等于随便写，下面会看到力气该花在哪。

直观解法：扫一遍矩阵数奇度 ​

题面几乎把算法写在脸上了：「度为奇数的顶点个数不大于 2 的偶数」时存在 EL 路径。EL 路径就是图论里的欧拉路径 / 欧拉回路，判定条件是现成的：

  • 奇度顶点数 = 0 ⇒ 存在欧拉回路；
  • 奇度顶点数 = 2 ⇒ 存在欧拉路径。

而题面已经保证「G 是无向连通图」，连通性是前提、不用自己验。于是整道题退化成一件事：数一数有几个奇度顶点。邻接矩阵下，顶点 i 的度就是第 i 行的元素之和：

c
int IsExistEL(MGraph G) {
    int n = G.numVertices;
    int oddCount = 0;

    for (int i = 0; i < n; i++) {
        int deg = 0;
        for (int j = 0; j < n; j++) deg += G.Edge[i][j];   // 顶点 i 的度 = 第 i 行之和
        if (deg % 2 == 1) oddCount++;                       // 奇度则计数
    }

    return (oddCount == 0 || oddCount == 2) ? 1 : 0;
}

复杂度：双重循环扫整个邻接矩阵，时间 O(n2)；只用了 oddCount、deg 几个标量，空间 O(1)。

为什么它就是满分解 ​

这道题没有「暴力 vs 最优」的分差，因为这个 O(n2) 已经是下界，无法再降。用总纲的「找浪费三问」审一遍，会发现三个问题全部答「没有」：

  1. 有没有重复扫描？ 没有。每个矩阵元素只读一次。
  2. 有没有重算已知的东西？ 没有。每个顶点的度只算一次，用完即弃。
  3. 有没有放着性质不用？ 没有。题目给的连通性已经用上了（正因为它成立，才不必验连通）。

更根本的一条：图用邻接矩阵存储，光是把这 n2 个元素读进来判断，就已经是 O(n2) 了。任何正确算法都躲不开这一遍读取，所以 O(n2) 是这种存储下的理论下界。既然碰到了下界，就没有优化空间——直观写法即最优。

这就是第二组题的共同特征：当输入规模本身就等于复杂度下界时，「优化」这个动作根本不存在。认出这一点，你就不会在考场上浪费时间。

真正的难点在判定条件 ​

分不在优化上，那在哪？在判定条件写没写准。这道题最容易丢分的就是最后那个 oddCount == 0 || oddCount == 2：

  • 写成 oddCount < 2：漏掉了 == 2（欧拉路径）的情形，只认了回路。
  • 写成 oddCount <= 2：把 oddCount == 1 也放了进来。虽然无向图里奇度顶点数必为偶数（握手定理的推论，奇度数 = 1 或 3 根本不可能出现），但判定条件写成 <= 2 在逻辑上就是不严谨。
  • 只写 == 0 或只写 == 2：各漏一半。

准确的表述只有一个：oddCount ∈ {0, 2}。这道 13 分的题，代码框架三行谁都会写，真正的区分度全在这个条件的边界上。设计思想那一问也要把「0 → 回路、2 → 路径」这层对应关系说清楚，而不是只写个「数奇度」。

扫矩阵统计度，看一遍 ​

用一个 5 顶点的无向图（顶点 0 和 3 是奇度，共 2 个奇度顶点，存在 EL 路径）。演示逐行累加求度、数出 oddCount = 2：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足 ​

第二组题的另一半功夫，是忍住不去做多余的事。这道题最典型的两个「过度设计」陷阱：

  • 真去构造一条欧拉路径（Fleury 算法、Hierholzer 算法）。题目只问「存不存在」，构造出具体路径纯属多余，还把复杂度抬到 O((n+e)⋅avg)、代码长几倍、出错点翻倍。判定存在性只需数奇度，不需要造路径。
  • 自己写 BFS/DFS 验连通性。题面白纸黑字保证了「无向连通图」，再验一遍是重复劳动。它不会让答案变错，但会占掉宝贵的卷面时间和心力——而这些本该留给把判定条件抠准。

看到一道图论大题就条件反射地想「遍历、递归、建辅助结构」，是这类题最大的失分来源。先问一句「题目到底要不要我这么干」，往往发现最朴素的一趟扫描就是标准答案。

下一步 ​

  • 在 OJ 上验证你的写法：ds-2021-41 EL 路径判定
  • 回到题库看这道题的完整解析与错因：真题库 · 数据结构
  • 同属「扫邻接矩阵一趟即满分」的邻题：2023·41 K 顶点、2024·41 拓扑序唯一性，专题后续更新