1. 项目概述与核心问题拆解最近在刷算法题时遇到了一个非常经典的图论问题——“重建行程”。题目乍一看像是简单的路径查找但深入分析后你会发现它本质上是一个寻找“哈密尔顿路径”的变种并且对访问顺序有字典序的额外要求。很多朋友在初次接触时容易把它和欧拉路径混淆或者被“按字典序访问”这个条件带偏导致代码写得很复杂或者直接超时。今天我就结合这道OJ题目用C带大家彻底搞懂如何高效地解决这类问题并深入聊聊哈密尔顿路径背后的算法思想。简单来说题目给你一堆机票信息每张机票代表从机场A到机场B的一条有向边。你需要从起点“JFK”出发用光所有的机票找出一条完整的行程路径。这里的关键约束有两点第一你必须使用每一张机票即遍历图中的每一条边这听起来像欧拉路径第二当存在多条可选路径时你必须选择目的地机场名字字典序最小的那条。最终你需要返回这个行程的机场访问序列。为什么说它是哈密尔顿路径问题呢哈密尔顿路径要求访问图中的每一个顶点恰好一次。而在这个机票问题里虽然我们访问的是边机票但每次到达一个机场就相当于访问了该顶点。由于机票可能重复同一个机场会被多次访问所以它不是一个标准的、顶点不重复的哈密尔顿路径。更准确地说这是一个在多重图允许重复边上寻找一条访问所有边的路径并且对顶点的访问顺序有隐含要求的问题。其求解的复杂度和思考方式与寻找哈密尔顿路径非常相似尤其是当采用回溯算法时面临的状态空间爆炸问题如出一辙。因此理解哈密尔顿路径的算法框架是解决此类问题的关键。2. 哈密尔顿路径与本题的关联深度解析2.1 什么是哈密尔顿路径哈密尔顿路径得名于数学家威廉·哈密尔顿它指的是在一个图中找到一条经过每个顶点恰好一次的路径。如果这条路径的起点和终点还能相连那就成了哈密尔顿回路。这和我们熟悉的“旅行商问题”在概念上很亲近但旅行商问题要求的是最短回路而哈密尔顿路径只要求存在性。这个问题是NP完全的这意味着对于顶点数n较大的图没有已知的多项式时间算法能解决所有情况。对于算法竞赛和OJ题目n通常会被限制在较小的范围比如n20这样我们才能使用回溯加状态压缩这类指数级但尚可接受的算法。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_mapstring, mapstring, 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: vectorstring findItinerary(vectorvectorstring tickets) { // 构建邻接表使用map保证邻接机场字典序 unordered_mapstring, mapstring, int graph; for (const auto ticket : tickets) { graph[ticket[0]][ticket[1]]; // 票数加1 } // ... 后续算法 } };路径记录我们使用一个vectorstring类型的path来记录行程。初始时将起点JFK加入。3.2 解法一回溯算法哈密尔顿路径思想这种解法模拟了寻找哈密尔顿路径的经典回溯过程从当前节点出发尝试所有可能的下一个未使用的“边”在这里是机票进行深度优先搜索如果最终能用完所有票则找到一条路径如果走到死胡同则回溯尝试其他选择。class Solution { private: unordered_mapstring, mapstring, int graph; vectorstring 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: vectorstring findItinerary(vectorvectorstring tickets) { ticketNum tickets.size(); path.clear(); // 构建图 for (const auto t : tickets) { graph[t[0]][t[1]]; } path.push_back(JFK); // 起点 backtracking(JFK); return path; } };算法解析与注意事项状态表示递归函数backtracking的参数curAirport表示当前所在的机场它代表了递归的当前状态。path和graph中票的剩余数量共同构成了完整的状态。剪枝这个解法本身包含了一个隐式剪枝——当ticketCount为0时这条边不再被考虑。但即便如此在最坏情况下它仍然需要探索所有可能的机票排列顺序时间复杂度是指数级的。对于本题的约束机票数量可能达到300这种朴素的回溯很可能会超时。找到第一个解即返回由于我们按照map的字典序遍历下一个机场并且一旦找到一条完整路径path.size() ticketNum 1就立即返回true那么我们找到的第一个完整路径就是字典序最小的路径。这是因为我们的搜索顺序本身就是字典序优先的。为什么可能超时想象一个极端情况所有机票都是从JFK到AAA从JFK到BBB从AAA到JFK从BBB到JFK……这会产生大量重复的、无效的搜索分支。这就是哈密尔顿类问题的典型状态爆炸。注意在实际OJ提交中这种回溯解法对于数据量大的测试用例很可能超时。它帮助我们理解问题本质但并非最优解。接下来看的高效解法才是通过本题的关键。3.3 解法二Hierholzer算法欧拉路径思想这是本题的正解也是效率最高的解法。Hierholzer算法用于在已知存在欧拉路径/回路的图中线性时间找出这条路径。算法流程如下从起点出发本题为JFK进行深度优先搜索。对于当前节点u选择它的一条未访问的边(u, v)删除这条边或标记为已访问然后递归地访问节点v。当节点u没有未访问的边时将u加入结果序列的头部或者最后逆序。最终得到的就是逆序的欧拉路径。对于字典序的要求我们只需要在每一步选择边时都优先选择到达机场字典序最小的那条边即可。由于我们使用了mapstring, int可以很方便地做到这一点。class Solution { private: // 使用mapstring, int记录从from机场到to机场的剩余票数 unordered_mapstring, mapstring, int graph; vectorstring 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: vectorstring findItinerary(vectorvectorstring 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; } };算法核心要点解析为什么是后序遍历这是Hierholzer算法的精髓。考虑一个简单的环A-B-C-A。从A出发如果按照前序加入路径我们可能得到ABC。但实际上当我们走到C时发现还有回A的边路径应该是ABCA。后序遍历确保了我们在处理完一个节点的所有出边之后才将该节点加入最终路径。这样像“C”这样的节点会在其所有后续路径C-A都安排好之后才被固定下来从而保证了路径的连续性。字典序如何保证关键在于for (auto [nextAirport, count] : graph[airport])这行循环。由于graph[airport]的类型是mapstring, intC的map在遍历时默认按键即string类型的机场名升序遍历。因此我们总是先尝试字典序更小的下一个机场。时间复杂度算法会遍历每一条边恰好一次因此时间复杂度是O(E)其中E是机票数量。但是由于我们使用map来存储邻接关系每次查找和选择下一个节点需要O(log V)的时间V是机场数量所以总复杂度可以认为是O(E log V)。构建图时对邻接表排序的复杂度是O(E log E)。这在E300的数据规模下非常高效。空间复杂度主要消耗在存储图graph、递归调用栈和结果路径result上是O(E V)。3.4 两种解法的对比与选择特性回溯解法 (哈密尔顿思想)Hierholzer算法 (欧拉路径思想)核心思想暴力搜索所有可能的机票使用顺序利用递归回溯。基于欧拉路径定理后序遍历删除边。时间复杂度指数级 O(E! ) 最坏情况无法接受。近似 O(E log V)非常高效。空间复杂度O(E V)递归深度可能达到E。O(E V)递归深度同样可能达到E。是否保证字典序是通过按map顺序遍历实现。是同样通过map的遍历顺序保证。适用场景帮助理解状态搜索、剪枝适用于小规模数据或教学。解决本题以及所有类似“一笔画”问题的标准算法。OJ通过情况大概率超时 (TLE)。可以顺利通过所有测试用例。显然对于这道题以及绝大多数类似问题Hierholzer算法是唯一正确的选择。回溯解法虽然直观但其指数级复杂度是致命的。这也给我们一个启示在面对图论路径问题时首先要分析问题的本质判断它属于欧拉路径、哈密尔顿路径还是其他类型这直接决定了我们能否找到高效算法。4. 完整C代码实现与逐行解读这里给出使用Hierholzer算法的完整、可运行的C代码并附上详细注释。#include iostream #include vector #include string #include unordered_map #include map #include algorithm using namespace std; class Solution { public: vectorstring findItinerary(vectorvectorstring tickets) { // 步骤1构建邻接表 graph[from][to] 剩余票数 // 使用 unordered_map 加快查找起始机场 // 内层使用 map使得每个起始机场对应的目的地列表自动按字典序排序 unordered_mapstring, mapstring, int graph; for (const auto ticket : tickets) { const string from ticket[0]; const string to ticket[1]; graph[from][to]; // 插入并增加票数计数 } vectorstring itinerary; // 用于存储最终行程逆序 // 步骤2定义DFS递归函数Hierholzer算法核心 // 使用函数内lambda表达式方便访问局部变量graph和itinerary functionvoid(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: 题目示例 vectorvectorstring tickets1 {{MUC,LHR},{JFK,MUC},{SFO,SJC},{LHR,SFO}}; vectorstring result1 sol.findItinerary(tickets1); cout Test 1: ; for (const auto ap : result1) cout ap ; cout endl; // 输出: JFK MUC LHR SFO SJC // 测试用例2: 存在多条可能路径需要字典序优先 vectorvectorstring tickets2 {{JFK,SFO},{JFK,ATL},{SFO,ATL},{ATL,JFK},{ATL,SFO}}; vectorstring 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; }关键代码行解读unordered_mapstring, mapstring, int graph;这是整个算法的数据结构基石。外层哈希表提供O(1)的平均访问速度找到起始机场的邻接信息。内层红黑树(map)在构建和遍历时自动维护目的地机场的字典序这是我们实现贪心选择选字典序最小的关键无需额外排序操作。graph[from][to];利用C map的特性如果键to不存在operator[]会插入一个默认构造的值对于int是0然后自增。这行代码简洁地完成了计数功能处理了多重边。functionvoid(const string) dfs [](const string airport) - void {...}使用std::function和lambda表达式定义递归函数。[]捕获列表表示以引用方式捕获所有外部变量graph和itinerary这样在递归函数内部可以直接修改它们。这比将graph和result作为类成员更清晰尤其是写竞赛代码时。for (auto it destinations.begin(); it ! destinations.end(); ) {...}遍历当前机场的所有目的地。这里显式使用迭代器it是为了避免在循环体内对destinations进行修改可能引起的潜在问题虽然本例中it-second--是安全的。更简单的写法for (auto [next, cnt] : destinations)在C17及以上也是完全可行的。it-second--; dfs(it-first);这是算法的核心动作。消耗一张票然后立即递归进入下一个机场。注意这里没有在递归返回后恢复票数(it-second)这与回溯算法有本质区别。Hierholzer算法沿着一条路走到底直到当前节点无路可走所有边都已访问然后回溯到上一个节点尝试其他未走的边。但这里的“回溯”是由函数调用栈自然完成的不需要显式恢复状态因为我们的目标是消耗掉所有边而不是探索所有排列。itinerary.push_back(airport);在递归调用之后将当前机场加入路径。这就是后序遍历。想象一下你只有处理完从当前机场出发的所有旅程之后才能确定当前机场在最终路径中的正确位置。reverse(itinerary.begin(), itinerary.end());由于是后序加入最先加入的是路径的终点最后加入的是起点。所以需要反转整个序列才能得到从起点到终点的正确行程。5. 常见问题、调试技巧与性能优化5.1 为什么我的回溯解法超时了这是遇到本题时最常见的问题。正如前面分析朴素的回溯算法时间复杂度是阶乘级的。即使只有10张票也可能有10! 3,628,800种排列需要探索。题目中机票数量可达300完全不可行。解决方案立即放弃回溯思路转而使用基于欧拉路径的Hierholzer算法。这是正确的算法范式转换。5.2 使用unordered_mapstring, vectorstring然后排序可以吗可以但不如map优雅。另一种常见做法是unordered_mapstring, vectorstring graph; for (auto t : tickets) { graph[t[0]].push_back(t[1]); } for (auto [from, toList] : graph) { sort(toList.begin(), toList.end()); // 对每个出发机场的目的地列表排序 }在DFS时你需要一个指针或额外的数据结构来标记每个目的地列表中下一个该用的索引。例如可以使用unordered_mapstring, int来记录每个机场当前使用到了其邻接列表的第几个位置。这种方法在空间上可能稍省但代码复杂度略高。使用mapstring, int记录票数在遍历时直接递减计数逻辑更清晰。5.3 递归深度过深会导致栈溢出吗有可能。递归深度等于路径中机场的数量最坏情况是E1每张票对应一个机场加上起点。对于E300递归深度301这在绝大多数OJ环境和现代编译器的默认栈空间下是安全的。如果担心栈溢出可以使用显式栈来模拟递归过程实现迭代版本的Hierholzer算法。迭代版本示例使用栈vectorstring findItinerary(vectorvectorstring tickets) { unordered_mapstring, mapstring, int graph; for (auto t : tickets) graph[t[0]][t[1]]; vectorstring result; stackstring 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 性能优化小贴士字符串哈希如果机场代码固定是三个大写字母可以考虑将其转换为整数ID如(c1-A)*26*26 (c2-A)*26 (c3-A)用vector代替unordered_map可以大幅提升访问速度。但代码可读性会下降在一般OJ中使用unordered_mapstring, ...已经足够快。避免不必要的拷贝在递归函数中传递机场字符串时使用const string引用。遍历map时使用for (auto [next, cnt] : graph[airport])的结构化绑定(C17)避免拷贝。提前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或回溯剪枝。这种分类思考的能力才是刷算法题带给我们的真正财富。