FC01-判断无向连通图中是否存在 EL 路径¶

已知无向连通图\(G\)由顶点集\(V\)和边集\(E\)组成，且\(|E|>0\)。当\(G\)中度为奇数的顶点个数为不大于2的偶数（即0或2）时，\(G\)存在一条包含所有边且长度为\(|E|\)的路径（称为欧拉路径，EL路径）。设图\(G\)采用邻接矩阵存储，设计算法判断图中是否存在EL路径，若存在返回1，否则返回0。（2021年统考题）

代码实现¶

C
// 函数 IsExistEL：判断无向连通图中是否存在 EL 路径
// 参数：G - 图的邻接矩阵表示
// 返回值：存在 EL 路径返回 1，否则返回 0
int IsExistEL(MGraph G) {
    int count = 0; // 用于统计度数为奇数的顶点个数

    // 遍历图中的每个顶点
    for (int i = 0; i < G.numver; i++) {
        int degree = 0; // 当前顶点的度数

        // 计算顶点 i 的度数（与顶点 i 相邻的边数）
        for (int j = 0; j < G.numver; j++) {
            degree += G.Edge[i][j]; // 累加邻接矩阵第 i 行的值
        }

        // 如果当前顶点的度数为奇数，则计数器加 1
        if (degree % 2 != 0) {
            count++;
        }
    }

    // 根据欧拉路径的判定条件判断是否存在 EL 路径
    // 条件：度数为奇数的顶点个数为 0 或 2
    if (count == 0 || count == 2) {
        return 1; // 存在 EL 路径
    } else {
        return 0; // 不存在 EL 路径
    }
}

代码逻辑解析¶

1. 基本概念¶

EL 路径：包含图中所有边且每条边只经过一次的路径（欧拉路径）
度数：与顶点相连的边的条数
奇度顶点：度数为奇数的顶点
偶度顶点：度数为偶数的顶点

2. 欧拉路径判定定理¶

对于无向连通图，存在欧拉路径的充要条件是： - 度数为奇数的顶点个数为 0 或 2

特殊情况说明： - 奇度顶点个数为 0：存在欧拉回路（起点和终点相同） - 奇度顶点个数为 2：存在欧拉路径（起点和终点分别为两个奇度顶点）

3. 算法思路¶

遍历图中每个顶点
计算每个顶点的度数
统计度数为奇数的顶点个数
根据判定定理判断是否存在欧拉路径

4. 度数计算方法¶

C
// 在邻接矩阵中，顶点 i 的度数等于第 i 行所有元素的和
for (int j = 0; j < G.numver; j++) {
    degree += G.Edge[i][j];
}

在无向图的邻接矩阵中： - G.Edge[i][j] = 1 表示顶点 i 和顶点 j 之间有边 - G.Edge[i][j] = 0 表示顶点 i 和顶点 j 之间无边 - 顶点 i 的度数 = 第 i 行中值为 1 的元素个数

时间复杂度分析¶

1. 外层循环¶

遍历所有顶点：O(V)，其中 V 是顶点数

2. 内层循环¶

对每个顶点计算度数：O(V)

3. 总体时间复杂度¶

嵌套循环：O(V × V) = O(V²)

空间复杂度分析¶

1. 额外空间使用¶

只使用了常量级别的局部变量：count, degree, i, j
没有使用额外的数据结构

2. 总体空间复杂度¶

O(1) - 常数空间复杂度

较难理解部分的说明¶

1. 欧拉路径判定定理的证明¶

必要性证明（存在欧拉路径 ⇒ 奇度顶点个数为 0 或 2）：¶

在欧拉路径中： - 中间顶点：每次进入都要离开，所以经过偶数次，度数为偶数 - 起点顶点：如果是欧拉回路，度数为偶数；如果是欧拉路径，度数为奇数 - 终点顶点：如果是欧拉回路，度数为偶数；如果是欧拉路径，度数为奇数

因此，奇度顶点最多 2 个。

图解说明：¶

Text Only

情况1：欧拉回路（奇度顶点数 = 0）
A ── B
|    |
D ── C
路径：A→B→C→D→A（起点=终点，都是偶度）

情况2：欧拉路径（奇度顶点数 = 2）
A ── B ── C
|         |
D ────────
路径：A→B→C（起点A和终点C都是奇度）

2. 邻接矩阵度数计算示例¶

假设图的邻接矩阵如下：

Text Only
1 2 3 4 5	`A B C D A [ 0 1 1 1 ] 度数 = 3（奇数） B [ 1 0 0 1 ] 度数 = 2（偶数） C [ 1 0 0 1 ] 度数 = 2（偶数） D [ 1 1 1 0 ] 度数 = 3（奇数）`

奇度顶点个数 = 2（顶点 A 和 D），因此存在欧拉路径。

延伸知识点¶

1. 欧拉回路判定¶

C
// 判断是否存在欧拉回路
int IsExistEulerCircuit(MGraph G) {
    int count = 0;
    for (int i = 0; i < G.numver; i++) {
        int degree = 0;
        for (int j = 0; j < G.numver; j++) {
            degree += G.Edge[i][j];
        }
        if (degree % 2 != 0) {
            count++;
        }
    }

    // 欧拉回路：所有顶点度数都为偶数
    return (count == 0) ? 1 : 0;
}

2. 邻接表存储的优化版本¶

C
// 对于邻接表存储的图，可以优化时间复杂度
int IsExistELOptimized(ALGraph G) {
    int count = 0;
    for (int i = 0; i < G.numver; i++) {
        // 直接获取顶点的度数（邻接表中链表长度）
        int degree = G.adjlist[i].degree; // 假设有度数字段
        if (degree % 2 != 0) {
            count++;
        }
    }

    return (count == 0 || count == 2) ? 1 : 0;
}
// 时间复杂度：O(V)

3. 实际构造欧拉路径算法¶

C
// Fleury 算法构造欧拉路径
void Fleury(MGraph G, int start) {
    int current = start;
    printf("欧拉路径: %d", current);

    while (hasEdges(G)) { // 还有边未访问
        int next = findNextEdge(G, current); // 找到下一条边
        removeEdge(G, current, next); // 删除已访问的边
        printf(" -> %d", next);
        current = next;
    }
    printf("\n");
}

4. 相关图论概念¶

汉密尔顿路径：经过每个顶点恰好一次的路径
哈夫曼编码：基于树的最优前缀编码
最小生成树：连接所有顶点的最小权重边集
最短路径：两点间权重和最小的路径

5. 实际应用场景¶

网络路由：数据包传输路径规划
电路设计：电路板布线优化
物流配送：快递配送路线规划
游戏设计：迷宫求解、棋盘遍历
DNA 测序：基因序列拼接

6. 算法优化技巧¶

C
// 提前终止优化
int IsExistELEarlyTermination(MGraph G) {
    int count = 0;
    for (int i = 0; i < G.numver && count <= 2; i++) {
        int degree = 0;
        for (int j = 0; j < G.numver; j++) {
            degree += G.Edge[i][j];
        }
        if (degree % 2 != 0) {
            count++;
        }
    }

    // 如果奇度顶点超过 2 个，提前返回
    return (count <= 2 && (count == 0 || count == 2)) ? 1 : 0;
}

这种方法体现了图论经典定理应用的思想，通过数学定理将复杂的路径存在性问题转化为简单的度数统计问题，是算法设计中理论指导实践的典型例子。