LeetCode 第332题：重新安排行程

📖 文章摘要

本文详细解析LeetCode第332题“重新安排行程”，这是一道中等难度的图论和深度优先搜索问题。文章提供了基于欧拉路径的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升图论算法能力的程序员。

核心知识点： 图论、欧拉路径、深度优先搜索、字典序
难度等级： 中等
推荐人群： 具有基础数据结构知识，想要提升图论算法能力的程序员

题目描述

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就是字典序更小的行程。

假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

示例

示例 1：

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

示例1

示例 2：

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

示例2

提示

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi 和 toi 由大写英文字母组成
fromi != toi

解题思路

方法：欧拉路径 + DFS

本题实质上是在寻找一条欧拉路径，需要遍历所有边恰好一次。

关键点：

使用邻接表存储图
按字典序排序目的地
使用DFS寻找路径
处理死胡同情况

具体步骤：

构建邻接表表示图
对每个节点的邻接点按字典序排序
从JFK开始进行DFS
处理死胡同时需要回溯
最后反转路径得到结果

时间复杂度：O(E * log E)，其中E为边数空间复杂度：O(V + E)，其中V为顶点数，E为边数

图解思路

算法流程分析表

步骤	操作	状态	说明
初始化	构建图	邻接表创建	存储所有航线
排序	字典序排序	邻接点有序	确保最小字典序
DFS	深度搜索	路径构建	寻找欧拉路径
回溯	处理死胡同	路径调整	确保遍历所有边

示例图解

JFK -> MUC -> LHR -> SFO -> SJC

图的邻接表示例：
JFK: [MUC]
MUC: [LHR]
LHR: [SFO]
SFO: [SJC]
SJC: []

代码实现

C# 实现

public class Solution {
    private Dictionary<string, PriorityQueue<string, string>> graph;
    private List<string> path;
    
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        // 初始化
        graph = new Dictionary<string, PriorityQueue<string, string>>();
        path = new List<string>();
        
        // 构建图
        foreach (var ticket in tickets) {
            string from = ticket[0], to = ticket[1];
            if (!graph.ContainsKey(from)) {
                graph[from] = new PriorityQueue<string, string>();
            }
            graph[from].Enqueue(to, to); // 使用目的地作为优先级，确保字典序
        }
        
        // DFS
        DFS("JFK");
        path.Reverse(); // 反转得到正确顺序
        return path;
    }
    
    private void DFS(string airport) {
        while (graph.ContainsKey(airport) && graph[airport].Count > 0) {
            string nextAirport = graph[airport].Dequeue();
            DFS(nextAirport);
        }
        path.Add(airport);
    }
}

Python 实现

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        # 构建图（使用字典和堆）
        from collections import defaultdict
        import heapq
        
        graph = defaultdict(list)
        for src, dst in tickets:
            heapq.heappush(graph[src], dst)
            
        path = []
        def dfs(airport):
            while graph[airport]:
                dfs(heapq.heappop(graph[airport]))
            path.append(airport)
        
        dfs("JFK")
        return path[::-1]  # 反转得到正确顺序

C++ 实现

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        // 构建图
        unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph;
        for (const auto& ticket : tickets) {
            graph[ticket[0]].push(ticket[1]);
        }
        
        vector<string> path;
        
        function<void(string)> dfs = [&](string airport) {
            while (!graph[airport].empty()) {
                string next = graph[airport].top();
                graph[airport].pop();
                dfs(next);
            }
            path.push_back(airport);
        };
        
        dfs("JFK");
        reverse(path.begin(), path.end());
        return path;
    }
};

执行结果

C# 实现

执行用时：128 ms
内存消耗：45.2 MB

Python 实现

执行用时：40 ms
内存消耗：15.8 MB

C++ 实现

执行用时：12 ms
内存消耗：14.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	128 ms	45.2 MB	实现最清晰
Python	40 ms	15.8 MB	代码最简洁
C++	12 ms	14.2 MB	性能最优

代码亮点

🎯 使用优先队列确保字典序
💡 巧妙运用DFS和回溯
🔍 高效的图结构设计
🎨 清晰的代码组织结构

常见错误分析

🚫 忘记处理死胡同情况
🚫 未按字典序排序目的地
🚫 路径顺序错误
🚫 图构建不正确

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
DFS + 优先队列	O(E * log E)	O(V + E)	保证字典序最小	空间消耗较大
DFS + 排序	O(E * log E)	O(V + E)	实现简单	需要预处理

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第332题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

方法：欧拉路径 + DFS

图解思路

算法流程分析表

示例图解

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流