图算法:邻接图的可达性 [英] graph algorithms: reachability from adjacency map

问题描述

我有一个依存关系图，我已经将其表示为Map<Node, Collection<Node>>(用Java讲，或者说f(Node n) -> Collection[Node]作为函数；这是从给定节点n到依赖于它的节点集合的映射) n).该图可能是循环的*.

I have a dependency graph that I have represented as a Map<Node, Collection<Node>> (in Java-speak, or f(Node n) -> Collection[Node] as a function; this is a mapping from a given node n to a collection of nodes that depend on n). The graph is potentially cyclic*.

给出节点列表badlist，我想解决 可达性问题 :即生成一个Map<Node, Set<Node>> badmap，该Map<Node, Set<Node>> badmap表示从列表badlist中的每个节点N到包含N或过渡依赖于此的其他节点的一组节点的映射.

Given a list badlist of nodes, I would like to solve a reachability problem: i.e. generate a Map<Node, Set<Node>> badmap that represents a mapping from each node N in the list badlist to a set of nodes which includes N or other node that transitively depends on it.

示例:

(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]}.

If badlist = [n4, n5, n1] then I expect to get 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.)

I'm floundering with finding graph algorithm references online, so if anyone could point me at an efficient algorithm description for reachability, I'd appreciate it. (An example of something that is not helpful to me is http://www.cs.fit.edu/~wds/classes/cse5081/reach/reach.html since that algorithm is to determine whether a specific node A is reachable from a specific node B.)

*循环的:如果您很好奇，那是因为它表示C/C ++类型，并且结构可以具有成员，这些成员是指向所讨论结构的指针.

*cyclic: if you're curious, it's because it represents C/C++ types, and structures can have members which are pointers to the structure in question.

推荐答案

在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

这篇关于图算法:邻接图的可达性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！