如何在有向无权图中查找不经过指定禁止节点集的路径

核心实现思路 #

• 有向无权图的路径查找优先选用广度优先搜索(BFS)，时间复杂度为O(V+E)，是这类场景的最优选择
• 禁止节点集合X的处理逻辑：在BFS遍历过程中，所有属于X的节点不允许被访问，只要在遍历前将这些节点标记为已访问状态（你代码中用set_color(color.black)的逻辑是可行的，只要原生BFS实现会跳过黑色节点，不会将其纳入遍历队列、也不会通过这类节点扩展后继节点）
• 注意遍历方向匹配需求：如果要查找源节点v到目标节点u的路径，BFS的起始节点要设置为v，终止判断条件为是否遍历到u

你现有代码的问题修正 #

你提供的代码存在两个明显错误：

1. 返回值逻辑错误：not G.bfs(u, v) and G.bfs(u, v)是恒假表达式，永远返回False，完全不符合需求
2. 参数顺序不匹配需求：如果你的原生G.bfs(a,b)接口的含义是判断是否存在a到b的路径，那么要匹配从v到u的需求，应该把v作为第一个入参，u作为第二个入参，和你现在的传参顺序相反

修正后代码示例 #

# 注意原函数名notPassTroughX存在拼写错误，Trough应为Through
def notPassThroughX(G: Graph, X: list, source: Node, target: Node) -> bool:
    # 提前将所有禁止节点标记为已访问，BFS时会自动跳过
    for x in X:
        x.set_color(color.black)
    # 调用BFS判断是否存在从source到target的可达路径
    return G.bfs(source, target)

调用时传入notPassThroughX(G, X, v, u)即可得到是否存在符合要求的路径。如果需要返回具体路径，只要修改BFS实现，在遍历的时候记录每个节点的前驱节点，最后从u回溯到v就能得到完整路径。

补充优化建议 #

如果你后续还要复用图G的节点状态，建议在函数执行完成后把X中节点的颜色重置为初始状态，避免影响其他图操作。
如果不想修改节点本身的属性，可以选择无侵入的实现方式，在BFS遍历节点时先判断是否属于禁止集合，示例如下：

def notPassThroughX(G: Graph, X: list, source: Node, target: Node) -> bool:
    forbidden = set(X)
    visited = set()
    queue = [source]
    visited.add(source)
    while queue:
        cur = queue.pop(0)
        if cur == target:
            return True
        for neighbor in G.get_neighbors(cur):
            if neighbor not in forbidden and neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return False

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