JFK#xff08;肯尼迪国际机场#xff09;出发的先生#xff0c;所以该行程必须从…力扣题目链接

[from,

to]子数组中的两个成员分别表示飞机出发和降落的机场地点对该行程进行重新规划排序。

所有这些机票都属于一个从

JFK

如果存在多种有效的行程请你按字符自然排序返回最小的行程组合。

例如行程

[JFK,

相比就更小排序更靠前所有的机场都用三个大写字母表示机场代码。

假定所有机票至少存在一种合理的行程。

所有的机票必须都用一次

解题思路

图的建模把航班信息建模为图其中城市为节点航班为边。

构建邻接表来表示图。

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

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

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

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

完整代码如下

根据航班每一站的重点字母顺序排序tickets.sort(keylambda

x:x[1])#

在之后的可选项机场中去掉这个机场self.adj[s].pop(0)

get

用于存储每个城市的邻接表。

邻接表是一个字典键是出发城市值是一个列表表示从该城市出发可以到达的目的城市。

x[1])对

列表按照每个航班的目的地x[1]进行排序。

这样做是为了在后续的处理过程中能优先选择字母顺序靠前的目的地。

for

self.adj:self.adj[u].append(v)else:self.adj[u]

已经在

self.adj[s][0]self.adj[s].pop(0)self.dfs(v)self.result.append(s)在

dfs

v因为航班列表已按字母排序过选择第一个保证了字母顺序并从列表中删除这个目的地。

然后递归调用

dfs

中的城市顺序是逆序的因为每次递归都会先处理后续的城市最后返回到当前城市。

return