如何基于字符对列表找出两个字符间的所有可行连接路径？

给定字符对列表：

["A-B", "C-D", "E-F", "B-C", "A-E", "A-F", "F-C"]

需要实现一个方法，找出任意两个字符之间的所有可行连接路径，比如查找"A-C"的连接时，期望输出：

["A-B-C", "A-E-F-C"]

实现思路 #

• 先构建无向图的邻接表：把每个字符作为节点，字符对中的双向连接关系存入邻接表，方便后续遍历。
• 用**深度优先搜索（DFS）**遍历：从起点出发，沿着邻接点递归探索每一条可能的路径，记录当前路径；当到达终点时，把路径存入结果列表。同时用已访问集合避免循环遍历。

Python 实现代码 #

def find_all_paths(pairs, start, end):
    # 构建邻接表
    graph = {}
    for pair in pairs:
        u, v = pair.split('-')
        graph.setdefault(u, []).append(v)
        graph.setdefault(v, []).append(u)
    
    # DFS 遍历找路径
    result = []
    def dfs(current, path, visited):
        if current == end:
            result.append('-'.join(path))
            return
        for neighbor in graph.get(current, []):
            if neighbor not in visited:
                dfs(neighbor, path + [neighbor], visited | {neighbor})
    
    dfs(start, [start], {start})
    return result

# 测试示例
pairs = ["A-B", "C-D", "E-F", "B-C", "A-E", "A-F", "F-C"]
print(find_all_paths(pairs, "A", "C"))

代码说明 #

• 邻接表构建：用setdefault简化代码，自动为不存在的节点创建空列表，同时添加双向连接，符合字符对的无向特性。
• DFS逻辑：递归过程中维护当前路径和已访问节点集合，确保每个节点只被访问一次，避免出现循环路径；到达终点时，将路径用-拼接成指定格式存入结果。
• 灵活性：这个方法可以适配任意字符对列表，只要传入对应的起点和终点，就能返回所有可行路径。

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