algorithm - 图算法 : reachability from adjacency map

我有一个依赖图，我表示为 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 到达。)

*循环:如果你很好奇，那是因为它代表 C/C++ 类型，并且结构可以包含指向所讨论结构的指针的成员。

最佳答案

在 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

关于algorithm - 图算法 : reachability from adjacency map，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7276010/