歐拉路徑是圖論的起點——柯尼斯堡七橋問題的答案，讓歐拉在 1736 年建立了圖論這個領域。
問題定義
歐拉路徑：走過圖中每條邊「恰好一次」的路徑（起終點可以不同）
歐拉迴路：同上，但要回到起點
重要區別：這和漢密頓路徑（每個頂點走一次）是完全不同的問題——漢密頓是 NP-complete，歐拉可以在 O(V+E) 解決。
存在條件（充要）
無向圖
歐拉迴路：所有頂點度數為偶數 + 圖連通
歐拉路徑：恰好 0 或 2 個奇數度頂點 + 圖連通
0 個奇數度頂點 = 等同歐拉迴路（任意頂點出發）
2 個奇數度頂點 = 從一個奇數度頂點出發，到另一個結束
有向圖
歐拉迴路：所有頂點 入度 = 出度 + 圖弱連通
歐拉路徑：
最多 1 個頂點 出度 - 入度 = 1 （起點）
最多 1 個頂點 入度 - 出度 = 1 （終點）
其餘頂點 入度 = 出度
Hierholzer 演算法
O(V+E) 找歐拉迴路。核心思路不是「一直走」，而是「走完小迴路，再插入主迴路」：
void hierholzer(int start) {
Stack<Integer> stack = new Stack<>();
List<Integer> path = new ArrayList<>();
stack.push(start);
while (!stack.isEmpty()) {
int v = stack.peek();
if (adj[v].isEmpty()) {
path.add(v); // 沒有剩餘邊 → 這個節點進入路徑
stack.pop();
} else {
int u = adj[v].removeFirst(); // 走一條邊並刪除
stack.push(u);
}
}
Collections.reverse(path);
}為什麼「沒有剩餘邊才進入路徑」？因為這樣能確保節點是在「所有可能延伸的路徑都走完後」才被固定到路徑中，避免提早鎖死而繞不回來。
競程常見應用
一筆畫問題：判斷是否存在歐拉路徑，就是在問能不能一筆畫完。
字串接龍：把 n 個字串排成一條鏈（首尾字元相接）。對每個字串，把首字母到末字母連一條有向邊，判斷有向歐拉路徑是否存在並找出順序。
De Bruijn 序列：包含所有 k 長二進制字串的最短序列。等價於在 de Bruijn 圖上找歐拉迴路。
歐拉路徑的存在判斷只看度數，不看具體結構——這是圖論最優雅的結論之一。