欧拉路径与回路

概念讲解

基本概念

  • 欧拉路径： 经过图中每条边恰好一次的路径
  • 欧拉回路： 经过图中每条边恰好一次并回到起点的回路

判定条件

无向图

  • 欧拉回路：所有顶点的度数都是偶数
  • 欧拉路径：恰好有两个顶点的度数是奇数

有向图

  • 欧拉回路：所有顶点的入度等于出度
  • 欧拉路径：恰好有一个顶点出度比入度大 1，一个顶点入度比出度大 1

实现

Hierholzer 算法

123456789101112131415161718192021222324const int N = 100005;
vector<pair<int, int>> graph[N];
bool visited[N];
vector<int> path;

void dfs(int u) {
    while (!graph[u].empty()) {
        auto [v, id] = graph[u].back();
        graph[u].pop_back();
        
        if (!visited[id]) {
            visited[id] = true;
            dfs(v);
        }
    }
    
    path.push_back(u);
}

vector<int> eulerPath(int start) {
    dfs(start);
    reverse(path.begin(), path.end());
    return path;
}

时间复杂度： O(E)

考点分析

初赛考查方式

  1. 选择题： 欧拉路径的判定
  2. 程序阅读： 理解欧拉路径算法
  3. 编程题： 欧拉路径应用

常见题型

  • 欧拉路径判定
  • 欧拉回路求解

例题精讲

例题 1：欧拉路径

题目： 求图中的欧拉路径。

解答：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int N = 100005;
vector<int> graph[N];
int inDegree[N], outDegree[N];
vector<int> path;

void dfs(int u) {
    while (!graph[u].empty()) {
        int v = graph[u].back();
        graph[u].pop_back();
        dfs(v);
    }
    path.push_back(u);
}

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        inDegree[v]++;
        outDegree[u]++;
    }
    
    // 找起点
    int start = 1;
    for (int i = 1; i <= n; i++) {
        if (outDegree[i] - inDegree[i] == 1) {
            start = i;
            break;
        }
    }
    
    dfs(start);
    
    reverse(path.begin(), path.end());
    
    for (int v : path) {
        cout << v << " ";
    }
    cout << endl;
    
    return 0;
}

练习题

  1. 洛谷 P1341 无序字母对
查看答案

思路：将字母对看作边，求欧拉路径。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 130;
vector<int> graph[N];
int inDegree[N], outDegree[N];
int parent[N];

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

void dfs(int u) {
    while (!graph[u].empty()) {
        int v = graph[u].back();
        graph[u].pop_back();
        dfs(v);
    }
    cout << (char)u;
}

int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < 128; i++) parent[i] = i;
    
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int u = s[0], v = s[1];
        graph[u].push_back(v);
        outDegree[u]++;
        inDegree[v]++;
        parent[find(u)] = find(v);
    }
    
    // 找起点
    int start = -1, end = -1;
    bool valid = true;
    for (int i = 0; i < 128; i++) {
        if (outDegree[i] - inDegree[i] == 1) {
            if (start != -1) { valid = false; break; }
            start = i;
        } else if (inDegree[i] - outDegree[i] == 1) {
            if (end != -1) { valid = false; break; }
            end = i;
        } else if (inDegree[i] != outDegree[i]) {
            valid = false;
            break;
        }
    }
    
    if (start == -1) {
        for (int i = 0; i < 128; i++) {
            if (outDegree[i] > 0) {
                start = i;
                break;
            }
        }
    }
    
    // 排序
    for (int i = 0; i < 128; i++) {
        sort(graph[i].begin(), graph[i].end());
    }
    
    dfs(start);
    cout << endl;
    
    return 0;
}
  1. 洛谷 P2731 [USACO3.3] 骑马修栅栏
查看答案

思路：欧拉路径，注意起点选择。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 505;
vector<int> graph[N];
int degree[N];
vector<int> path;

void dfs(int u) {
    while (!graph[u].empty()) {
        int v = graph[u].back();
        graph[u].pop_back();
        dfs(v);
    }
    path.push_back(u);
}

int main() {
    int m;
    cin >> m;
    
    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]++;
    }
    
    // 排序
    for (int i = 1; i <= 500; i++) {
        sort(graph[i].begin(), graph[i].end());
    }
    
    // 找起点
    int start = 1;
    for (int i = 1; i <= 500; i++) {
        if (degree[i] % 2 == 1) {
            start = i;
            break;
        }
    }
    
    dfs(start);
    
    reverse(path.begin(), path.end());
    for (int v : path) {
        cout << v << endl;
    }
    
    return 0;
}
  1. 洛谷 P1127 词链
查看答案

思路：将单词看作边，首尾字母看作点，求欧拉路径。

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 26;
vector<pair<int, string>> graph[N];
int inDegree[N], outDegree[N];
vector<string> path;

void dfs(int u) {
    while (!graph[u].empty()) {
        auto [v, word] = graph[u].back();
        graph[u].pop_back();
        dfs(v);
        path.push_back(word);
    }
}

int main() {
    int n;
    cin >> n;
    
    vector<string> words(n);
    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }
    
    sort(words.begin(), words.end());
    
    for (string& word : words) {
        int u = word[0] - 'a';
        int v = word.back() - 'a';
        graph[u].push_back({v, word});
        outDegree[u]++;
        inDegree[v]++;
    }
    
    // 找起点
    int start = -1, end = -1;
    bool valid = true;
    for (int i = 0; i < 26; i++) {
        if (outDegree[i] - inDegree[i] == 1) {
            if (start != -1) { valid = false; break; }
            start = i;
        } else if (inDegree[i] - outDegree[i] == 1) {
            if (end != -1) { valid = false; break; }
            end = i;
        } else if (inDegree[i] != outDegree[i]) {
            valid = false;
            break;
        }
    }
    
    if (start == -1) {
        for (int i = 0; i < 26; i++) {
            if (outDegree[i] > 0) {
                start = i;
                break;
            }
        }
    }
    
    dfs(start);
    
    reverse(path.begin(), path.end());
    
    for (int i = 0; i < path.size(); i++) {
        if (i > 0) cout << ".";
        cout << path[i];
    }
    cout << endl;
    
    return 0;
}

易错点

⚠️ 注意：

  1. 欧拉路径的判定条件很重要
  2. Hierholzer 算法要注意边的删除
  3. 欧拉路径和欧拉回路不同
  4. 注意图的连通性