题目

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

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) 说明你所设计算法的时间复杂度和空间复杂度。

解析

(1) 设计思想

答案：扫一遍邻接矩阵，统计度为奇数的顶点个数 oddCount；当 oddCount == 0 或 oddCount == 2 时返回 1，否则返回 0。

为什么这条判定就对了？

题面已经说"G 是无向连通图，|E| > 0"——连通性是前提，无需自己验。在这个前提下，EL 路径（即图论里的欧拉路径 / 欧拉回路）的存在性等价于：

• 奇度顶点数 = 0 ⇒ 存在欧拉回路（起点 = 终点）；
• 奇度顶点数 = 2 ⇒ 存在欧拉路径（从一个奇度点出发，到另一个奇度点结束）。

编者注（生僻术语）：对无向图来说，"奇度顶点的个数一定是偶数"是握手定理的推论——所以题面说"奇度顶点个数为不大于 2 的偶数"等同于 "{0, 2} 中的一个"。换句话说：奇度数 = 1 或 3 在无向图里根本不可能，但代码里仍按"oddCount ∈ {0, 2}"判定是最安全的写法。

邻接矩阵下顶点度的算法：第 行的所有元素之和就是顶点 的度数（邻接矩阵对称，第 列也行）。注意——这个写法假设图无自环；如果存在自环 ，标准定义自环要算 2 度，扫一行只算了 1，需另做处理。本题按"无自环"的常规假设来。

(2) 代码实现

#define MAXV 100

typedef struct {
    int  numVertices, numEdges;
    char VerticesList[MAXV];
    int  Edge[MAXV][MAXV];
} MGraph;

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

    for (int i = 0; i < n; i++) {
        // 顶点 i 的度 = 邻接矩阵第 i 行的非 0 项数
        int deg = 0;
        for (int j = 0; j < n; j++) deg += G.Edge[i][j];

        // 度为奇数则计数
        if (deg % 2 == 1) oddCount++;
    }

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

关键点说明：

• 不需要做连通性检查：题面已保证连通，不必再写 BFS/DFS 验。如果题面没保证（变种题），还要先验"图连通"或"边都集中在同一连通分量"。
• 不必算具体度值，知"奇偶"就够：可以让代码更紧凑——int deg = 0; for j: deg += G[i][j]; if (deg & 1) oddCount++;。这里给的写法把"算度"和"判奇偶"分开，更易读。
• 奇度顶点数 ≥ 4 直接返 0：比如 oddCount > 2 提前 break 也行，但 n ≤ MAXV 一般不大，不剪枝写起来更简洁。

(3) 复杂度分析

• 时间复杂度 ：外层扫 n 个顶点，内层扫一行 n 个元素；与邻接矩阵的存储规模相当，已是该存储下的下界。
• 空间复杂度 ：除入参图 G 外，只用了 oddCount、deg、i、j 几个标量，与图规模无关。