Python3.5+中基于项目对连接规则的路径高效查找方法

针对你提出的问题，在Python 3.5及以上版本中，最高效的解决方案是基于邻接映射构建节点关系，再通过线性遍历生成完整路径，整体时间复杂度为O(n)（n为节点对的数量），这是理论上的最优复杂度了。

思路分析 #

根据题目条件，所有节点对最终会连成一条单一的链（无分支、无孤立）：

1. 每个中间节点都有且仅有两个连接节点（前一个和后一个）
2. 链的两个端点节点只有一个连接节点
3. 我们可以先构建双向的邻接映射，快速找到每个节点的连接对象
4. 定位链的任意一个端点作为起点，然后依次遍历下一个节点，直到覆盖所有节点

代码实现 #

from collections import defaultdict

def build_connected_path(pairs):
    # 1. 构建邻接映射：记录每个节点的连接节点
    adj = defaultdict(list)
    for a, b in pairs:
        adj[a].append(b)
        adj[b].append(a)
    
    # 2. 找到链的起点（只有一个连接的端点）
    start = None
    for node in adj:
        if len(adj[node]) == 1:
            start = node
            break
    
    # 3. 遍历生成完整路径
    path = []
    current_node = start
    prev_node = None
    
    while current_node is not None:
        path.append(current_node)
        # 排除前一个节点，找到下一个要走的节点
        next_candidates = [n for n in adj[current_node] if n != prev_node]
        prev_node = current_node
        current_node = next_candidates[0] if next_candidates else None
    
    return tuple(path)

# 测试示例输入（注意：原输入中的('dsd', 'sds')是孤立对，不符合题目"无孤立对"条件，故移除）
input_pairs = [('Bergerac','Pau'), ('Nice','Montpelier'), ('Pau','Paris'), ('Marseille','Nice'), ('Montpelier','Bergerac'), ('new','Marseille'), ('old','new'), ('Paris', 'last')]
output = build_connected_path(input_pairs)
print(output)
# 输出：('old', 'new', 'Marseille', 'Nice', 'Montpelier', 'Bergerac', 'Pau', 'Paris', 'last')

效率说明 #

• 构建邻接映射：遍历所有节点对，时间复杂度O(n)
• 定位起点：遍历所有节点（数量为n+1），时间复杂度O(n)
• 生成路径：每个节点仅被访问一次，时间复杂度O(n)
• 整体空间复杂度O(n)，主要用于存储邻接映射和路径结果

补充说明 #

• 使用collections.defaultdict可以简化邻接映射的构建，无需提前初始化每个节点的键
• 遍历过程中通过prev_node避免往回走，保证路径是单向的线性链
• 题目明确说明"无孤立对"，因此无需处理分支或断开的情况，代码可以稳定运行

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