题目描述

重新安排行程

给定一系列航班信息，包括出发地和目的地，你需要重新安排这些航班的顺序，使得从某一城市出发的乘客能够到达目的地，且满足以下条件：

1. 每一架航班必须被安排一次且仅一次。
2. 航班的出发地必须是上一航班的目的地（或起始城市）。
3. 不存在环，即最终每个乘客都能到达目的地，而不是回到起点形成闭环。

输入：

• 航班信息以列表形式给出，每个元素是一个二元组 (start, end)，表示从 start 飞往 end 的航班。
• 一个起始城市作为起点。

输出：

• 如果可以重新安排行程，则返回一个行程列表，列表中的元素按照访问顺序排列。
• 如果无法重新安排行程（例如，存在无法到达的航班或闭环），则返回空列表。

示例：

输入：

flights = [("KCL", "LHR"), ("JFK", "KCL"), ("SFO", "SJC"), ("LHR", "SFO")]
start = "JFK"

输出：

["JFK", "KCL", "LHR", "SFO", "SJC"]

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 示例代码

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 示例代码

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));

码小课网站中有更多关于算法和数据结构的内容分享，欢迎大家学习交流。