基于城市优先级约束的旅行路线排序问题求解

问题需求 #

给定城市列表与表示城市间优先级的元组列表（元组(A,B)表示A需排在B之前），生成符合所有优先级约束的旅行城市排序；若存在优先级循环（如A>B且B>A），则返回空列表。

示例1 #

城市列表：

cities = ['London', 'Berlin', 'Medellín', 'São Paulo', 'Prague', 'Ladakh', 'Nice']

优先级列表：

priorities = [('London', 'Medellín'), ('Medellín', 'São Paulo'), ('Prague', 'Berlin')]

预期输出：

['Nice', 'London', 'Medellín', 'Prague', 'São Paulo', 'Berlin', 'Ladakh']

示例2 #

城市列表：

cities = ['New York', 'Honolulu']

优先级列表：

priorities = [('New York', 'Honolulu'), ('Honolulu', 'New York')]

输出：[]（因优先级互相冲突）

用户已实现代码片段 #

用户已完成提取无优先级约束的城市、去重优先级涉及城市的部分代码：

def get_answer(cities, priorities):
    # 获取不在优先级约束中的城市
    cities_not_in_priorities = [
        city
        for city in cities
        if city not in [city for priority in priorities for city in priority]
    ]
    # 获取涉及优先级约束的城市
    cities_in_priorities = [
        city
        for priority in priorities
        for city in priority
        if city not in cities_not_in_priorities
    ]
    print(cities_in_priorities)
    # 去重优先级涉及的城市
    cities_in_priorities = list(dict.fromkeys(cities_in_priorities))

    print(cities_not_in_priorities)

# 生成带索引的优先级城市列表（用户额外编写的代码）
cities_in_priorities_with_index = [
    (cities_in_priorities.index(city), city)
    for city in cities_in_priorities
]

print(cities_in_priorities_with_index)

后续实现步骤与完整解决方案 #

要完成需求，核心是拓扑排序——处理有向无环图（DAG）的排序，若图中存在环则返回空列表。以下是完整实现：

步骤1：构建图与入度表 #

为涉及优先级的城市构建邻接表（表示城市间的依赖关系），同时统计每个城市的入度（即有多少城市需要排在它前面）。

步骤2：拓扑排序（Kahn算法） #

使用Kahn算法进行拓扑排序：

• 初始化队列，将所有入度为0的城市加入队列（这些城市没有前置依赖，可以优先安排）。
• 每次从队列取出一个城市，加入结果列表；遍历该城市的所有邻接城市，将它们的入度减1，若入度变为0则加入队列。
• 若最终结果列表的长度不等于优先级涉及城市的总数，说明存在环，返回空列表。

步骤3：合并无约束城市 #

无优先级约束的城市可以插入到结果的任意位置（只要不违反优先级约束即可），示例中是分散在排序结果的首尾，我们可以保持无约束城市在原列表中的相对顺序，灵活插入。

完整代码实现 #

from collections import deque

def get_answer(cities, priorities):
    # 提取所有涉及优先级的城市
    priority_cities = set()
    for a, b in priorities:
        priority_cities.add(a)
        priority_cities.add(b)
    # 筛选无优先级约束的城市
    cities_not_in_priorities = [city for city in cities if city not in priority_cities]
    
    # 构建邻接表和入度表
    adj = {city: [] for city in priority_cities}
    in_degree = {city: 0 for city in priority_cities}
    
    for a, b in priorities:
        adj[a].append(b)
        in_degree[b] += 1
    
    # Kahn算法执行拓扑排序
    queue = deque()
    # 入度为0的城市先加入队列
    for city in in_degree:
        if in_degree[city] == 0:
            queue.append(city)
    
    sorted_priority_cities = []
    while queue:
        current_city = queue.popleft()
        sorted_priority_cities.append(current_city)
        # 更新邻接城市的入度
        for neighbor in adj[current_city]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # 检查是否存在循环
    if len(sorted_priority_cities) != len(priority_cities):
        return []
    
    # 合并无约束城市与排序后的优先级城市（贴近示例输出的插入方式）
    final_result = []
    if cities_not_in_priorities:
        # 第一个无约束城市放在开头
        final_result.append(cities_not_in_priorities[0])
        # 加入排序后的优先级城市
        final_result.extend(sorted_priority_cities)
        # 剩余无约束城市放在末尾
        final_result.extend(cities_not_in_priorities[1:])
    else:
        final_result = sorted_priority_cities
    
    return final_result

# 测试示例1
cities1 = ['London', 'Berlin', 'Medellín', 'São Paulo', 'Prague', 'Ladakh', 'Nice']
priorities1 = [('London', 'Medellín'), ('Medellín', 'São Paulo'), ('Prague', 'Berlin')]
print(get_answer(cities1, priorities1))  # 输出符合约束的排序，如 ['Nice', 'London', 'Medellín', 'São Paulo', 'Prague', 'Berlin', 'Ladakh']

# 测试示例2
cities2 = ['New York', 'Honolulu']
priorities2 = [('New York', 'Honolulu'), ('Honolulu', 'New York')]
print(get_answer(cities2, priorities2))  # 输出 []

代码说明 #

1. 图结构构建：用邻接表adj记录每个城市的后续依赖，in_degree统计每个城市需要前置的数量，清晰反映优先级关系。
2. 拓扑排序逻辑：Kahn算法通过队列逐步处理无前置依赖的节点，确保生成的顺序完全符合优先级约束；若存在循环，排序后的节点数量会少于优先级城市总数，直接返回空列表。
3. 结果合并：无约束城市的插入方式灵活，这里采用首尾分散插入的方式贴近示例，实际可根据需求调整为全部前置、后置或穿插。

内容的提问来源于stack exchange，提问作者Atif Imam