Python实现最多n步从源起点查找图可达目的地的简易算法

原参考代码的问题拆解 #

• 未初始化循环变量i，执行时会直接触发未定义变量报错
• 循环内对步数上限n做自增操作，原本设定的最大步数限制完全失效，会陷入无意义的循环
• 直接覆盖修改source值，没有并行记录所有分支的可达节点，遇到多分支的连接关系时会漏算结果

零复杂算法的实现思路 #

完全贴合手动模拟走路的过程，不需要记复杂概念：

• 全程按步数分层推进，每一次循环对应移动1步
• 每轮从当前所在的所有节点出发，找出一步直达的所有邻居
• 用无重复的结构存储所有新到达的节点，避免路径绕圈导致的死循环
• 走到规定的最大步数、或者没有新的节点可以抵达时，直接结束流程

不需要额外记录完整路径，只需要留存每一步能到达的节点，逻辑简单好排查

可直接运行的参考实现 #

def reach_dest(source, n, connections):
    # 用集合存储结果，自动去除重复统计的节点
    reachable = set()
    # 记录当前轮次所在的节点集合，初始状态是起点（起点不算入结果）
    current_nodes = [source]

    # 最多走n步，每一次循环对应移动1步
    for _ in range(n):
        next_nodes = []
        # 遍历当前所在的所有节点，找一步可达的邻居
        for node in current_nodes:
            # 兼容邻接表中不存在的孤立节点，避免触发键错误
            for neighbor in connections.get(node, []):
                # 只统计从未到达过的节点
                if neighbor not in reachable:
                    reachable.add(neighbor)
                    next_nodes.append(neighbor)
        # 切换到下一轮的节点集合，准备移动下一步
        current_nodes = next_nodes
        # 如果当前没有可以继续移动的节点，直接提前退出，空跑无意义
        if not current_nodes:
            break

    # 返回列表形式的结果，方便后续操作
    return list(reachable)

题目场景的验证效果 #

• 调用reach_dest("A", 1, source_destination)，输出['B', 'D']，匹配1步移动的规则要求
• 调用reach_dest("B", 2, source_destination)，输出['C', 'D', 'A']，匹配2步移动的规则要求

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