We are given a collection of air tickets in the form of (source, destination).
These collection of air tickets are from a complete itinerary for a person who cannot seem to recall in what order he possible could have visited the places, but she knows that she started her trip from the beautiful city 'J'.
We have to find the complete itinerary from the collection for air tickets.
If multiple itineraries are possible, get the lexicographically smallest one.
Air Tickets: [ ("J", "A"), ("A", "D"), ("A", "B"), ("B", "C"), ("C", "A"), ("C", "E"), ("E", "C") ] Itinerary: ['J', 'A', 'B', 'C', 'E', 'C', 'A', 'D']
More technically speaking we have to find out a path that covers all the nodes and traverses every edge exactly once. Luckily this is a standard problem called as finding the "Euler Circuit".
It's guaranteed in the question that there is an Euler Circuit present as the trips are from an actual itinerary followed by someone.
We can observer the fact that if there were no cycles in the graph, we could've done a simple traversal to get the path followed.
1. Start with the city J.
2. Get the lexicographically smallest city that we can go from J.
3. From our next city also repeat the steps till we reach a dead end and keep adding these nodes in a stack.
4. By dead end we mean, we can't go anywhere from this city and is possibly the end destination.
5. This is what the main path will look like. If there are still unvisited nodes, they form cycles around these nodes only.
6. Pop the stack and put the node in the routes list, we are going to build the route in reverse order. This node is fully explored and has no outgoing edges.
7. Loop until the stack is empty, get the top of the stack and take the next smallest possible node and repeat the same procedure.