Step 1: Grasping the Problem
You are given a list of airline tickets in [from, to]
format and you will need to construct an itinerary in order starting from a fixed airport "JFK"
. The key points to mention in this question are:
 Lexical ordered itinerary should be constructed if there are multiple itinerary possible.
 It is guaranteed that an itinerary with using all tickets is possible.
 One must use all the tickets and start from
"JFK"
.
Because there are a lot of visiting and traversal going on, one can surely tell that this is a graph theory problem. So first and foremost thing to do is create a graph from the given tickets.
In the graph, the airports will be nodes and the tickets will be edges. According to the problem stated above, we can say “using all tickets exactly once” means “using all edges exactly once” in the graph. So in this graph problem, one needs to use all edges no matter if you visit the nodes or not. Hearing this, if you are familiar, you will say this is the application of Eulerian Path Construction Algorithm.
There are a lot of algorithms to construct the eulerian path from both directed and undirected graphs e.g. Fleury’s algorithm, Hierholzer’s algorithm etc. Our graph is directed and we will construct the path with a modified version of Hierholzer’s algorithm.
Step 2: Reverse sort the tickets
Because we need the first lexicographic ordered solution, we need to traverse the graph is lexicographic order. For this, we will construct the graph in a way so that the adjacency list’s descendants will be ordered. For this, we will sort the tickets
in descending order.


Step 2: Build the Graph
The first part of solving a graph theory problem has always been constructing the graph itself. In python it is nowadays usual to represent a graph with dictionary graph
where the keys are sources and values are list
of descendants of each edge. This is an adjacency list representation of the graph.
Many use defaultdict
to create the graph, but to keep things simple, we will use “default” dict
of python instead. Just loop through the edges (tickets
in this problem) and append a src
dst
to the graph
dict.


Step 3: Eulerian Path Construction
A graph may or may not have eulerian paths depending on where the edges it has. Hierholzer’s algorithm first checks if the graph has a feasible Eulerian path in it. To check that, it follows the following table.
There are four flavors of Euler path/circuit problem we care about:
X  Eulerian Circuit  Eulerian Path 

Undirected Graph  Every vertex has an even degree  Either every vertex has even degree or exactly two vertices have odd degree. 
Directed Graph  Every vertex has equal indegree and outdegree  At most one vertex has (outdegree)  (indegree) = 1 and at most one vertex has (indegree)  (outdegree) = 1 and all other vertices have equal in and outdegrees. 
This problem guarantees that there must be at least one eulerian path in it. So we do not need to check whether there is one or not.
After detecting the existence of Eulerian path, the algorithm does the two things:
 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.
 Since we assume the original graph is connected, repeating the previous step will exhaust all edges of the graph.
So we can use a list
named route
to keep track of “joining the tour formed in this way”. We can also create and call a recursive function to do “repeating the previous step” to “exhaust all edges” and get the final route
in backward.
A demonstration of the algorithm is given below. Note that, this graph does not have a valid itinerary to use all tickets, still the algorithm takes as much tickets as possible and build an itinerary.


Step 4: Reverse and Return route
Finally, we have route
with the eulerian path in backward direction. So we will reverse the path and return it as a result.


The time complexity of this problem is O(ELogE)
where E
is the number of edges (tickets
), and V
is the number of nodes (airports). The space complexity is order of O(E)
because we are just storing the graph with a dict
. The small but efficient full code is given below:





