2021 年第 41 题

题目描述

给定一个连通无向图 G，判断该图是否存在欧拉回路或欧拉路径。若存在，返回相应类型；否则返回不存在。

解题思路

这题只要抓住无向图的度数性质即可。

• 所有顶点度数都为偶数：存在欧拉回路。
• 恰有 2 个顶点度数为奇数：存在欧拉路径但不存在欧拉回路。
• 其余情况：不存在欧拉路径。

因为题目给的是连通图，所以不需要额外再判连通性；若原题未保证连通，则还要加上连通性判断。

手算示例

图中顶点度数分别为：

a: 2
b: 3
c: 2
d: 3

奇度顶点有 b、d 两个。

所以：

存在欧拉路径
不存在欧拉回路

Python 实现

def euler_type(adj_matrix):
    n = len(adj_matrix)
    odd_count = 0

    for i in range(n):
        degree = sum(adj_matrix[i])
        if degree % 2 == 1:
            odd_count += 1

    if odd_count == 0:
        return "Euler Circuit"
    if odd_count == 2:
        return "Euler Path"
    return "Not Eulerian"

复杂度分析

• 时间复杂度：O(n^2)，邻接矩阵统计每个顶点的度
• 空间复杂度：O(1)，忽略输入存储

易错点

• 无向图中顶点度数等于对应行元素之和。
• “有欧拉路径”不等于“一定有欧拉回路”。
• 若题目未明确保证图连通，还必须补充连通性判断。

对应题

来源	题目	相似度	主要差异
PAT 甲级	1126 Eulerian Path	95%	真题更强调按定义判断图类型

难度

⭐️