> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/graph_search/reconstruct-itinerary.md).

# Reconstruct Itinerary

**Medium**

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.
```

## Analysis

By @Grandyang Source: <http://www.cnblogs.com/grandyang/p/5183210.html>

给一堆飞机票，从中建立一个行程单，如果有多种方法，取其中字母顺序小的那种方法。

本质是**有向图的遍历**问题，而且本题是关于有向图的边的遍历。

每张机票都是有向图的一条边，我们需要找出一条经过所有边的路径，那么DFS不是我们的不二选择。

**步骤**：

* 首先把图建立起来，通过邻接链表edge list来建立。但由于题目要求解法按字母顺序小的，这个list可以使用**PriorityQueue**来自动对存入的节点进行排序。所以edge list 的实现可以是 `HashMap<String, PriorityQueue<String>> flights;`
* 然后从节点 `"JFK"`开始DFS遍历，只要当前节点映射的PriorityQueue里有节点，我们取出这个节点，将其在PriorityQueue里删掉，然后继续**递归遍历**这个节点，由于题目中限定了一定会有解，那么等图中所有的PriorityQueue中都没有节点的时候，我们把当前节点存入结果中，然后再一层层回溯回去，将当前节点都存入结果，那么最后我们结果中存的顺序和我们需要的相反的。因此也可以在存入结果时，就存入头部（反向插入）: `path.addFirst(departure);`

此外还可以用stack来实现迭代的解法。

其实这里的DFS也是来头不简单：**欧拉回路Eulerian Path，Hierholzer算法**

> **Definition**: In graph theory, an Eulerian trail (or Eulerian path) is a trial in a finite graph which visits every edge exactly once.

在这里就是每张机票用一次并且全部用掉

**一个有向图中存在欧拉路径，iff:**

* 图是连通的，即图上任意二点总有路径连接
* 满足下面两个条件中的一个：
  * 有且只有一个点的入度比出度少1（作为欧拉路径的起点），有且只有一个点的入度比出度多1（作为终点），且其余点入度 = 出度。
  * 所有点入度 = 出度

**已知图中存在欧拉路径，找到一个欧拉路径：**

1. Fleury 算法
2. Hierholzer 算法

**Hierholzer 算法**

```
path = []

DFS(u):
    while (u has unvisited edge e(u,v))
        mark edge e(u, v) as visited
        DFS(v)
    end
    path.pushLeft(u)
```

回到这个问题，假设n是tickets的数量，那么**复杂度**：

Time：建图：O(n + nlogn), Hierholzer: O(n); Total : O(n + nlogn + n)

Space: O(n)

## Solution

### DFS + HashMap + Priority Queue : DFS递归有向图遍历 （7 ms, faster than 71.94%）

```java
public class Solution {

    Map<String, PriorityQueue<String>> flights;
    LinkedList<String> path;

    public List<String> findItinerary(String[][] tickets) {
        flights = new HashMap<>();
        path = new LinkedList<>();
        for (String[] ticket : tickets) {
            flights.putIfAbsent(ticket[0], new PriorityQueue<>());
            flights.get(ticket[0]).add(ticket[1]);
        }
        dfs("JFK");
        return path;
    }

    public void dfs(String departure) {
        PriorityQueue<String> arrivals = flights.get(departure);
        while (arrivals != null && !arrivals.isEmpty())
            dfs(arrivals.poll());
        path.addFirst(departure);
    }
}
```

Another implementation with DFS + HashMap + MinHeap (PriorityQueue)

```java
public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        LinkedList<String> list = new LinkedList<>();

        HashMap<String, PriorityQueue<String>> map = new HashMap<>();
        for(String[] ticket : tickets){
            if(!map.containsKey(ticket[0])) map.put(ticket[0], new PriorityQueue<String>());

            map.get(ticket[0]).add(ticket[1]);
        }

        dfs(list, "JFK", map);

        return new ArrayList<String>(list);
    }

    private void dfs(LinkedList<String> list, String airport, HashMap<String, PriorityQueue<String>> map){
        while(map.containsKey(airport) && !map.get(airport).isEmpty()){
            dfs(list, map.get(airport).poll(), map);
        }
        list.offerFirst(airport);
    }
}
```

后话：

这题用DFS的代码，跟Topological Sorting的DFS代码几乎一模一样；也从侧面说明了这道题其实也包含了拓扑排序的内核。

## Reference

<https://leetcode.com/problems/reconstruct-itinerary/discuss/78766/Share-my-solution>

<http://www.cnblogs.com/grandyang/p/5183210.html>

<https://www.youtube.com/watch?v=LKSdX31pXjY>


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/graph_search/reconstruct-itinerary.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.