当前位置： 面试刷题>> 重新安排行程 (经典算法题500道)
### 题目描述
**重新安排行程**
给定一系列航班信息，包括出发地和目的地，你需要重新安排这些航班的顺序，使得从某一城市出发的乘客能够到达目的地，且满足以下条件：
1. 每一架航班必须被安排一次且仅一次。
2. 航班的出发地必须是上一航班的目的地（或起始城市）。
3. 不存在环，即最终每个乘客都能到达目的地，而不是回到起点形成闭环。
**输入**：
- 航班信息以列表形式给出，每个元素是一个二元组 (start, end)，表示从 start 飞往 end 的航班。
- 一个起始城市作为起点。
**输出**：
- 如果可以重新安排行程，则返回一个行程列表，列表中的元素按照访问顺序排列。
- 如果无法重新安排行程（例如，存在无法到达的航班或闭环），则返回空列表。
**示例**：
输入：
```
flights = [("KCL", "LHR"), ("JFK", "KCL"), ("SFO", "SJC"), ("LHR", "SFO")]
start = "JFK"
```
输出：
```
["JFK", "KCL", "LHR", "SFO", "SJC"]
```
### PHP 示例代码
```php
function findItinerary($flights, $start) {
$graph = array_fill_keys(array_keys(array_column($flights, 0)), []);
foreach ($flights as $flight) {
$graph[$flight[0]][] = $flight[1];
}
$result = [];
backtrack($graph, $start, $result);
return empty($result) ? [] : array_reverse($result);
}
function backtrack(&$graph, $city, &$result) {
if (empty($graph[$city])) {
$result[] = $city;
return true;
}
while (!empty($graph[$city])) {
$nextCity = array_shift($graph[$city]);
if (backtrack($graph, $nextCity, $result)) {
return true;
}
}
// 回溯，尝试其他路径
array_push($graph[$city], $nextCity);
return false;
}
// 示例用法
$flights = [["KCL", "LHR"], ["JFK", "KCL"], ["SFO", "SJC"], ["LHR", "SFO"]];
$start = "JFK";
print_r(findItinerary($flights, $start));
```
**注意**：PHP 示例中，航班信息需要稍作修改以适应 PHP 数组结构。
### Python 示例代码
```python
def findItinerary(flights, start):
graph = collections.defaultdict(list)
for start, end in flights:
graph[start].append(end)
result = []
def backtrack(city):
while graph[city]:
next_city = graph[city].pop(0)
if backtrack(next_city):
result.append(next_city)
return True
# 回溯
graph[city].append(next_city)
result.append(city)
return True
backtrack(start)
return result[::-1]
# 示例用法
import collections
flights = [("KCL", "LHR"), ("JFK", "KCL"), ("SFO", "SJC"), ("LHR", "SFO")]
start = "JFK"
print(findItinerary(flights, start))
```
### JavaScript 示例代码
```javascript
function findItinerary(flights, start) {
const graph = {};
for (const [startCity, endCity] of flights) {
if (!graph[startCity]) graph[startCity] = [];
graph[startCity].push(endCity);
}
const result = [];
function backtrack(city) {
while (graph[city].length > 0) {
const nextCity = graph[city].shift();
if (backtrack(nextCity)) {
result.push(nextCity);
return true;
}
// 回溯
graph[city].push(nextCity);
}
result.push(city);
return true;
}
backtrack(start);
return result.reverse();
}
// 示例用法
const flights = [["KCL", "LHR"], ["JFK", "KCL"], ["SFO", "SJC"], ["LHR", "SFO"]];
const start = "JFK";
console.log(findItinerary(flights, start));
```
**码小课**网站中有更多关于算法和数据结构的内容分享，欢迎大家学习交流。