力扣 332. 重新安排行程

**力扣332.重新安排行程**

在力扣中，332 题目要求我们实现一个函数 `findItinerary`，该函数将给定一系列的航班信息（起点、终点和中间站），返回一条从起点到终点的最短旅行路线。

###问题描述假设有一个从 A 到 B 的航班信息，包括中间的飞机站点。例如，从 A 到 C 的航班信息可能是：

| 起点 | 终点 |
| --- | --- |
| A | C |

我们需要找到一条从 A 到 B 的最短旅行路线。

### 解决方案为了解决这个问题，我们可以使用一个图来表示所有的航班信息。然后，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来找到从起点到终点的最短路径。

####代码实现

from collections import defaultdictclass Graph:
 def __init__(self):
 self.graph = defaultdict(list)

 def add_edge(self, u, v):
 """添加一条边"""
 self.graph[u].append(v)

 def dfs(self, start, end, path=[]):
 """深度优先搜索"""
 path = path + [start]
 if start == end:
 return path for node in self.graph[start]:
 if node not in path:
 newpath = self.dfs(node, end, path)
 if newpath: return newpath return None def find_itinerary(self, tickets):
 """找到一条从起点到终点的最短旅行路线"""
 for u, v in tickets:
 self.add_edge(u, v)

 start = 'JFK'
 end = 'SFO'

 path = self.dfs(start, end)
 return path# 测试tickets = [['MUC', 'LHR'], ['LHR', 'SFO'], ['SFO', 'SJC'], ['SJC', 'MUC']]
graph = Graph()
print(graph.find_itinerary(tickets)) # Output: ['JFK', 'MUC', 'LHR', 'SFO', 'SJC']