Solution: Reconstruct Itinerary

Statement

Given a list of airline tickets where tickets[i] = [fromi, toi] represent a departure airport and an arrival airport of a single flight, reconstruct the itinerary in the correct order and return it.

The person who owns these tickets always starts their journey from "JFK". Therefore, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should prioritize the one with the smallest lexical ordeLexicographical order is a sorting arrangement similar to how words are arranged in a dictionary. It compares items character by character, based on their order in the alphabet or numerical value.r when considering a single string.

• For example, the itinerary ["JFK", "EDU"] has a smaller lexical order than ["JFK", "EDX"].

Note: You may assume all tickets form at least one valid itinerary. You must use all the tickets exactly once.

Constraints:

• $1 \leq$ tickets.length $\leq 300$

• tickets[i].length $= 2$

• fromi.length $= 3$

• toi.length $= 3$

• fromi $\neq$ toi

• fromi and toi consist of uppercase English letters.

Solution

The algorithm uses Hierholzer’s algorithmHierholzer's algorithm is a method for finding an Eulerian circuit (a cycle that visits every edge exactly once) in a graph. It starts from any vertex and follows edges until it returns to the starting vertex, forming a cycle. If there are any unvisited edges, it starts a new cycle from a vertex on the existing cycle that has unvisited edges and merges the cycles. The process continues until all edges are visited. to reconstruct travel itineraries from a list of airline tickets. This problem is like finding an Eulerian pathAn Eulerian path is a trail in a graph that visits every edge exactly once. An Eulerian path can exist only if exactly zero or two vertices have an odd degree. If there are exactly zero vertices with an odd degree, the path can form a circuit (Eulerian circuit), where the starting and ending points are the same. If there are exactly two vertices with an odd degree, the path starts at one of these vertices and ends at the other. but with a fixed starting point, “JFK”. Hierholzer’s algorithm is great for finding Eulerian paths and cycles, which is why we use it here.

The algorithm starts by arranging the destinations in reverse lexicographical order to ensure we always choose the smallest destination first. It then uses depth-first search (DFS) starting from “JFK” to navigate the flights. As it explores each flight path, it builds the itinerary by appending each visited airport when there are no more destinations to visit from that airport. Since the airports are added in reverse order during this process, the final step is to reverse the list to get the correct itinerary.

The basic algorithm to solve this problem will be:

1. Create a dictionary, flight_map, to store the flight information. Each key represents an airport; its corresponding value is a list of destinations from that airport.

2. Initialize an empty list, result, to store the reconstructed itinerary.

3. Sort the destinations lexicographically in reverse order to ensure that the smallest destination is chosen first.

4. Perform DFS traversal starting from the airport "JFK".

   1. Get the list of destinations for the current airport from flight_map.

   2. While there are destinations available:

      1. Pop the next_destination from destinations.

      2. Recursively explore all available flights starting from the popped next_destination, until all possible flights have been considered.

   3. Append the current airport to the result list.

5. Return the result list in reverse order to ensure the itinerary starts from the initial airport, "JFK", and proceeds through the subsequent airports in the correct order.

Let’s look at the following illustration to get a better understanding of the solution: