重新安排行程为什么是回溯找欧拉路径？字典序如何保证最小？

简化版

重新安排行程要求从 JFK 出发，使用所有机票一次，并返回字典序最小的行程。

可以把机场看成点、机票看成有向边，这本质是在找使用所有边一次的路径。

回溯做法是按字典序尝试下一站，每用一张票就减少对应边计数，路径长度达到 tickets.length + 1 时成功。

详细版

由于可能有重复机票，邻接表不能只存 Set，最好存目的地计数。

先把每个起点的目的地按字典序排序。回溯从 JFK 开始：

如果路径长度等于机票数加 1，返回成功；
否则枚举当前机场的目的地；
如果某条边还有剩余，就使用它、递归下一站；
如果失败，恢复边计数和路径。

更优雅的做法是 Hierholzer 算法求欧拉路径，但回溯版本更容易解释搜索过程。

完整版教学

一、为什么这是图上的回溯

每张机票必须使用一次，机场可以重复经过。这说明选择对象不是“节点是否访问过”，而是“边是否使用过”。从当前机场出发，选择一张还没用过的出边，加入路径，再到达下一机场继续选择。失败时撤销这张票，尝试下一张。

记忆钩子：行程题用的是机票，不是机场；去重和状态都要按边处理。

二、为什么要处理字典序

题目要求在多个合法行程中返回字典序最小。回溯时如果每一步都按目的地字典序从小到大尝试，那么第一个成功使用所有机票的完整路径就是字典序最小路径。因为字典序比较从第一个不同位置决定，越早位置越小越优先。

当前机场	可选目的地	尝试顺序
JFK	ATL, SFO	ATL 先
ATL	JFK, SFO	JFK 先

排序邻接表是保证结果要求的关键。

三、重复机票为什么要用计数

可能存在两张完全相同的票，比如 ["JFK","ATL"] 出现 2 次。如果只用布尔 visited 或 Set，会把两张票合并成一张，导致路径长度不够。用计数可以准确表示某条边还剩几次可用。

JFK -> ATL: 2
使用一次后变 1
再使用一次后变 0

这比单纯记录目的地更严谨。

四、回溯代码骨架

实现思路如下：

function findItinerary(tickets) {
  const graph = new Map()
  for (const [from, to] of tickets) {
    if (!graph.has(from)) graph.set(from, new Map())
    const m = graph.get(from)
    m.set(to, (m.get(to) || 0) + 1)
  }
  for (const [from, m] of graph) {
    graph.set(from, new Map([...m.entries()].sort()))
  }

  const path = ['JFK']
  function dfs(cur) {
    if (path.length === tickets.length + 1) return true
    const nexts = graph.get(cur)
    if (!nexts) return false
    for (const [to, count] of nexts) {
      if (count === 0) continue
      nexts.set(to, count - 1)
      path.push(to)
      if (dfs(to)) return true
      path.pop()
      nexts.set(to, count)
    }
    return false
  }

  dfs('JFK')
  return path
}

这段代码直接体现“使用边、递归、撤销边”的回溯过程。

五、和欧拉路径算法的关系

从图论角度看，这题是在有向图中找一条使用所有边一次的路径，也就是欧拉路径。Hierholzer 算法可以更高效地构造答案：不断沿边走，走不通时把节点加入结果，最后逆序。若邻接表用小根堆或倒序数组，就能兼顾字典序。

回溯：容易理解，但可能回退多
Hierholzer：更图论，复杂度更优

面试中可以先讲回溯，再补充欧拉路径视角。

六、常见误区与追问

误区：把机场标记为 visited。 机场可以重复经过，应该标记机票边。
误区：用 Set 存目的地。 重复机票会被合并，答案错误。
误区：不排序邻接表。 可能找到合法行程，但不是字典序最小。
追问：为什么第一个成功路径字典序最小？ 因为每个分支按字典序尝试，字典序由最早不同位置决定。
追问：更优算法是什么？ 可以用 Hierholzer 算法求欧拉路径。

这些问题集中在“边状态”和“字典序”。

七、加强记忆

重新安排行程记成“票是边，JFK 起，按字典序试边”。每张票只能用一次，所以状态要记录边计数；机场可以重复，不要 visited 机场。回溯中使用一张票、路径加目的地，失败就恢复。第一个完整成功路径就是字典序最小，进阶可用欧拉路径算法优化。

简化版

详细版