Backtracking Algorithm In Graphs Question: Reconstruct Itineary

Given tickets between cities need to display valid itineary in lexical order

We have to display list like this [“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”] This is lexical output. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”] Trick: when we use the lexical ordering in the priority queue we would be able to traverse the string in lexical order

Below hand sketch describes how backtracking works in graph Input and output explanied for the problem

Input : [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]] Output : [“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]