Đường đi Euler

Wiki › Thuật toán › Thuật toán đồ thị

huunguyen · Last updated 8, Tháng 4, 2026, 15:26

Đường đi Euler là đường đi qua mỗi cạnh đúng một lần. Chu trình Euler là đường đi Euler bắt đầu và kết thúc tại cùng một đỉnh.

Điều kiện tồn tại

Đồ thị vô hướng:

Chu trình Euler: Đồ thị liên thông và mọi đỉnh có bậc chẵn.
Đường đi Euler: Đồ thị liên thông và đúng 2 đỉnh có bậc lẻ (đây là đỉnh đầu và cuối).

Đồ thị có hướng:

Chu trình Euler: Đồ thị liên thông yếu và $\deg^{+} (u) = \deg^{-} (u)$ với mọi $u$ .
Đường đi Euler: Đồ thị liên thông yếu, đúng một đỉnh có $\deg^{+} - \deg^{-} = 1$ (đỉnh đầu), đúng một đỉnh có $\deg^{-} - \deg^{+} = 1$ (đỉnh cuối), còn lại bằng nhau.

Thuật toán Hierholzer — $O (V + E)$

Dùng stack để xây đường đi Euler. Tránh duyệt cạnh đã đi bằng con trỏ ptr.

// Đồ thị vô hướng
const int MAXN = 2e5 + 5;
vector<pair<int,int>> adj[MAXN];  // {neighbor, edge_id}
bool used_edge[MAXN];             // đánh dấu cạnh đã dùng
int ptr[MAXN];                    // con trỏ vị trí duyệt adj[u]

vector<int> euler_path;

void dfs(int u) {
    while (ptr[u] < (int)adj[u].size()) {
        auto [v, eid] = adj[u][ptr[u]++];
        if (used_edge[eid]) continue;
        used_edge[eid] = true;
        dfs(v);
    }
    euler_path.push_back(u);
}

// Gọi từ đỉnh bắt đầu, đảo ngược kết quả:
// dfs(start);
// reverse(euler_path.begin(), euler_path.end());

// Đồ thị có hướng
vector<int> adj[MAXN];
int ptr[MAXN];
vector<int> euler_path;

void dfs(int u) {
    while (ptr[u] < (int)adj[u].size()) {
        int v = adj[u][ptr[u]++];
        dfs(v);
    }
    euler_path.push_back(u);
}

Ví dụ đầy đủ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n+1);
    vector<int> deg(n+1, 0);

    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        deg[u]++; deg[v]++;
    }

    // Tìm đỉnh bắt đầu
    int start = 1;
    int odd_count = 0;
    for (int i = 1; i <= n; i++)
        if (deg[i] % 2 == 1) { odd_count++; start = i; }

    if (odd_count != 0 && odd_count != 2) {
        cout << "Không tồn tại đường đi Euler\n";
        return 0;
    }

    vector<bool> used(m, false);
    vector<int> ptr(n+1, 0);
    vector<int> path;

    function<void(int)> dfs = [&](int u) {
        while (ptr[u] < (int)adj[u].size()) {
            auto [v, eid] = adj[u][ptr[u]++];
            if (used[eid]) continue;
            used[eid] = true;
            dfs(v);
        }
        path.push_back(u);
    };

    dfs(start);
    reverse(path.begin(), path.end());

    if ((int)path.size() != m + 1) {
        cout << "Đồ thị không liên thông\n";
        return 0;
    }

    for (int u : path) cout << u << " ";
}

Ứng dụng

Chinese Postman Problem: Tìm chu trình ngắn nhất đi qua mọi cạnh (với trọng số).
De Bruijn sequence: Xây chuỗi chứa mọi substring độ dài $k$ — đưa về bài toán Euler trên đồ thị de Bruijn.
DNA sequencing: Assembly đoạn gen từ overlap.
Bài toán vẽ hình không nhấc bút.

Độ phức tạp

$O (V + E)$ — mỗi cạnh được xét đúng một lần nhờ con trỏ ptr.

Bình luận

Không có bình luận tại thời điểm này.