Cấu trúc dữ liệu và Giải thuật Bài 63: Đường đi và Chu trình Euler (Eulerian Path & Circuit) - Đi qua mọi cạnh đúng một lần.

Trong các bài toán duyệt đồ thị thông thường như BFS hay DFS (Bài 47), mục tiêu của chúng ta là ghé thăm mọi Đỉnh (Vertex). Tuy nhiên, trong nhiều bài toán thực tế về hạ tầng giao thông, quy hoạch mạng lưới cấp thoát nước hoặc quét đường cáp quang, yêu cầu đặt ra lại hoàn toàn khác: Làm sao để đi qua mọi Cạnh (Edge) của đồ thị đúng một lần duy nhất mà không bị lặp lại?

Bài toán kinh điển này khởi nguồn từ Thảm kịch Bảy cây cầu ở Königsberg năm 1736 và được giải quyết bởi nhà toán học vĩ đại Leonhard Euler, khai sinh ra hai khái niệm nền tảng: Đường đi Euler và Chu trình Euler.

1. Giải phẫu Chu trình và Đường đi Euler

Trước khi thiết kế thuật toán, chúng ta cần phân định rõ hai khái niệm cốt lõi:

• Chu trình Euler (Eulerian Circuit / Cycle): Là một đường đi khép kín đi qua mọi Cạnh của đồ thị đúng một lần và quay trở lại chính điểm xuất phát (Đỉnh bắt đầu trùng với đỉnh kết thúc).

• Đường đi Euler (Eulerian Path): Là một đường đi đi qua mọi Cạnh của đồ thị đúng một lần, nhưng điểm xuất phát và điểm kết thúc là hai đỉnh khác nhau.

Định luật nhận diện (Điều kiện tồn tại)

Làm sao để biết một đồ thị có chứa đường đi hoặc chu trình Euler trước khi cắm đầu viết code? Euler đã chứng minh các quy luật bất di bất dịch dựa trên Bậc của Đỉnh (Degree):

• Đối với Đồ thị Vô hướng (Undirected Graph):

  • Điều kiện có Chu trình Euler: Tất cả các đỉnh có bậc lớn hơn 0 phải liên thông với nhau, và mọi đỉnh đều phải có bậc chẵn (Even Degree).

  • Điều kiện có Đường đi Euler: Tất cả các đỉnh có bậc lớn hơn 0 liên thông, và đúng 0 hoặc 2 đỉnh có bậc lẻ. (Nếu có 0 đỉnh lẻ $\rightarrow$ tồn tại chu trình; nếu có đúng 2 đỉnh lẻ $\rightarrow$ đường đi bắt đầu từ một đỉnh lẻ và kết thúc ở đỉnh lẻ còn lại).

• Đối với Đồ thị Có hướng (Directed Graph):

  • Điều kiện có Chu trình Euler: Tất cả các đỉnh có cạnh liên thông, và mọi đỉnh đều có In-degree bằng Out-degree (Số mũi tên đi vào bằng số mũi tên đi ra).

  • Điều kiện có Đường đi Euler: Có tối đa 1 đỉnh có Out-degree - In-degree = 1 (điểm xuất phát), tối đa 1 đỉnh có In-degree - Out-degree = 1 (điểm kết thúc), và tất cả các đỉnh còn lại có In-degree == Out-degree.

2. Thuật toán Hierholzer: Chìa khóa vàng giải quyết bài toán

Thay vì mò mẫm bằng DFS thông thường (dễ bị kẹt ở các nhánh cụt), Carl Hierholzer đã phát minh ra một thuật toán tuyến tính tuyệt đẹp để tìm ra chu trình/đường đi Euler với độ phức tạp $O(V + E)$.

Tư duy cốt lõi của Hierholzer:

1. Bắt đầu từ đỉnh hợp lệ, tiến hành duyệt DFS. Nếu gặp một cạnh chưa đi qua, ta đi tiếp và đánh dấu xóa cạnh đó để không bao giờ đi lại lần thứ hai.

2. Khi đụng phải ngõ cụt (tức là đỉnh hiện tại không còn bất kỳ cạnh xuất phát nào chưa thăm), ta đưa đỉnh đó vào một Ngăn xếp kết quả (Result Stack / Path).

3. Quá trình quay lui (Backtracking) sẽ tự động lấp đầy ngăn xếp theo thứ tự ngược lại của chu trình. Khi thuật toán kết thúc, ta đảo ngược ngăn xếp lại sẽ thu được lộ trình Euler hoàn chỉnh.

3. Triển khai Thuật toán Hierholzer bằng Golang

Dưới đây là mã nguồn chuẩn mực giải quyết bài toán tìm Chu trình/Đường đi Euler trên Đồ thị có hướng (Directed Graph) sử dụng danh sách kề và cơ chế dọn dẹp cạnh đã thăm:

Go

package main

import "fmt"

// Cấu trúc Đồ thị có hướng
type EulerianGraph struct {
    numVertices int
    adj         [][]int
}

func NewEulerianGraph(v int) *EulerianGraph {
    return &EulerianGraph{
        numVertices: v,
        adj:         make([][]int, v),
    }
}

func (g *EulerianGraph) AddEdge(u, v int) {
    g.adj[u] = append(g.adj[u], v)
}

// Thuật toán Hierholzer tìm Đường đi/Chu trình Euler
func (g *EulerianGraph) FindEulerianPath() []int {
    // 1. Theo dõi số lượng cạnh đã xuất phát tại mỗi đỉnh (Pointer tracking để tối ưu DFS)
    edgeIndex := make([]int, g.numVertices)
    
    var path []int
    var currPath []int

    // Tìm đỉnh xuất phát chuẩn xác dựa trên bậc vào/ra
    // (Trong ví dụ này giả định đồ thị đã thỏa mãn điều kiện tồn tại đường đi Euler)
    startNode := 0
    outDegree := make([]int, g.numVertices)
    inDegree := make([]int, g.numVertices)

    for u := 0; u < g.numVertices; u++ {
        outDegree[u] = len(g.adj[u])
        for _, v := range g.adj[u] {
            inDegree[v]++
        }
    }

    // Kiểm tra đỉnh xuất phát nếu là Đường đi Euler (Out - In = 1)
    for i := 0; i < g.numVertices; i++ {
        if outDegree[i] - inDegree[i] == 1 {
            startNode = i
            break
        }
    }

    // 2. Tiến hành duyệt Hierholzer bằng Stack nội bộ
    currPath = append(currPath, startNode)

    for len(currPath) > 0 {
        u := currPath[len(currPath)-1]

        // Nếu đỉnh u vẫn còn cạnh chưa được duyệt
        if edgeIndex[u] < len(g.adj[u]) {
            v := g.adj[u][edgeIndex[u]]
            edgeIndex[u]++ // Đánh dấu cạnh đã đi qua bằng cách tịnh tiến con trỏ
            currPath = append(currPath, v) // Tiến sâu vào v
        } else {
            // Đụng ngõ cụt: Đưa đỉnh u vào mảng path kết quả và quay lui
            path = append(path, u)
            currPath = currPath[:len(currPath)-1]
        }
    }

    // 3. Đảo ngược path để thu được lộ trình chuẩn xác từ trái sang phải
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }

    return path
}

4. Phân tích Hiệu năng (Big-O)

• Thời gian (Time Complexity): $O(V + E)$. Nhờ mảng edgeIndex theo dõi tiến độ duyệt cạnh tại mỗi đỉnh thay vì xóa phần tử khỏi Slice, mỗi cạnh trong đồ thị chỉ được ghé thăm đúng một lần duy nhất.

• Không gian (Space Complexity): $O(V + E)$ để lưu trữ danh sách kề và các mảng ngăn xếp phụ trợ cho quá trình DFS.

5. Ứng dụng Thực tế trong Kỹ thuật Phần mềm

Đường đi và Chu trình Euler không chỉ là bài toán đố toán học mà có những ứng dụng cấp thiết trong các hệ thống công nghệ hiện đại:

• Sinh học phân tử & Giải mã Gen (DNA De Bruijn Graphs): Trong công nghệ sinh học, các đoạn chuỗi DNA ngắn (reads) được ghép nối lại với nhau bằng cách xây dựng đồ thị De Bruijn. Bài toán tìm chuỗi DNA hoàn chỉnh chính là bài toán tìm Đường đi Euler trên đồ thị này.

• Tối ưu hóa In ấn bảng mạch (PCB Routing) và Cắt vật liệu: Các máy cắt laser tự động hoặc máy phay CNC sử dụng thuật toán Euler để tính toán đường đi của đầu cắt sao cho phủ kín toàn bộ đường cắt mà không lãng phí thời gian di chuyển thừa thãi.

• Xử lý và Xóa tệp Log hệ thống tuần tự: Tối ưu hóa các tiến trình quét tuần tự các nút mạng lưới hoặc thư mục tập tin sao cho mọi liên kết đều được kiểm tra đúng một lần duy nhất mà không gây nghẽn băng thông hệ thống.

Khép lại chương đồ thị nâng cao, chúng ta đã đi qua từ luồng mạng cực đại, thành phần liên kết mạnh cho đến các chu trình Euler khép kín. Khi các hệ thống phần mềm phải đối mặt với không gian trạng thái bùng nổ, nơi mọi lựa chọn đều phụ thuộc vào các điều kiện ràng buộc toán học, chúng ta tiến vào lãnh địa của Tối ưu hóa tổ hợp.