algorithm - 图算法 : reachability from adjacency map

Question

我有一个表示为 Map<Node, Collection<Node>> 的依赖关系图(在 Java 中，或 f(Node n) -> Collection[Node] 作为函数；这是从给定节点 n 到依赖于 n 的节点集合的映射)。该图可能是循环的*。

给定一个列表 badlist的节点，我想解决一个reachability problem :即生成一个 Map<Node, Set<Node>> badmap表示来自列表 badlist 中每个节点 N 的映射到一组节点，其中包括 N 或其他传递依赖于它的节点。

例子:

(x -> y means node y depends on node x)
n1 -> n2
n2 -> n3
n3 -> n1
n3 -> n5
n4 -> n2
n4 -> n5
n6 -> n1
n7 -> n1

这可以表示为邻接图 {n1: [n2], n2: [n3], n3: [n1, n5], n4: [n2, n5], n6: [n1], n7: [n1]} .

如果badlist = [n4, n5, n1]然后我希望得到 badmap = {n4: [n4, n2, n3, n1, n5], n5: [n5], n1: [n1, n2, n3, n5]} .

我正在网上寻找图算法引用资料，所以如果有人能指出我关于可达性的有效算法描述，我将不胜感激。 (对我没有帮助的例子是 http://www.cs.fit.edu/~wds/classes/cse5081/reach/reach.html，因为该算法是确定特定节点 A 是否可以从特定节点 B 到达。)

*cyclic:如果你很好奇，那是因为它表示 C/C++ 类型，并且结构可以包含指向相关结构的指针的成员。

Answer 1

在 Python 中:

def reachable(graph, badlist):
    badmap = {}
    for root in badlist:
        stack = [root]
        visited = set()
        while stack:
            v = stack.pop()
            if v in visited: continue
            stack.extend(graph[v])
            visited.add(v)
        badmap[root] = visited
    return badmap