Reconstruct Itinerary

Background Knowledge

The "Reconstruct Itinerary" problem involves working with graphs, specifically a type of graph known as a directed graph or digraph, where each edge has a direction. In this context, airports are represented as vertices or nodes, and flights between them are represented as edges. The problem requires finding a path in this graph that visits each edge exactly once, which is a classic problem in graph theory known as an Eulerian path. An Eulerian path is a path that visits every edge in a graph exactly once.

To solve this problem, it's essential to understand the concept of graph traversal and how to represent graphs in a computer. A common way to represent graphs is using an adjacency list, where each vertex is associated with a list of its neighboring vertices. In the context of this problem, the adjacency list would store the destination airports for each source airport. Understanding how to iterate through this list and keep track of visited edges is crucial for finding the Eulerian path.

The problem also involves sorting and lexical order, as the solution requires returning the itinerary with the smallest lexical order if multiple valid itineraries exist. This means that the algorithm must be able to compare and sort the possible itineraries based on the alphabetical order of the airport codes.

Algorithm/Approach

The general approach to solve this type of problem involves using a graph traversal algorithm, such as depth-first search (DFS), to find the Eulerian path. The algorithm must be modified to keep track of the visited edges and ensure that each edge is visited exactly once. Additionally, the algorithm must be able to handle the case where multiple valid itineraries exist and return the one with the smallest lexical order.