欧拉图(Eulerian Graph)

欧拉通路 (Eulerian Path/Trail)：又称欧拉路径，通过图中每一条边恰好一次的通路（顶点可以重复访问）。

欧拉回路 (Eulerian Circuit/Cycle)：首尾顶点相接的欧拉通路（即一个起点和终点相同的欧拉通路）。

具有欧拉回路的无向图称为欧拉图。
具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。

非形式化地讲，欧拉图就是从任意一个点开始都可以一笔画完整个图，半欧拉图必须从某个点开始才能一笔画完整个图。

要判断一个无向图是否为欧拉图或半欧拉图，有以下两个必要条件：

  1. 欧拉图：图中所有顶点的度数均为偶数。
  2. 半欧拉图：图中恰有两个顶点的度数为奇数。

如果一个无向图满足上述第一个条件，则它是欧拉图。如果满足第二个条件，则它是半欧拉图。

对于有向图（有向欧拉图）：

  1. 有向欧拉图：每个顶点的入度等于出度，并且整个图必须是强连通图。这意味着，从图的任意一个顶点，可以沿着有向边到达任何其他顶点。
  2. 有向半欧拉图：图中只有两个顶点的入度与出度不相等，其中一个顶点的出度比入度大1，另一个顶点的入度比出度大1。其余所有顶点的入度必须等于出度。图必须是弱连通的，即在将所有边看作无向边后，图必须连通。

代码：判断是否为欧拉图或半欧拉图

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/****************************************************************
 * 代码作者: Alex Li
 * 创建时间: 2026-06-06 11:57
 * 最后修改: 2026-06-06 12:18
 * 文件描述: 在输入保证为连通无向图时，判断其是否为欧拉图或半欧拉图；时间复杂度 O(n + m)
 * 核心算法: 在连通图前提下，只需统计奇度点个数即可判断欧拉回路或欧拉通路
****************************************************************/
#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<int>> graph;
vector<int> degree;

bool isEulerianGraph() {
    // 无向图存在欧拉回路，当且仅当所有顶点度数均为偶数。
    for (int i = 1; i <= n; ++i) {
        if (degree[i] % 2 != 0) {
            return false;
        }
    }
    return true;
}

bool hasTrail() {
    int oddCount = 0;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] % 2 != 0) {
            ++oddCount;
        }
    }
    // 无向图存在欧拉通路，当且仅当奇度点个数为 0 或 2。
    return oddCount == 0 || oddCount == 2;
}

int main() {
    cin >> n >> m;

    graph.assign(n + 1, vector<int>());
    degree.assign(n + 1, 0);

    // 输入前提：该无向图是连通图。
    // 输入格式：
    // n m
    // 接下来 m 行，每行一条无向边 u v
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // 无向边要双向加入邻接表，同时分别统计两个端点的度数。
        graph[u].push_back(v);
        graph[v].push_back(u);
        ++degree[u];
        ++degree[v];
    }

    if (isEulerianGraph()) {
        cout << "Eulerian graph\n";
    } else if (hasTrail()) {
        cout << "Semi-Eulerian graph\n";
    } else {
        cout << "Not Eulerian\n";
    }

    return 0;
}

Previous Quiz
Back to Lesson
Next Topic