leetcode332.重新安排行程：优先队列与DFS实现欧拉路径的行程规划

一、题目深度解析与行程规划本质

题目描述

给定一个机票的字符串二维数组 tickets，每个元素是 [from, to] 的形式，表示从 from 到 to 的机票。要求找出从 JFK 出发的行程，且必须使用所有机票，若存在多种可能的行程，返回字典序最小的那个。

核心特性分析

1. 图论模型：每个机场是图的节点，机票是图的边，问题转化为在图中寻找一条经过所有边的路径
2. 欧拉路径：题目本质是寻找图中的欧拉路径（经过每条边恰好一次的路径）
3. 字典序要求：在可能的路径中选择字典序最小的

示例说明

• 输入：[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
• 输出：["JFK","MUC","LHR","SFO","SJC"]

二、代码核心实现与数据结构设计

完整代码实现

class Solution {Map<String, PriorityQueue<String>> targetMap = new HashMap<>(); // 存储起点到终点的映射，用优先队列保持字典序List<String> result = new LinkedList<>(); // 存储最终行程public List<String> findItinerary(List<List<String>> tickets) {// 构建邻接表，使用优先队列保证字典序for (List<String> ticket : tickets) {String start = ticket.get(0);String end = ticket.get(1);if (!targetMap.containsKey(start)) {targetMap.put(start, new PriorityQueue<>());}targetMap.get(start).offer(end);}dfs("JFK"); // 从JFK开始DFSCollections.reverse(result); // 反转结果得到正确顺序return result;}public void dfs(String current) {// 当当前机场还有未使用的机票时，继续递归while (targetMap.containsKey(current) && targetMap.get(current).size() > 0) {dfs(targetMap.get(current).poll());}// 当前机场没有未使用的机票时，加入结果result.add(current);}
}

核心数据结构解析：

1. targetMap：

   • 键：起点机场
   • 值：PriorityQueue存储终点机场，自动按字典序排序
   • 作用：构建邻接表，确保每次选择字典序最小的终点

2. result：

   • 存储最终行程的列表
   • 注意：结果需要反转，原因后文详细解释

3. DFS函数：

   • 递归处理每个机场的行程
   • 后序遍历方式确保机票被完全使用

三、核心问题解析：优先队列与DFS的协同作用

1. 为什么使用优先队列？

字典序保证：

PriorityQueue的自然排序特性确保：

• 当同一个起点有多个终点时，优先选择字典序最小的终点
• 例如：起点"JFK"对应终点[“SFO”, “ATL”]，优先队列会先选"ATL"

代码体现：

targetMap.get(start).offer(end); // 按字典序插入
targetMap.get(current).poll(); // 取出字典序最小的终点

2. DFS的后序遍历逻辑

遍历过程：

while (targetMap.containsKey(current) && targetMap.get(current).size() > 0) {dfs(targetMap.get(current).poll());
}
result.add(current);

• 先递归后添加：先处理所有子节点，再将当前节点加入结果
• 后序遍历原因：
  1. 确保所有子行程处理完毕后，再将当前机场加入行程
  2. 类似于"填坑"策略，确保每条边都被使用

示例说明：

• 行程路径：JFK→MUC→LHR→SFO→SJC
• DFS顺序：
  1. 递归到SJC（最末端节点）
  2. 返回时添加SJC到结果
  3. 递归到SFO，添加SFO
  4. 依此类推，最终结果需要反转

3. 为什么反转结果？

后序遍历的反转需求：

• DFS过程是后序遍历（先处理子节点，再处理父节点）
• 例如：遍历顺序为 SJC→SFO→LHR→MUC→JFK
• 反转后得到正确的行程顺序：JFK→MUC→LHR→SFO→SJC

代码体现：

Collections.reverse(result); // 反转后序遍历结果

四、DFS流程深度模拟：以示例输入为例

示例输入：

[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

构建的targetMap：

• JFK: [“MUC”]
• MUC: [“LHR”]
• LHR: [“SFO”]
• SFO: [“SJC”]

DFS执行过程：

1. 调用dfs(“JFK”)：

   • JFK存在且有终点MUC，poll出MUC，递归dfs(“MUC”)

2. 调用dfs(“MUC”)：

   • MUC存在且有终点LHR，poll出LHR，递归dfs(“LHR”)

3. 调用dfs(“LHR”)：

   • LHR存在且有终点SFO，poll出SFO，递归dfs(“SFO”)

4. 调用dfs(“SFO”)：

   • SFO存在且有终点SJC，poll出SJC，递归dfs(“SJC”)

5. 调用dfs(“SJC”)：

   • SJC不存在于targetMap或没有终点，添加"SJC"到result，返回

6. 回到dfs(“SFO”)：

   • 添加"SFO"到result，返回

7. 回到dfs(“LHR”)：

   • 添加"LHR"到result，返回

8. 回到dfs(“MUC”)：

   • 添加"MUC"到result，返回

9. 回到dfs(“JFK”)：

   • 添加"JFK"到result，返回

结果列表：

• 初始result: [“SJC”, “SFO”, “LHR”, “MUC”, “JFK”]
• 反转后: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]

五、算法复杂度分析

1. 时间复杂度

• O(E log E)：
  • E为机票数量（边数）
  • 构建优先队列：每个边入队出队操作O(log E)
  • DFS遍历：每个边处理一次O(E)

2. 空间复杂度

• O(E)：
  • 邻接表存储所有边O(E)
  • 结果列表存储所有节点O(E+1)

六、核心技术点总结：行程规划的关键要素

1. 图模型构建

• 邻接表表示：使用HashMap+PriorityQueue构建有向图
• 字典序保证：PriorityQueue确保每次选择字典序最小的边

2. 后序DFS遍历

• 遍历策略：先递归处理子节点，再将当前节点加入结果
• 反转需求：后序遍历结果需要反转得到正确行程顺序

3. 欧拉路径特性

• 问题本质：寻找图中的欧拉路径
• 算法保证：DFS后序遍历确保每条边被访问一次

七、常见误区与优化建议

1. 忽略PriorityQueue的作用

• 误区：使用普通List存储终点，无法保证字典序

  Map<String, List<String>> targetMap = new HashMap<>(); // 错误，无法保证顺序
  

• 正确做法：使用PriorityQueue保证字典序

2. 忘记反转结果

• 误区：直接返回后序遍历结果

  return result; // 错误，顺序相反
  

• 正确做法：反转后返回

3. 优化建议：处理重复机票

// 处理重复机票的情况（如存在多条相同航线）
// 代码已天然支持，PriorityQueue会按顺序处理

• 优势：PriorityQueue自动处理重复边的字典序选择
• 注意：题目保证存在有效行程，无需额外处理

八、总结：优先队列与后序DFS的完美结合

本算法通过优先队列和后序DFS的结合，高效解决了行程规划问题，核心在于：

1. 数据结构选择：PriorityQueue保证字典序，HashMap构建邻接表
2. 遍历策略：后序DFS确保所有边被使用，反转结果得到正确顺序
3. 问题建模：将行程问题转化为图的欧拉路径问题

理解这种解法的关键是把握后序遍历与反转操作的配合，以及优先队列在字典序保证中的作用。这种思路不仅适用于行程规划，还可迁移到其他图的欧拉路径问题，是图论算法在实际场景中的典型应用。