題目描述:給定一組機票(每張機票為 [from, to] 的出發地和目的地),從 "JFK" 出發,使用所有機票恰好一次,找出字母序最小的行程路線。保證輸入的機票必然能構成合法行程。
解題思路:此題等價於在有向圖中找 Eulerian Path(歐拉路徑)——恰好經過每條邊一次的路徑。由於要求字母序最小,我們將每個出發地的目的地清單排序(由小到大),使用 Hierholzer's Algorithm 求解。
Hierholzer's Algorithm 核心概念:
為何要 prepend(而非 append):DFS 遇到死路代表這個節點是路徑的「末端」。若某個中間節點先到達死路,說明它在這條路徑的後段出現。以遞迴展開後的後序(post-order)方式收集節點,再反轉,能正確還原歐拉路徑的順序。
字典序保證:對每個節點的鄰接清單按字母序排序(或使用 multiset),每次取最小目的地,確保在所有合法歐拉路徑中選到字典序最小的一條。
時間複雜度:O(E log E) — 其中 E 為機票數量。建立鄰接表並插入 multiset 共需 O(E log E)(每次 insert 為 O(log E))。Hierholzer's algorithm 每條邊恰好處理一次,每次從 multiset 取最小值並刪除需 O(log E),總計 O(E log E)。
空間複雜度:O(V + E) — 鄰接表儲存所有邊需 O(E),DFS stack 最壞情況深度為 O(E),結果陣列需 O(V + E)(V 為機場數量)。
1. Build adjacency map: for each ticket [from, to], insert to into sorted multiset adj[from]
2. Initialize stack with "JFK", result = []
3. While stack not empty:
a. curr = stack.top()
b. If adj[curr] is empty:
- Append curr to result
- Pop from stack
c. Else:
- next = smallest element in adj[curr]
- Remove next from adj[curr]
- Push next onto stack
4. Reverse result and return遞迴 DFS 版 Hierholzer O(E log E):與迭代版邏輯相同,但以遞迴方式實作。對每個節點,當鄰接清單非空時遞迴訪問最小目的地,在後序(遞迴返回後)將當前節點加入結果陣列前端。遞迴版程式碼更簡潔直觀,但深度大時(機票數量多)可能遭遇堆疊溢位(stack overflow),工業場景通常偏好迭代版。
排序鄰接清單 + vector O(E log E):以 vector 取代 multiset 儲存目的地,在建圖後對每個 vector 排序。取用時從尾端(最小值排在最前則從前端)移除,移除操作 O(1) 但需預先排序。此法減少每次 insert 的 O(log E) 開銷,整體時間複雜度相同但常數較小;然而若需動態插入邊則不適用。