# 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

• 首先把图建立起来，通过邻接链表edge list来建立。但由于题目要求解法按字母顺序小的，这个list可以使用PriorityQueue来自动对存入的节点进行排序。所以edge list 的实现可以是 `HashMap<String, PriorityQueue<String>> flights;`

• 然后从节点 `"JFK"`开始DFS遍历，只要当前节点映射的PriorityQueue里有节点，我们取出这个节点，将其在PriorityQueue里删掉，然后继续递归遍历这个节点，由于题目中限定了一定会有解，那么等图中所有的PriorityQueue中都没有节点的时候，我们把当前节点存入结果中，然后再一层层回溯回去，将当前节点都存入结果，那么最后我们结果中存的顺序和我们需要的相反的。因此也可以在存入结果时，就存入头部（反向插入）: `path.addFirst(departure);`

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

• 图是连通的，即图上任意二点总有路径连接

• 满足下面两个条件中的一个：

• 有且只有一个点的入度比出度少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)``````

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%）

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

``````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);
}
}``````

## 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

Last updated