LeetCode 332. 重新安排行程

题目描述：
给你一个机票列表 tickets，其中 tickets[i] = [from_i, to_i] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序，使得：

1. 所有这些机票都属于一个从 "JFK" 出发的行程
2. 所有机票必须使用且只能用一次
3. 如果存在多种有效的行程，请你按字典排序返回最小的行程组合

解题过程：

第一步：理解问题本质
这是一个欧拉路径问题，我们需要找到一条路径，从JFK出发，使用所有的边（机票）恰好一次。由于要求字典序最小的行程，我们需要在每一步都优先选择字典序较小的目的地。

第二步：数据结构设计
我们需要一个邻接表来存储每个机场可以到达的机场列表。为了确保每次都能选择字典序最小的目的地，我们应该对每个机场的目的地列表进行排序，或者使用优先队列。

更高效的做法是使用哈希表+最小堆：

• key: 出发机场
• value: 到达机场的优先队列（按字典序）

第三步：算法选择 - Hierholzer算法
这是一个经典的求解欧拉路径的算法，特别适合有向图。算法步骤：

1. 从起点JFK开始深度优先搜索
2. 对于当前机场，递归访问其所有未使用的出边
3. 当某个机场没有未使用的出边时，将其加入结果路径
4. 最后将结果路径反转

第四步：详细实现步骤

步骤1：构建邻接表

# 使用字典和最小堆（通过排序实现）
graph = {}
for from_airport, to_airport in tickets:
    if from_airport not in graph:
        graph[from_airport] = []
    graph[from_airport].append(to_airport)

# 对每个机场的目的地列表进行排序（相当于最小堆）
for from_airport in graph:
    graph[from_airport].sort()

步骤2：深度优先搜索（DFS）

def dfs(airport):
    # 访问当前机场的所有出边
    while graph.get(airport):
        # 选择最小的目的地（字典序最小）
        next_airport = graph[airport].pop(0)
        dfs(next_airport)
    # 当没有出边时，将机场加入结果
    result.append(airport)

步骤3：执行算法

result = []
dfs("JFK")
# 由于是后序遍历，需要反转结果
return result[::-1]

第五步：完整算法示例
假设输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

1. 构建邻接表：

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

2. DFS遍历过程：

   • 从JFK开始 → MUC
   • 从MUC开始 → LHR
   • 从LHR开始 → SFO
   • 从SFO开始 → SJC
   • SJC没有出边，加入结果：[SJC]
   • 回溯到SFO，加入结果：[SJC, SFO]
   • 回溯到LHR，加入结果：[SJC, SFO, LHR]
   • 回溯到MUC，加入结果：[SJC, SFO, LHR, MUC]
   • 回溯到JFK，加入结果：[SJC, SFO, LHR, MUC, JFK]

3. 反转结果：[JFK, MUC, LHR, SFO, SJC]

第六步：算法复杂度分析

• 时间复杂度：O(E log E)，其中E是边的数量，主要来自排序操作
• 空间复杂度：O(E)，用于存储邻接表和递归栈

第七步：关键点说明

1. 使用后序遍历的原因：确保在访问完所有出边后再将节点加入结果，这样可以处理环的情况
2. 字典序保证：通过对每个机场的目的地列表排序，确保每次都选择字典序最小的路径
3. 算法正确性：基于欧拉路径的性质，从起点开始深度优先搜索，当没有未访问的出边时，说明该节点应该是路径的终点

通过这种分层递进的讲解，你应该能够理解这个算法题的解题思路和实现细节。Hierholzer算法是解决这类欧拉路径问题的经典方法，结合DFS和贪心思想（选择字典序最小的路径）来找到最优解。