从哈密尔顿路径到欧拉路径：C++高效解决“重建行程”算法题

1. 项目概述与核心问题拆解

最近在刷算法题时，遇到了一个非常经典的图论问题——“重建行程”。题目乍一看像是简单的路径查找，但深入分析后，你会发现它本质上是一个寻找“哈密尔顿路径”的变种，并且对访问顺序有字典序的额外要求。很多朋友在初次接触时，容易把它和欧拉路径混淆，或者被“按字典序访问”这个条件带偏，导致代码写得很复杂或者直接超时。今天，我就结合这道OJ题目，用C++带大家彻底搞懂如何高效地解决这类问题，并深入聊聊哈密尔顿路径背后的算法思想。

简单来说，题目给你一堆机票信息，每张机票代表从机场A到机场B的一条有向边。你需要从起点“JFK”出发，用光所有的机票，找出一条完整的行程路径。这里的关键约束有两点：第一，你必须使用每一张机票（即遍历图中的每一条边），这听起来像欧拉路径；第二，当存在多条可选路径时，你必须选择目的地机场名字字典序最小的那条。最终，你需要返回这个行程的机场访问序列。

为什么说它是哈密尔顿路径问题呢？哈密尔顿路径要求访问图中的每一个顶点恰好一次。而在这个机票问题里，虽然我们访问的是边（机票），但每次到达一个机场，就相当于访问了该顶点。由于机票可能重复，同一个机场会被多次访问，所以它不是一个标准的、顶点不重复的哈密尔顿路径。更准确地说，这是一个在多重图（允许重复边）上，寻找一条访问所有边的路径，并且对顶点的访问顺序有隐含要求的问题。其求解的复杂度和思考方式，与寻找哈密尔顿路径非常相似，尤其是当采用回溯算法时，面临的状态空间爆炸问题如出一辙。因此，理解哈密尔顿路径的算法框架，是解决此类问题的关键。

2. 哈密尔顿路径与本题的关联深度解析

2.1 什么是哈密尔顿路径？

哈密尔顿路径得名于数学家威廉·哈密尔顿，它指的是在一个图中，找到一条经过每个顶点恰好一次的路径。如果这条路径的起点和终点还能相连，那就成了哈密尔顿回路。这和我们熟悉的“旅行商问题”在概念上很亲近，但旅行商问题要求的是最短回路，而哈密尔顿路径只要求存在性。

这个问题是NP完全的，这意味着对于顶点数n较大的图，没有已知的多项式时间算法能解决所有情况。对于算法竞赛和OJ题目，n通常会被限制在较小的范围（比如n<=20），这样我们才能使用回溯加状态压缩这类指数级但尚可接受的算法。

2.2 从“重建行程”看问题转化

现在我们回头看“重建行程”这道题。题目输入是[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]这样的票列表。我们可以把它构建成一个有向图：

• 顶点：机场（如JFK， MUC, LHR, SFO, SJC）。
• 边：机票，从出发机场指向到达机场。

我们的任务是找到一条路径，从JFK开始，用完所有的边。这首先让人联想到有向图的欧拉路径（一笔画问题），欧拉路径确实要求遍历所有边恰好一次。但欧拉路径有一个著名的判定定理：在有向图中，存在欧拉路径的充要条件是：要么所有顶点的入度等于出度；要么恰好有一个顶点的出度比入度大1（起点），恰好有一个顶点的入度比出度大1（终点），其余顶点入度等于出度。

在我们这道题里，题目保证存在至少一条合理的行程，这其实间接保证了这张机票图满足存在欧拉路径的条件（或至少存在一条使用所有边的路径）。那么，问题似乎简化成了寻找欧拉路径？确实，有一种非常巧妙的解法是利用Hierholzer算法在O(E)的时间复杂度内找出欧拉路径，并且通过优先队列维护邻接表来实现字典序选择。这是本题最高效的解法，时间复杂度约为O(E log E)，主要花在排序上。

但是，为什么我们还要提哈密尔顿路径呢？因为从另一个视角——回溯算法的视角来看，这道题呈现出了哈密尔顿路径问题的典型特征。我们可以把“选择下一张机票”看作“选择下一个要访问的机场（顶点）”。虽然同一机场可多次访问，但每用掉一张机票，就相当于做出了一次选择，状态空间的大小是关于边数E的指数级。当我们用标准的DFS回溯去尝试所有可能的机票使用顺序时，面临的挑战和解决哈密尔顿路径时一模一样：如何避免重复搜索、如何高效剪枝。题目要求的“字典序第一的行程”，正是要求我们在所有可能的路径中，找到字典序最小的那个解，这通常需要系统地探索整个状态空间，或者利用贪心策略。

因此，理解哈密尔顿路径的回溯解法，不仅能帮我们解决严格意义上的哈密尔顿路径问题，更能让我们掌握处理这类“状态空间遍历”问题的通用思路和优化技巧（如状态压缩、剪枝），这对于解决更复杂的变种题至关重要。接下来，我将先介绍基于回溯的“哈密尔顿式”解法，再对比介绍更优的“欧拉路径式”解法。

3. 核心算法设计与实现细节

3.1 数据结构的选择与构建

无论采用哪种思路，第一步都是构建图。由于机场名字是字符串，我们需要将其映射为整数索引以便操作。同时，因为存在多张相同起终点的机票（多重边），我们需要记录边的数量。

邻接表构建：我选择使用unordered_map<string, map<string, int>> graph这个数据结构。

• 外层unordered_map：键是出发机场，值是该机场的邻接信息。
• 内层map：键是到达机场，值是从“出发机场”到“到达机场”剩余的机票数量。使用map而不是unordered_map的原因在于，map会自动根据键（机场名）进行排序，这为我们后续实现“按字典序访问”提供了极大的便利。当我们需要选择下一个机场时，直接遍历这个map，遍历顺序自然就是字典序升序。

#include <iostream> #include <vector> #include <string> #include <unordered_map> #include <map> using namespace std; class Solution { public: vector<string> findItinerary(vector<vector<string>>& tickets) { // 构建邻接表，使用map保证邻接机场字典序 unordered_map<string, map<string, int>> graph; for (const auto& ticket : tickets) { graph[ticket[0]][ticket[1]]++; // 票数加1 } // ... 后续算法 } };

路径记录：我们使用一个vector<string>类型的path来记录行程。初始时，将起点"JFK"加入。

3.2 解法一：回溯算法（哈密尔顿路径思想）

这种解法模拟了寻找哈密尔顿路径的经典回溯过程：从当前节点出发，尝试所有可能的下一个未使用的“边”（在这里是机票），进行深度优先搜索，如果最终能用完所有票，则找到一条路径；如果走到死胡同，则回溯尝试其他选择。

class Solution { private: unordered_map<string, map<string, int>> graph; vector<string> path; int ticketNum; bool backtracking(const string& curAirport) { // 递归终止条件：如果路径长度等于机票数+1，说明所有机票已用完 if (path.size() == ticketNum + 1) { return true; // 找到一条完整路径 } // 遍历当前机场所有可能的目的地（map保证字典序） for (auto& [nextAirport, ticketCount] : graph[curAirport]) { if (ticketCount > 0) { // 还有票 // 做出选择：使用一张票 ticketCount--; path.push_back(nextAirport); // 进入下一层决策 if (backtracking(nextAirport)) { return true; // 找到一条可行路径，直接返回 } // 回溯：撤销选择 path.pop_back(); ticketCount++; } } return false; // 当前机场的所有选择都走不通 } public: vector<string> findItinerary(vector<vector<string>>& tickets) { ticketNum = tickets.size(); path.clear(); // 构建图 for (const auto& t : tickets) { graph[t[0]][t[1]]++; } path.push_back("JFK"); // 起点 backtracking("JFK"); return path; } };

算法解析与注意事项：

1. 状态表示：递归函数backtracking的参数curAirport表示当前所在的机场，它代表了递归的当前状态。path和graph中票的剩余数量共同构成了完整的状态。
2. 剪枝：这个解法本身包含了一个隐式剪枝——当ticketCount为0时，这条边不再被考虑。但即便如此，在最坏情况下，它仍然需要探索所有可能的机票排列顺序，时间复杂度是指数级的。对于本题的约束（机票数量可能达到300），这种朴素的回溯很可能会超时。
3. 找到第一个解即返回：由于我们按照map的字典序遍历下一个机场，并且一旦找到一条完整路径（path.size() == ticketNum + 1）就立即返回true，那么我们找到的第一个完整路径就是字典序最小的路径。这是因为我们的搜索顺序本身就是字典序优先的。
4. 为什么可能超时？想象一个极端情况：所有机票都是从JFK到AAA，从JFK到BBB，从AAA到JFK，从BBB到JFK……这会产生大量重复的、无效的搜索分支。这就是哈密尔顿类问题的典型状态爆炸。

注意：在实际OJ提交中，这种回溯解法对于数据量大的测试用例很可能超时。它帮助我们理解问题本质，但并非最优解。接下来看的高效解法才是通过本题的关键。

3.3 解法二：Hierholzer算法（欧拉路径思想）

这是本题的正解，也是效率最高的解法。Hierholzer算法用于在已知存在欧拉路径/回路的图中，线性时间找出这条路径。算法流程如下：

1. 从起点出发（本题为JFK），进行深度优先搜索。
2. 对于当前节点u，选择它的一条未访问的边(u, v)，删除这条边（或标记为已访问），然后递归地访问节点v。
3. 当节点u没有未访问的边时，将u加入结果序列的头部（或者最后逆序）。
4. 最终得到的就是逆序的欧拉路径。

对于字典序的要求，我们只需要在每一步选择边时，都优先选择到达机场字典序最小的那条边即可。由于我们使用了map<string, int>，可以很方便地做到这一点。

class Solution { private: // 使用map<string, int>记录从from机场到to机场的剩余票数 unordered_map<string, map<string, int>> graph; vector<string> result; void dfs(const string& airport) { // 遍历当前机场的所有目的地（map自动按key字典序排序） // 注意这里需要引用，因为我们要修改map中的值 for (auto& [nextAirport, count] : graph[airport]) { if (count > 0) { // 还有票 count--; // 消耗一张票 dfs(nextAirport); } } // 当当前机场的所有边都处理完后，将其加入结果 // 注意是后序加入，所以最终结果需要逆序 result.push_back(airport); } public: vector<string> findItinerary(vector<vector<string>>& tickets) { graph.clear(); result.clear(); // 构建邻接表 for (const auto& ticket : tickets) { graph[ticket[0]][ticket[1]]++; } dfs("JFK"); // 从JFK开始深度优先遍历 reverse(result.begin(), result.end()); // 将后序序列逆序得到正确行程 return result; } };

算法核心要点解析：

1. 为什么是后序遍历？这是Hierholzer算法的精髓。考虑一个简单的环：A->B->C->A。从A出发，如果按照前序加入路径，我们可能得到A，B，C。但实际上，当我们走到C时，发现还有回A的边，路径应该是A，B，C，A。后序遍历确保了我们在处理完一个节点的所有出边之后，才将该节点加入最终路径。这样，像“C”这样的节点，会在其所有后续路径（C->A）都安排好之后，才被固定下来，从而保证了路径的连续性。
2. 字典序如何保证？关键在于for (auto& [nextAirport, count] : graph[airport])这行循环。由于graph[airport]的类型是map<string, int>，C++的map在遍历时默认按键（即string类型的机场名）升序遍历。因此，我们总是先尝试字典序更小的下一个机场。
3. 时间复杂度：算法会遍历每一条边恰好一次，因此时间复杂度是O(E)，其中E是机票数量。但是，由于我们使用map来存储邻接关系，每次查找和选择下一个节点需要O(log V)的时间（V是机场数量），所以总复杂度可以认为是O(E log V)。构建图时对邻接表排序的复杂度是O(E log E)。这在E=300的数据规模下非常高效。
4. 空间复杂度：主要消耗在存储图graph、递归调用栈和结果路径result上，是O(E + V)。

3.4 两种解法的对比与选择

显然，对于这道题以及绝大多数类似问题，Hierholzer算法是唯一正确的选择。回溯解法虽然直观，但其指数级复杂度是致命的。这也给我们一个启示：在面对图论路径问题时，首先要分析问题的本质，判断它属于欧拉路径、哈密尔顿路径还是其他类型，这直接决定了我们能否找到高效算法。

4. 完整C++代码实现与逐行解读

这里给出使用Hierholzer算法的完整、可运行的C++代码，并附上详细注释。

#include <iostream> #include <vector> #include <string> #include <unordered_map> #include <map> #include <algorithm> using namespace std; class Solution { public: vector<string> findItinerary(vector<vector<string>>& tickets) { // 步骤1：构建邻接表 graph[from][to] = 剩余票数 // 使用 unordered_map 加快查找起始机场 // 内层使用 map，使得每个起始机场对应的目的地列表自动按字典序排序 unordered_map<string, map<string, int>> graph; for (const auto& ticket : tickets) { const string& from = ticket[0]; const string& to = ticket[1]; graph[from][to]++; // 插入并增加票数计数 } vector<string> itinerary; // 用于存储最终行程（逆序） // 步骤2：定义DFS递归函数（Hierholzer算法核心） // 使用函数内lambda表达式，方便访问局部变量graph和itinerary function<void(const string&)> dfs = [&](const string& airport) -> void { // 获取当前机场的所有可能目的地（已按字典序排列在map中） // 注意：这里必须使用引用，因为我们需要修改graph中的票数 auto& destinations = graph[airport]; // 遍历所有目的地 // 使用while循环而不是for-range，因为我们在循环内会修改destinations的迭代器状态？ // 实际上，因为使用的是map，删除元素不会使其他迭代器失效，for-range是安全的。 // 但更常见的写法是直接遍历，因为我们是减少计数，不是删除key。 for (auto it = destinations.begin(); it != destinations.end(); ) { // it->first 是目的地机场名， it->second 是剩余票数 if (it->second > 0) { // 还有票，选择这条边 it->second--; // 消耗一张票 string nextAirport = it->first; dfs(nextAirport); // 递归处理下一个机场 // 注意：递归返回后，不需要“撤销”操作，因为Hierholzer算法是单向消耗边 // 关键点：我们不需要回溯恢复票数！ } // 如果票数减到0，理论上可以删除这个键值对以节省空间，但非必须。 // 移动迭代器到下一个元素 ++it; } // 当前机场的所有出边都处理完毕后，将其加入路径 // 这里是后序遍历的位置，所以加入的节点顺序是“完成访问”的顺序 itinerary.push_back(airport); }; // 步骤3：从起点"JFK"开始执行深度优先搜索 dfs("JFK"); // 步骤4：反转路径得到正确顺序 // 因为dfs是后序加入节点，得到的itinerary是逆序的路径 reverse(itinerary.begin(), itinerary.end()); return itinerary; } }; // 简易的主函数用于测试 int main() { Solution sol; // 测试用例1: 题目示例 vector<vector<string>> tickets1 = {{"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"}}; vector<string> result1 = sol.findItinerary(tickets1); cout << "Test 1: "; for (const auto& ap : result1) cout << ap << " "; cout << endl; // 输出: JFK MUC LHR SFO SJC // 测试用例2: 存在多条可能路径，需要字典序优先 vector<vector<string>> tickets2 = {{"JFK","SFO"},{"JFK","ATL"},{"SFO","ATL"},{"ATL","JFK"},{"ATL","SFO"}}; vector<string> result2 = sol.findItinerary(tickets2); cout << "Test 2: "; for (const auto& ap : result2) cout << ap << " "; cout << endl; // 输出: JFK ATL JFK SFO ATL SFO // 解释：从JFK出发，字典序ATL < SFO，所以先去ATL。 return 0; }

关键代码行解读：

1. unordered_map<string, map<string, int>> graph;：这是整个算法的数据结构基石。外层哈希表提供O(1)的平均访问速度，找到起始机场的邻接信息。内层红黑树(map)在构建和遍历时自动维护目的地机场的字典序，这是我们实现贪心选择（选字典序最小）的关键，无需额外排序操作。
2. graph[from][to]++;：利用C++ map的特性，如果键to不存在，operator[]会插入一个默认构造的值（对于int是0），然后自增。这行代码简洁地完成了计数功能，处理了多重边。
3. function<void(const string&)> dfs = [&](const string& airport) -> void {...}：使用std::function和lambda表达式定义递归函数。[&]捕获列表表示以引用方式捕获所有外部变量（graph和itinerary），这样在递归函数内部可以直接修改它们。这比将graph和result作为类成员更清晰，尤其是写竞赛代码时。
4. for (auto it = destinations.begin(); it != destinations.end(); ) {...}：遍历当前机场的所有目的地。这里显式使用迭代器it，是为了避免在循环体内对destinations进行修改可能引起的潜在问题（虽然本例中it->second--是安全的）。更简单的写法for (auto& [next, cnt] : destinations)在C++17及以上也是完全可行的。
5. it->second--; dfs(it->first);：这是算法的核心动作。消耗一张票，然后立即递归进入下一个机场。注意，这里没有在递归返回后恢复票数(it->second++)，这与回溯算法有本质区别。Hierholzer算法沿着一条路走到底，直到当前节点无路可走（所有边都已访问），然后回溯到上一个节点，尝试其他未走的边。但这里的“回溯”是由函数调用栈自然完成的，不需要显式恢复状态，因为我们的目标是消耗掉所有边，而不是探索所有排列。
6. itinerary.push_back(airport);：在递归调用之后将当前机场加入路径。这就是后序遍历。想象一下，你只有处理完从当前机场出发的所有旅程之后，才能确定当前机场在最终路径中的正确位置。
7. reverse(itinerary.begin(), itinerary.end());：由于是后序加入，最先加入的是路径的终点，最后加入的是起点。所以需要反转整个序列，才能得到从起点到终点的正确行程。

5. 常见问题、调试技巧与性能优化

5.1 为什么我的回溯解法超时了？

这是遇到本题时最常见的问题。正如前面分析，朴素的回溯算法时间复杂度是阶乘级的。即使只有10张票，也可能有10! = 3,628,800种排列需要探索。题目中机票数量可达300，完全不可行。

解决方案：立即放弃回溯思路，转而使用基于欧拉路径的Hierholzer算法。这是正确的算法范式转换。

5.2 使用unordered_map<string, vector<string>>然后排序可以吗？

可以，但不如map优雅。另一种常见做法是：

unordered_map<string, vector<string>> graph; for (auto& t : tickets) { graph[t[0]].push_back(t[1]); } for (auto& [from, toList] : graph) { sort(toList.begin(), toList.end()); // 对每个出发机场的目的地列表排序 }

在DFS时，你需要一个指针或额外的数据结构来标记每个目的地列表中下一个该用的索引。例如，可以使用unordered_map<string, int>来记录每个机场当前使用到了其邻接列表的第几个位置。这种方法在空间上可能稍省，但代码复杂度略高。使用map<string, int>记录票数，在遍历时直接递减计数，逻辑更清晰。

5.3 递归深度过深会导致栈溢出吗？

有可能。递归深度等于路径中机场的数量，最坏情况是E+1（每张票对应一个机场，加上起点）。对于E=300，递归深度301，这在绝大多数OJ环境和现代编译器的默认栈空间下是安全的。如果担心栈溢出，可以使用显式栈来模拟递归过程，实现迭代版本的Hierholzer算法。

迭代版本示例（使用栈）：

vector<string> findItinerary(vector<vector<string>>& tickets) { unordered_map<string, map<string, int>> graph; for (auto& t : tickets) graph[t[0]][t[1]]++; vector<string> result; stack<string> stk; stk.push("JFK"); while (!stk.empty()) { string cur = stk.top(); auto& dests = graph[cur]; if (!dests.empty()) { // 选择字典序最小的目的地 auto it = dests.begin(); stk.push(it->first); it->second--; if (it->second == 0) { dests.erase(it); // 可选，删除已用完的边 } } else { // 当前节点没有出边，加入结果 result.push_back(cur); stk.pop(); } } reverse(result.begin(), result.end()); return result; }

迭代版本避免了递归调用开销和栈深度限制，是更工程化的写法。

5.4 如何处理起点不是“JFK”或者题目不保证有解？

本题明确规定了起点是“JFK”且保证至少有一条有效行程。如果是变种题：

• 起点不定：你需要先找到合适的起点。对于欧拉路径，起点是出度比入度大1的节点（如果存在），否则可以是任意节点（欧拉回路情况）。你需要先计算所有顶点的入度和出度来确定起点。
• 不保证有解：你的算法需要能判断无解的情况。在构建图后，可以先检查是否满足有向图欧拉路径的存在性定理。如果不满足，直接返回空数组。

5.5 性能优化小贴士

1. 字符串哈希：如果机场代码固定是三个大写字母，可以考虑将其转换为整数ID（如(c1-'A')*26*26 + (c2-'A')*26 + (c3-'A')），用vector代替unordered_map，可以大幅提升访问速度。但代码可读性会下降，在一般OJ中，使用unordered_map<string, ...>已经足够快。
2. 避免不必要的拷贝：在递归函数中，传递机场字符串时使用const string&引用。遍历map时，使用for (auto& [next, cnt] : graph[airport])的结构化绑定(C++17)，避免拷贝。
3. 提前Reserve：在知道机票数量后，可以为结果向量itinerary预留空间：itinerary.reserve(tickets.size() + 1);，减少动态扩容的开销。

5.6 一个容易忽略的坑：map的遍历与删除

在递归版本的DFS中，我们循环遍历graph[airport]这个map。当我们执行it->second--后，如果票数变为0，在本次循环迭代中，这个键值对依然存在。这没有问题，因为下次循环时it->second > 0条件为假，就不会再选择它。你也可以选择在票数为0时将其从map中删除(dests.erase(it++))，但必须小心处理迭代器失效问题。对于本题，不删除是完全可行的，不会影响正确性和效率。

最后，理解“重建行程”这道题，不仅仅是学会了一个算法，更重要的是建立了对欧拉路径和哈密尔顿路径两类问题的直觉。当你看到需要“遍历所有边”且对顺序有特定要求时，就该立刻想到Hierholzer算法；而当你需要“遍历所有点”时，就要警惕NP完全问题，考虑状态压缩DP或回溯剪枝。这种分类思考的能力，才是刷算法题带给我们的真正财富。