Thi đấu

Chu Trình và Đường Đi Euler: Thuật Toán Hierholzer O(V + E)

Thuật toán Hierholzer tìm chu trình hoặc đường đi Euler đi qua mỗi cạnh của đồ thị đúng một lần trong thời gian tuyến tính O(V + E) bằng phương pháp đi nối vòng khép kín.

Chu Trình và Đường Đi Euler: Thuật Toán Hierholzer O(V + E)

Năm 1736, bài toán Bảy cây cầu ở Königsberg đã đi vào lịch sử như phát súng khai sinh ra ngành Lý thuyết Đồ thị và Tô-pô học hiện đại. Thành phố Königsberg có 7 cây cầu bắc qua sông Pregel nối liền hai hòn đảo lớn với đất liền. Câu hỏi đặt ra là: Liệu có thể xuất phát từ một điểm bất kỳ, đi qua mỗi cây cầu đúng một lần rồi quay trở lại điểm xuất phát hay không?. Nhà toán học vĩ đại Leonhard Euler đã chứng minh câu trả lời là không thể, đồng thời đặt nền móng cho khái niệm Chu trình Euler và Đường đi Euler.

Trong các kỳ thi lập trình thi đấu từ Học sinh giỏi Quốc gia đến ICPC, bài toán Euler thường xuất hiện dưới dạng khôi phục xâu ký tự từ các đoạn con kề nhau (bài toán De Bruijn Sequence trong sinh học tính toán), bài toán đi qua mọi tuyến đường giao thông với chi phí nhỏ nhất (Chinese Postman Problem), hay sắp xếp lịch trình vệ tinh.

Bài viết này sẽ trình bày trọn vẹn điều kiện tồn tại Euler trên cả đồ thị vô hướng và có hướng, phân tích chi tiết thuật toán Hierholzer đạt độ phức tạp tuyến tính \(O(V + E)\), và hướng dẫn kỹ thuật cài đặt bằng ngăn xếp (stack) để loại bỏ hoàn toàn nguy cơ tràn bộ nhớ đệ quy.

1. Điều kiện tồn tại Chu trình và Đường đi Euler

Một Chu trình Euler (Eulerian Circuit) là một chu trình đóng đi qua mỗi cạnh của đồ thị đúng một lần. Một Đường đi Euler (Eulerian Path) là một đường đi mở đi qua mỗi cạnh đúng một lần (điểm bắt đầu và điểm kết thúc khác nhau).

Chu Trình & Đường Đi Euler (Thuật Toán Hierholzer O(V + E)) Đi qua mọi cạnh đúng một lần bằng ngăn xếp (stack) không đệ quy, tránh tràn bộ nhớ stack Điều kiện tồn tại Euler (Đồ thị vô hướng) • Chu trình Euler: Mọi đỉnh đều có bậc chẵn • Đường đi Euler: Có đúng 2 đỉnh bậc lẻ • Đồ thị phải liên thông (xét các đỉnh có cạnh) Kỹ thuật đánh dấu cạnh đã đi: Gán used_edge[edge_id] = true Dùng pop_back() trên danh sách kề để đạt O(1) mỗi cạnh Chạy tay Hierholzer đồ thị tam giác (0, 1, 2) Cạnh: e0(0-1), e1(1-2), e2(2-0) -> deg = [2, 2, 2] • Stack ban đầu: [0] • Đi e0 -> Stack [0, 1]; Đi e1 -> Stack [0, 1, 2] • Đi e2 -> Stack [0, 1, 2, 0] • Đỉnh 0 hết cạnh kề -> pop dần rồi đảo ngược thứ tự: Chu trình: 0 -> 1 -> 2 -> 0 (Đủ 3 cạnh!)
Chu Trình Euler (Hierholzer) Đi qua mọi cạnh đúng một lần O(V + E) Điều kiện tồn tại: • Chu trình: Mọi đỉnh đều có bậc chẵn • Đường đi: Đúng 2 đỉnh có bậc lẻ Dùng stack tránh lỗi tràn bộ nhớ đệ quy Ví dụ đồ thị tam giác 3 đỉnh: Bậc các đỉnh: deg(0)=2, deg(1)=2, deg(2)=2 Hierholzer stack: [0, 1, 2, 0] => Chu trình Euler: 0 -> 1 -> 2 -> 0 Đi qua đúng 3 cạnh phân biệt và khép kín
Quy trình Hierholzer tìm chu trình Euler trên đồ thị tam giác 3 đỉnh bằng ngăn xếp (stack) không đệ quy.

Đối với đồ thị vô hướng

Đồ thị phải liên thông (xét trên các đỉnh có bậc lớn hơn 0):

  1. Tồn tại Chu trình Euler \(\iff\) Mọi đỉnh đều có bậc chẵn (deg[u] % 2 == 0).
  2. Tồn tại Đường đi Euler \(\iff\) Đúng 2 đỉnh có bậc lẻ (hai đỉnh này chính là điểm xuất phát và điểm kết thúc), các đỉnh còn lại đều có bậc chẵn.

Đối với đồ thị có hướng

Đồ thị phải liên thông yếu (khi bỏ chiều mũi tên):

  1. Tồn tại Chu trình Euler \(\iff\) Bán bậc vào bằng bán bậc ra tại mọi đỉnh (in_deg[u] == out_deg[u]).
  2. Tồn tại Đường đi Euler \(\iff\) Tồn tại đúng một đỉnh có out_deg - in_deg = 1 (đỉnh bắt đầu), đúng một đỉnh có in_deg - out_deg = 1 (đỉnh kết thúc), và mọi đỉnh khác đều có in_deg == out_deg.

2. Thuật toán Hierholzer tuyến tính O(V + E)

Thuật toán của Carl Hierholzer (công bố năm 1873) là phương pháp tối ưu nhất để tìm chu trình Euler. Nguyên lý của thuật toán là:

  1. Bắt đầu từ một đỉnh hợp lệ \(S\). Đi theo các cạnh chưa thăm cho đến khi bị "mắc kẹt" tại một đỉnh không còn cạnh nào đi tiếp.
  2. Vì mọi đỉnh đều có bậc chẵn, đỉnh duy nhất mà ta có thể bị mắc kẹt bắt buộc phải chính là đỉnh xuất phát \(S\) (ta đã tìm được một chu trình con). Với đường đi Euler (đúng 2 đỉnh bậc lẻ), ta xuất phát từ một đỉnh bậc lẻ; lần mắc kẹt đầu tiên khi đó xảy ra ở đỉnh bậc lẻ còn lại, và cách làm với ngăn xếp bên dưới vẫn ghép đúng các chu trình con vào đường đi.
  3. Nếu trên chu trình con này vẫn còn đỉnh nào có cạnh kề chưa thăm, ta lại tiếp tục mở rộng chu trình con mới từ đỉnh đó rồi ghép lồng vào chu trình lớn.

Cài đặt bằng Ngăn xếp (Stack) tránh Stack Overflow

Trong các bài toán thi đấu với \(E = 2 \times 10^5\), nếu cài đặt đệ quy DFS ngây thơ, độ sâu đệ quy sẽ đạt tới \(2 \times 10^5\), lập tức gây lỗi Runtime Error (Stack Overflow).

Cách cài đặt an toàn tuyệt đối là dùng ngăn xếp tự tạo:

  • Đẩy đỉnh xuất phát vào stack: st.push(start).
  • Khi stack chưa rỗng:
    • Lấy đỉnh \(u = \text{st.top()}\).
    • Nếu \(u\) còn cạnh kề chưa đi: lấy cạnh kề \((u, v)\) ra, đánh dấu cạnh đã đi, và đẩy \(v\) vào stack (st.push(v)).
    • Nếu \(u\) đã hết sạch cạnh kề chưa đi: đỉnh \(u\) không thể đi tiếp được nữa \(\to\) lấy \(u\) ra khỏi stack và đưa vào mảng kết quả: path.push_back(u); st.pop();.
  • Sau khi kết thúc, đảo ngược mảng path để thu được thứ tự các đỉnh trên chu trình Euler!

3. Cài đặt C++17 và Python 3 chuẩn thi đấu

Dưới đây là mã nguồn chuẩn cho đồ thị vô hướng. Hàm find_euler(start) đếm các đỉnh bậc lẻ: không có đỉnh bậc lẻ thì tìm chu trình Euler từ start; đúng 2 đỉnh bậc lẻ thì tìm đường đi Euler, xuất phát từ start nếu đó là một đỉnh bậc lẻ, ngược lại tự đổi sang đỉnh bậc lẻ đầu tiên; các trường hợp còn lại không có chu trình hay đường đi Euler. Đi xong, hàm so số đỉnh trên đường với số cạnh cộng 1: nếu còn cạnh chưa đi (đồ thị không liên thông) thì trả về mảng rỗng. Con trỏ ptr[u] giúp mỗi phần tử của danh sách kề chỉ bị xét một lần, nên tổng thời gian là \(O(V + E)\). Chương trình in 0 1 2 0 cho tam giác, 0 1 2 cho đường 0-1-2 (gọi từ đỉnh 1 bậc chẵn, hàm đổi sang đỉnh 0) và dòng báo không có cho hai tam giác rời nhau.

Cài đặt C++17

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

// Tim chu trinh hoac duong di Euler tren do thi vo huong bang thuat toan Hierholzer
struct EulerUndirected {
    int n, edges = 0;                    // so dinh, so canh da them
    vector<vector<pair<int, int>>> adj;  // Luu cap: {dinh_ke, id_canh}
    vector<int> deg, ptr;                // ptr[u]: vi tri canh ke tiep theo can xet cua u
    vector<bool> used_edge;

    EulerUndirected(int n, int m) : n(n), adj(n), deg(n, 0), ptr(n, 0), used_edge(m, false) {}

    void add_edge(int u, int v, int id) { // id chay tu 0 den m - 1
        adj[u].push_back({v, id});
        adj[v].push_back({u, id});
        deg[u]++;
        deg[v]++;
        edges++;
    }

    // Tra ve day dinh cua chu trinh Euler (moi dinh bac chan) hoac duong di Euler (dung 2 dinh bac le);
    // tra ve {} neu do thi khong co chu trinh hay duong di Euler
    vector<int> find_euler(int start = 0) {
        vector<int> odd;
        for (int i = 0; i < n; ++i)
            if (deg[i] % 2 != 0) odd.push_back(i);
        if (odd.size() == 2) {
            // Duong di Euler bat buoc xuat phat tu mot trong hai dinh bac le
            if (start != odd[0] && start != odd[1]) start = odd[0];
        } else if (!odd.empty()) {
            return {}; // 4, 6, ... dinh bac le: khong co
        } else if (deg[start] == 0) {
            // Chu trinh Euler: xuat phat tu mot dinh co canh
            for (int i = 0; i < n; ++i) if (deg[i] > 0) { start = i; break; }
        }

        stack<int> st;
        st.push(start);
        vector<int> path;

        while (!st.empty()) {
            int u = st.top();
            // Bo qua cac canh da di (moi canh nam trong danh sach ke cua ca hai dau)
            while (ptr[u] < (int)adj[u].size() && used_edge[adj[u][ptr[u]].second]) ptr[u]++;
            if (ptr[u] < (int)adj[u].size()) {
                auto [v, id] = adj[u][ptr[u]];
                used_edge[id] = true;
                st.push(v);
            } else {
                // Khong con canh di tiep -> day vao ket qua
                path.push_back(u);
                st.pop();
            }
        }
        // Con canh chua di: cac canh khong cung mot thanh phan lien thong
        if ((int)path.size() != edges + 1) return {};
        reverse(path.begin(), path.end());
        return path;
    }
};

void print_walk(const vector<int>& walk) {
    if (walk.empty()) {
        cout << "Khong co chu trinh hay duong di Euler\n";
        return;
    }
    for (int i = 0; i < (int)walk.size(); ++i) {
        cout << walk[i] << (i + 1 == (int)walk.size() ? '\n' : ' ');
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Do thi tam giac 3 dinh, 3 canh: 0-1, 1-2, 2-0 -> moi dinh bac chan: chu trinh Euler
    EulerUndirected triangle(3, 3);
    triangle.add_edge(0, 1, 0);
    triangle.add_edge(1, 2, 1);
    triangle.add_edge(2, 0, 2);
    print_walk(triangle.find_euler(0));

    // Duong 0-1-2: dinh 0 va 2 bac le -> duong di Euler; goi tu dinh 1 (bac chan), ham doi sang dinh 0
    EulerUndirected path_graph(3, 2);
    path_graph.add_edge(0, 1, 0);
    path_graph.add_edge(1, 2, 1);
    print_walk(path_graph.find_euler(1));

    // Hai tam giac roi nhau: moi dinh bac chan nhung khong lien thong -> khong co
    EulerUndirected two_triangles(6, 6);
    int e[6][2] = {{0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}, {5, 3}};
    for (int i = 0; i < 6; ++i) two_triangles.add_edge(e[i][0], e[i][1], i);
    print_walk(two_triangles.find_euler(0));
    return 0;
}

Cài đặt Python 3

import sys

class EulerUndirected:
    def __init__(self, n: int, m: int):
        self.n = n
        self.edges = 0                   # so canh da them
        self.adj = [[] for _ in range(n)]
        self.deg = [0] * n
        self.ptr = [0] * n               # ptr[u]: vi tri canh ke tiep theo can xet cua u
        self.used_edge = [False] * m

    def add_edge(self, u: int, v: int, edge_id: int):
        self.adj[u].append((v, edge_id))
        self.adj[v].append((u, edge_id))
        self.deg[u] += 1
        self.deg[v] += 1
        self.edges += 1

    def find_euler(self, start: int = 0) -> list[int]:
        odd = [v for v in range(self.n) if self.deg[v] % 2 != 0]
        if len(odd) == 2:
            if start not in odd:
                start = odd[0]           # duong di Euler phai xuat phat tu dinh bac le
        elif odd:
            return []                    # 4, 6, ... dinh bac le: khong co
        elif self.deg[start] == 0:
            start = next((v for v in range(self.n) if self.deg[v] > 0), start)
        st = [start]
        path = []
        while st:
            u = st[-1]
            while self.ptr[u] < len(self.adj[u]) and self.used_edge[self.adj[u][self.ptr[u]][1]]:
                self.ptr[u] += 1
            if self.ptr[u] < len(self.adj[u]):
                v, edge_id = self.adj[u][self.ptr[u]]
                self.used_edge[edge_id] = True
                st.append(v)
            else:
                path.append(u)
                st.pop()
        if len(path) != self.edges + 1:
            return []                    # con canh chua di: do thi khong lien thong
        path.reverse()
        return path

def print_walk(walk: list[int]):
    if not walk:
        print('Khong co chu trinh hay duong di Euler')
    else:
        print(*walk)

def main():
    triangle = EulerUndirected(3, 3)
    triangle.add_edge(0, 1, 0)
    triangle.add_edge(1, 2, 1)
    triangle.add_edge(2, 0, 2)
    print_walk(triangle.find_euler(0))
    path_graph = EulerUndirected(3, 2)
    path_graph.add_edge(0, 1, 0)
    path_graph.add_edge(1, 2, 1)
    print_walk(path_graph.find_euler(1))
    two_triangles = EulerUndirected(6, 6)
    for i, (u, v) in enumerate([(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)]):
        two_triangles.add_edge(u, v, i)
    print_walk(two_triangles.find_euler(0))

if __name__ == '__main__':
    main()

4. Phân biệt Chu trình Euler và Chu trình Hamilton

Rất nhiều thí sinh mới bắt đầu thường nhầm lẫn giữa chu trình Euler và chu trình Hamilton:

Đặc điểm Chu trình Euler (Eulerian Circuit) Chu trình Hamilton (Hamiltonian Circuit)
Định nghĩa Đi qua mỗi CẠNH đúng một lần Đi qua mỗi ĐỈNH đúng một lần
Độ phức tạp Tuyến tính \(O(V + E)\) (Dễ dàng giải quyết) NP-đầy đủ (chưa biết thuật toán đa thức)
Thuật toán Thuật toán Hierholzer Quay lui \(O(N!)\), DP Bitmask \(O(2^N \cdot N^2)\)
Kiểm tra Đếm bậc đỉnh (Chẵn / Lẻ) trong \(O(V)\) Không có điều kiện cần và đủ đơn giản

Bảng chạy tay chi tiết thuật toán Hierholzer với ngăn xếp

Xét đồ thị vô hướng gồm 4 đỉnh \(\{1, 2, 3, 4\}\) với các cạnh tạo thành một tam giác 1-2-3 và hai cạnh song song nối đỉnh 1 với đỉnh 4: Cạnh: \((1, 2), (2, 3), (3, 1), (1, 4), (4, 1)\). Tất cả các đỉnh đều có bậc chẵn (\(\text{deg}(1) = 4, \text{deg}(2) = 2, \text{deg}(3) = 2, \text{deg}(4) = 2\)). Bắt đầu từ đỉnh 1:

Bước Đỉnh trên đỉnh Stack Cạnh đi tiếp Đỉnh kề tiếp theo Hành động của Stack Trạng thái chu trình Euler
1 1 \((1, 2)\) 2 Push 2 Trống
2 2 \((2, 3)\) 3 Push 3 Trống
3 3 \((3, 1)\) 1 Push 1 Trống
4 1 \((1, 4)\) 4 Push 4 Trống
5 4 \((4, 1)\) 1 Push 1 Trống
6 1 Hết cạnh - Pop 1, thêm vào chu trình [1]
7 4 Hết cạnh - Pop 4, thêm vào chu trình [1, 4]
8 1 Hết cạnh - Pop 1, thêm vào chu trình [1, 4, 1]
9 3 Hết cạnh - Pop 3, thêm vào chu trình [1, 4, 1, 3]
10 2 Hết cạnh - Pop 2, thêm vào chu trình [1, 4, 1, 3, 2]
11 1 Hết cạnh - Pop 1, thêm vào chu trình [1, 4, 1, 3, 2, 1]

Đảo ngược chu trình thu được: 1 -> 2 -> 3 -> 1 -> 4 -> 1. Đây là một chu trình Euler hoàn hảo đi qua tất cả 5 cạnh của đồ thị đúng một lần!

Bốn lỗi cài đặt phổ biến khi tìm chu trình Euler

  1. Quên kiểm tra tính liên thông của các cạnh: Đồ thị thỏa mãn điều kiện bậc chẵn nhưng lại gồm nhiều thành phần liên thông riêng biệt (mỗi thành phần có cạnh). Trong trường hợp đó, thuật toán chỉ đi hết một thành phần và bỏ sót các cạnh ở thành phần khác. Luôn kiểm tra số lượng cạnh duyệt được có bằng tổng số cạnh của đồ thị hay không; code ở mục 3 làm việc này ở dòng if ((int)path.size() != edges + 1) return {};.

  2. Duyệt lại các cạnh đã đi qua trên danh sách kề: Nếu chỉ dùng mảng visited_edge mà không tối ưu con trỏ chỉ số cạnh hiện tại head[u], thuật toán có thể duyệt qua các cạnh đã bị xóa nhiều lần, làm độ phức tạp thoái hóa về \(O(V \cdot E)\) và bị TLE trên đồ thị dày. Kỹ thuật con trỏ tiến head[u] (code ở mục 3 gọi là ptr[u]) đảm bảo mỗi phần tử của danh sách kề chỉ bị xét đúng một lần.

  3. Chọn sai đỉnh xuất phát khi tìm đường đi Euler: Nếu đồ thị có đúng 2 đỉnh bậc lẻ, đường đi Euler bắt buộc phải xuất phát từ một trong hai đỉnh bậc lẻ này. Nếu xuất phát từ đỉnh bậc chẵn, thuật toán sẽ kết thúc sớm mà không thể đi hết mọi cạnh. Hàm find_euler ở mục 3 tự đổi đỉnh xuất phát sang một đỉnh bậc lẻ trong trường hợp này.

  4. Tràn ngăn xếp đệ quy khi đồ thị lớn: Với đồ thị có \(10^5\) cạnh, đệ quy sâu có thể gây lỗi tràn bộ nhớ ngăn xếp (Stack Overflow). Phiên bản khử đệ quy sử dụng cấu trúc dữ liệu std::stack được trình bày ở trên là giải pháp tuyệt đối an toàn cho mọi kích thước đồ thị.

Luyện ngay trên Big-O Coding

Để thực hành thành thạo thuật toán Hierholzer và phân tích chu trình trên đồ thị, hãy giải ngay các bài tập sau trên Big-O Coding:

Làm thế nào để xử lý đồ thị có đa cạnh (Multi-graph) hoặc khuyên (Self-loop) trong Hierholzer?

Cài đặt thuật toán Hierholzer ở trên gán cho mỗi cạnh một định danh duy nhất edge_id từ \(0\) đến \(M-1\). Bằng cách đánh dấu mảng boolean used_edge[edge_id] = true, thuật toán xử lý trơn tru cả đồ thị có nhiều cạnh nối cùng một cặp đỉnh lẫn cạnh khuyên tự nối một đỉnh vào chính nó mà không xảy ra bất kỳ lỗi vòng lặp nào.

Nếu đồ thị có đúng 2 đỉnh bậc lẻ thì chọn đỉnh xuất phát thế nào?

Nếu bài toán yêu cầu tìm Đường đi Euler (có 2 đỉnh bậc lẻ \(u\) và \(v\)), bạn bắt buộc phải đặt đỉnh bắt đầu là một trong hai đỉnh bậc lẻ này: start = u. Nếu bạn xuất phát từ một đỉnh bậc chẵn, thuật toán sẽ bị mắc kẹt sớm và không thể đi hết mọi cạnh của đồ thị. Hàm find_euler ở mục 3 tự làm việc này: nếu start không phải đỉnh bậc lẻ, hàm đổi sang đỉnh bậc lẻ đầu tiên.

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483