traversal-tickets
---
id: traversal-tickets
title: Finding Travel Itinerary Explanation
description: Write a Python function using recursion and DFS to find a travel itinerary using flight tickets
tags:
- Python
- DFS
- Recursion
- Travel Itinerary
sidebar_position: 16
isPublic: false
---
# Finding Travel Itinerary Explanation
We will write a function to find possible travel itineraries using flight tickets.
This process will be implemented using `recursion` and `Depth-First Search (DFS)`.
<br />
## Function Implementation
1. `Initialize the Graph`:
- Create a graph using the departure and destination of each ticket.
- This graph stores a list of all destinations reachable from each airport.
2. `Sort Tickets`:
- Sort tickets departing from each airport in reverse order. This allows the DFS to explore the lexicographically smallest route first.
3. `Implement the DFS Function`:
- Define a recursive function `dfs` that explores all possible routes starting from the current airport.
- After exploration, add the route to the `route` list.
4. `Calculate the Final Route`:
- Initiate the `dfs` function starting from the `JFK` airport.
- Since routes are stored in reverse order, reverse the list before returning the final result.
<br />
```python title="Optimal Solution"
def solution(tickets):
graph = {} # Initialize the graph
for start, end in tickets:
graph.setdefault(start, []).append(end) # Add departure and destination pairs
graph.setdefault(end, [])
# Sort tickets
for airport in graph:
graph[airport].sort(reverse=True)
route = [] # Store the route
# DFS function
def dfs(airport):
while graph[airport]:
dfs(graph[airport].pop()) # Move to the next destination
route.append(airport) # Add to route
dfs("JFK") # Start from 'JFK'
return route[::-1] # Return the final route
Example Usage
Example Input/Output
print(solution([["JFK", "SFO"], ["LAX", "MIA"], ["SFO", "LAX"]])) # Output: ["JFK", "SFO", "LAX", "MIA"]
In this example, the task is to find a possible travel itinerary using the given tickets. The tickets are ["JFK", "SFO"], ["LAX", "MIA"], ["SFO", "LAX"], representing the departure and destination. The goal is to find the lexicographically smallest route using all the tickets.
The function solution finds the following itinerary using these tickets: ["JFK", "SFO", "LAX", "MIA"]. This route uses all the tickets and is the smallest in lexicographical order.
The route is created by departing from "JFK" to "SFO", then continuing to "LAX" and finally arriving at "MIA". This satisfies the given conditions, so the function returns this route.
Want to learn more?
Join CodeFriends Plus membership or enroll in a course to start your journey.