题目描述

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

说明:
1. 如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
2. 所有的机场都用三个大写字母表示（机场代码）。
3. 假定所有机票至少存在一种合理的行程。

示例 1:
输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reconstruct-itinerary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1

首先，我们忽略按照字典顺序排列这一条件，那么这道题本质上求得的是有向图的欧拉路径。

严谨地说，一个连通有向图G有欧拉路径，指存在一个顶点，从它出发，沿着有向边的方向，可以不重复地遍历图中所有的边。

https://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98

题目中给定的机场名称是图的顶点，行程是图的边。题目要求重新安排行程，从示例可以看出每个行程都必须用到且只用一次。对应到欧拉路径的定义，每条边都要走到，且不重复。那么，这道题就转化成了给定起点，求一条字典顺序最小的欧拉路径。为了引出解法，我们先放几个例子。

图1展示了一张顶点度数都为偶数的图，首先我们忽略掉按字典顺序输出的条件。我们可以看出，如果顶点度数为偶数，那么我们先从JFK到MUC再回JFK到ATL最后返回JFK，又或是JFK先到ATL再回JFK再去MUC再回JFK，都是合法的路径。如果按照字典顺序输出，我们优先访问字典顺序小的节点ATL即可。因此，我们使用贪心策略，优先访问字典顺序小的顶点。

图2这个例子可以看出，我们别无选择必须先从JFK到NRT再回JFK，最后到达KUL作为终点。如果我们按照字典顺序先到KUL，就进入了“死路”。但是上一个例子我们提到了，优先访问字典顺序小的顶点，那么我们第一次肯定是先到KUL，这就走不通了，那怎么解决呢？当我们采用DFS方式遍历图时，需要将访问到的节点逆序插入到结果集。因此第一个访问到的节点将出现在结果集最后面，而我们是以顺序的方式来查看结果。如果第一个访问的节点是“孤岛节点”，他会出现在结果集的最后。当我们顺序读取结果集时，这种“孤岛节点”是最后遇到的，是图遍历的终点，这样就没有问题了。

我们在图3绘制了算法执行过程，黑色实线表示图的边；红色实实线表示递归调用；绿色虚线表示递归调用返回；数字代表执行顺序；文字表示执行的操作，结果集的数字表示在第几步操作加入的。我们从JFK出发，沿着边到达KUL（因为KUL字典顺序比NRT小），然后KUL没有临接点，将它放入结果集(2)，然后从KUL返回到达JFK，注意这个是通过调用栈返回而不是沿着边返回。然后从JFK出发沿着边到达NRT，因为NRT到JFK有返回边，沿着边再回到JFK。此时JFK的两个临接点都访问过了，我们将JFK加入结果集(6)。然后我们从JFK返回到NRT，这是从调用栈返回。然后NRT的临接点都访问过了，我们将NRT加入结果集(8)，然后退栈回到JFK。JFK的所有临接点都访问过了，将JFK加入结果集(10)，然后退栈，整个流程结束。

在实现方面，我们使用Map<String, List<String>>存储图，Key为顶点，List<String>为临接点。为了避免存在环路导致节点重复访问，我们每访问过一条边就把它标记为访问过，或者直接将访问过的边删除。为了实现按照字典顺序访问，我们把每个顶点的临接点按照字典顺序排序。这里，我们直接将访问过的边删除，然后每次都取临接点的第一个即可满足字典顺序访问。

因为每个顶点都要访问一次，每条边都要访问一次，时间复杂度应为O(|V|+|E|)，还要记得对临接点排序的时间复杂度O(|E|log|E|)，算法整体时间复杂度为O(|E|log|E|)；如果整个图是链式的，那么调用栈最深，空间复杂度应为O(|E|)。全部代码如下：

import java.util.*;

class Solution {

    public List<String> findItinerary(List<List<String>> tickets) {
        // 因为逆序插入，所以用链表
        List<String> ans = new LinkedList<>();

        if (tickets == null || tickets.size() == 0)
            return ans;

        Map<String, List<String>> graph = new HashMap<>();

        for (List<String> pair : tickets) {
            // 因为涉及删除操作，我们用链表
            List<String> nbr = graph.computeIfAbsent(pair.get(0), k -> new LinkedList<>());
            nbr.add(pair.get(1));
        }

        // 按目的顶点排序
        graph.values().forEach(x -> x.sort(String::compareTo));

        visit(graph, "JFK", ans);

        return ans;
    }

    // DFS方式遍历图，当走到不能走为止，再将节点加入到答案
    private void visit(Map<String, List<String>> graph, String src, List<String> ans) {
        List<String> nbr = graph.get(src);

        while (nbr != null && nbr.size() > 0) {
            String dest = nbr.remove(0);
            visit(graph, dest, ans);
        }

        ans.add(0, src); // 逆序插入
    }
}

解法1优化

其实我们可以不对临接点排序，而是使用小顶堆（Java可以用优先队列）。这样我们删除边的操作和访问最小字典顺序顶点可以用出队操作代替，时间复杂度应该会比排序再删除要低一些。

import java.util.*;

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        // 因为逆序插入，所以用链表
        List<String> ans = new LinkedList<>();

        if (tickets == null || tickets.size() == 0)
            return ans;

        Map<String, PriorityQueue<String>> graph = new HashMap<>();

        for (List<String> pair : tickets) {
            // 因为涉及删除操作，我们用链表
            PriorityQueue<String> nbr = graph.computeIfAbsent(pair.get(0), k -> new PriorityQueue<>());
            nbr.add(pair.get(1));
        }

        visit(graph, "JFK", ans);

        return ans;
    }

    // DFS方式遍历图，当走到不能走为止，再将节点加入到答案
    private void visit(Map<String, PriorityQueue<String>> graph, String src, List<String> ans) {
        PriorityQueue<String> nbr = graph.get(src);

        while (nbr != null && nbr.size() > 0) {
            String dest = nbr.poll();
            visit(graph, dest, ans);
        }

        ans.add(0, src); // 逆序插入
    }
}

进一步优化，将递归算法改为迭代算法：

import java.util.*;

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        // 因为逆序插入，所以用链表
        List<String> ans = new LinkedList<>();

        if (tickets == null || tickets.size() == 0)
            return ans;

        Map<String, PriorityQueue<String>> graph = new HashMap<>();

        for (List<String> pair : tickets) {
            // 因为涉及删除操作，我们用链表
            PriorityQueue<String> nbr = graph.computeIfAbsent(pair.get(0), k -> new PriorityQueue<>());
            nbr.add(pair.get(1));
        }

        // 按目的顶点排序

        visit(graph, "JFK", ans);

        return ans;
    }

    // DFS方式遍历图，当走到不能走为止，再将节点加入到答案
    private void visit(Map<String, PriorityQueue<String>> graph, String src, List<String> ans) {

        Stack<String> stack = new Stack<>();

        stack.push(src);

        while (!stack.isEmpty()) {
            PriorityQueue<String> nbr;

            while ((nbr = graph.get(stack.peek())) != null &&
                    nbr.size() > 0) {
                stack.push(nbr.poll());
            }
            ans.add(0, stack.pop());
        }
    }
}

参考：https://zxi.mytechroad.com/blog/graph/leetcode-332-reconstruct-itinerary/