[Java] Eulerian path that covers all edges

Given a list of flight tickets and a start airport, find if possible an itinerary that uses all tickets. If there are more such itineraries, return the earliest lexicographically sorted one.

Example:

a,b - c,d start at a: there is no path

a,b - a,c - b,c - c,a start at a: return a,b,c,a,c since it's alphabetically earlier than a,c,a,b,c

This exercise is a bit simpler since we are given the start vertex and it's asking us to find a Eulerian path for the given directed graph.

The complexity for that would be O(E) where E is number of edges as we tray to visit each at most once and either we'll find a path or not.

However we are asked to return the earliest lexicographically sorted path, therefore when choosing a next vertex to visit, we can't pick any edge as we would normally do, but need to choose the earliest one.

This can be done by sorting the edges first, bringing the total time to O(E log E). Using an adjacency list, we could replace the list with a PriorityQueue instead to have this done for us while building the graph.

We can then have a map with key = vertex, value = priority queue to track our graph.

The idea then is to do a DFS and start from the source and:

• remove the next vertex from the queue of destinations of this vertex
• if the queue is now empty, remove the vertex from the map, otherwise, update map for this vertex to reflect having followed this edge
• call recursion of next vertex

When the queue of destinations for a vertex is empty, we can't progress further from that vertex, so we add it as HEAD of our result path

When we return from the initial call, we have one check to do: the adjacency list of all vertices must be empty (we were removing edges while doing DFS) as we want to have visited all edges.

If that is not the case, there was no path, we return an empty list.

You can check my implementation of eulerianPath on my Gist along with some tests in EulerianPathJTests. 

I have also added optional code that would perform the check whether a path exists and would help in finding a potential start and end vertices in case they were not given.