回溯——11.重新安排行程

力扣题目链接

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：

• 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
• 所有的机场都用三个大写字母表示（机场代码）。
• 假定所有机票至少存在一种合理的行程。
• 所有的机票必须都用一次 且 只能用一次。

解题思路

1. 图的建模：把航班信息建模为图，其中城市为节点，航班为边。构建邻接表来表示图。

2. 排序：对目的地进行字母排序，确保在深度优先搜索中总是优先访问字母顺序靠前的目的地。

3. DFS遍历：使用深度优先搜索遍历图，从起始城市出发，一直走到所有可能的目的地，记录经过的城市。

4. 路径重建：由于深度优先搜索会使得路径顺序反向，需要在结果列表中反转顺序以获得正确的行程。

这个方法有效地使用了排序和深度优先搜索来解决旅行路径问题，保证了按照字母顺序访问目的地并生成正确的行程路径。

完整代码如下：

class Solution:def findItinerary(self, tickets: List[List[str]]) -> List[str]:self.adj = {}# sort by the destination alphabetically# 根据航班每一站的重点字母顺序排序tickets.sort(key=lambda x:x[1])# get all possible connection for each destination# 罗列每一站的下一个可选项for u,v in tickets:if u in self.adj: self.adj[u].append(v)else: self.adj[u] = [v]# 从JFK出发self.result = []self.dfs("JFK")  # start with JFKreturn self.result[::-1]  # reverse to get the resultdef dfs(self, s):# if depart city has flight and the flight can go to another citywhile s in self.adj and len(self.adj[s]) > 0:# 找到s能到哪里，选能到的第一个机场v = self.adj[s][0]  # we go to the 1 choice of the city# 在之后的可选项机场中去掉这个机场self.adj[s].pop(0)  # get rid of this choice since we used it# 从当前的新出发点开始self.dfs(v)  # we start from the new airportself.result.append(s)  # after append, it will back track to last node, thus the result list is in reversed order

self.adj = {}

self.adj 用于存储每个城市的邻接表。邻接表是一个字典，键是出发城市，值是一个列表，表示从该城市出发可以到达的目的城市。

tickets.sort(key=lambda x: x[1])

对 tickets 列表按照每个航班的目的地（x[1]）进行排序。这样做是为了在后续的处理过程中能优先选择字母顺序靠前的目的地。

for u, v in tickets:if u in self.adj:self.adj[u].append(v)else:self.adj[u] = [v]

• 遍历排序后的航班列表，为每个出发城市 u 创建一个目的地列表。若 u 已经在 self.adj 字典中，则将 v 加入到对应的列表中；否则创建一个新的列表。

self.result = []
self.dfs("JFK")

初始化 self.result 列表，用于存储最终的行程路径。调用 dfs 方法从起始城市 "JFK" 开始进行深度优先搜索。

def dfs(self, s):while s in self.adj and len(self.adj[s]) > 0:v = self.adj[s][0]self.adj[s].pop(0)self.dfs(v)self.result.append(s)

在 dfs 方法中，首先检查当前城市 s 是否有可用的航班（即 s 是否在 self.adj 中且有目的地）。如果有，取出列表中的第一个目的地 v（因为航班列表已按字母排序过，选择第一个保证了字母顺序），并从列表中删除这个目的地。然后递归调用 dfs 方法继续从 v 出发。递归完成后，将当前城市 s 添加到 self.result 中。注意，self.result 中的城市顺序是逆序的，因为每次递归都会先处理后续的城市，最后返回到当前城市。

return self.result[::-1]

最后，返回 self.result 的反转列表，即按照正确的旅行顺序输出最终的行程路径。