332. Reconstruct Itinerary

Leetcode Graph Depth-first Search

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

分析

这道题目寻找访问所有有向图的边的路径，并且路径的词典序(lexical order)为最小。通过图（有向图或无向图）中的所有边且每一条边仅通过一次的路径称为欧拉路径。那么这道题目其实就是寻找欧拉路径。

其实不知道欧拉路径以及它的算法，这道题目也是可以解决的。由于是图的遍历问题，很容易想到dfs，或者回溯法。具体做法为：创建一个图，将图中的目的地按照字母顺序排序，依次访问每一个目的地，记录下访问的目的地，检查是否使用完所有飞机票；如果没有，则改变行程，尝试另一张飞机票。一直尝试，直到用完所有飞机票。

关键点在于：由于要求访问的词典序最小，所以首先访问词典序最小的目的地，如果不成功，再尝试词典序大一些的。

public List<String> findItinerary(String[][] tickets) {
    int n = tickets.length;
    LinkedList<String> visitOrder = new LinkedList<>();
    Map<String, LinkedList<String>> map = new HashMap<>();
    for (String[] ticket : tickets) {
        map.putIfAbsent(ticket[0], new LinkedList<>());
        map.get(ticket[0]).add(ticket[1]);
    }
    for (String v : map.keySet())
        Collections.sort(map.get(v));

    visitOrder.addFirst("JFK");
    findItinerary(visitOrder, map, "JFK", n);
    return visitOrder;
}


private boolean findItinerary(LinkedList<String> visitOrder, Map<String,    
                    LinkedList<String>> map, String v, int n) {
    // base case
    if (visitOrder.size() == n + 1) return true;

    LinkedList<String> destinations = map.get(v);
    // special case: v is invalid or v has no destinations
    if (destinations == null || destinations() == 0) return false;
    // iterate
    int size = destinations();
    for (int i = 0; i < size; i++) {
        String w = destinations.remove(i);
        visitOrder.addLast(w);
        if (findItinerary(visitOrder, map, w, n)) return true;
        visitOrder.removeLast();
        destinations.add(i, w);
    }
    return false;
}

对于欧拉路径，有专门的算法Hierholzer's algorithm来寻找欧拉路径。

Hierholzer's 1873 paper provides a different method for finding Euler cycles that is more efficient than Fleury's algorithm:

• Choose any starting vertex $v$, and follow a trail of edges from that vertex until returning to $v$. It is not possible to get stuck at any vertex other than $v$, because the even degree of all vertices ensures that, when the trail enters another vertex $w$ there must be an unused edge leaving $w$. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
• As long as there exists a vertex $u$ that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from $u$, following unused edges until returning to $u$, and join the tour formed in this way to the previous tour.

首先从起点JFK出发，dfs找到一个sub-path: JFK->A->C->D->A，在A处出现dead end(不再有可以走的边)，此时将A加到解当中，dfs返回。对于返回到的节点D，还有可以继续走的subpath，dfs继续找，得：D->B->C->JFK->D。此时的D为dead end，说明可以将D加到解当中，而且处于已经加过的点之前。以此类推，每次都加dead end的节点。直到所有点都是dead end！