logo标签列表

图算法：从邻接表中判断可达性

algorithmgraph-algorithm
3

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

给定一个节点列表badlist，我想解决可达性问题：即生成一个 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++类型，而结构体可以有成员是指向问题结构体的指针。
6个回答
5

在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
好的，那很简单。由于某种原因，我被卡住了，因为你必须在没有利用先前执行循环所获得的知识的情况下重新执行for root in badlist循环。所以也许有可能为速度进行优化…但是你现在所拥有的已经足够简单了。 - Jason S
@Jason对于有界入度（即被一个结构引用的不同结构类型的数量）的图来说，这是渐近最优的。如果瓶颈不在其他地方，我会感到惊讶的。 - quaint
@Jason：如果你想优化该算法的速度，就把标记位放在顶点本身，而不是在外部“visited”集合中查找。 - J D
2

这是我最终采用的方案，基于 @quaint 的答案：

（为了方便使用，需要使用几个 Guava 类）

static public <T> Set<T> findDependencies(
        T rootNode, 
        Multimap<T, T> dependencyGraph)
{
    Set<T> dependencies = Sets.newHashSet();
    LinkedList<T> todo = Lists.newLinkedList();
    for (T node = rootNode; node != null; node = todo.poll())
    {
        if (dependencies.contains(node))
            continue;
        dependencies.add(node);
        Collection<T> directDependencies = 
                dependencyGraph.get(node);
        if (directDependencies != null)
        todo.addAll(directDependencies);
    }
    return dependencies;
}
static public <T> Multimap<T,T> findDependencies(
        Iterable<T> rootNodes, 
        Multimap<T, T> dependencyGraph)
{
    Multimap<T, T> dependencies = HashMultimap.create();
    for (T rootNode : rootNodes)
        dependencies.putAll(rootNode, 
                findDependencies(rootNode, dependencyGraph));
    return dependencies;
}
static public void testDependencyFinder()
{
    Multimap<Integer, Integer> dependencyGraph = 
            HashMultimap.create();
    dependencyGraph.put(1, 2);
    dependencyGraph.put(2, 3);
    dependencyGraph.put(3, 1);
    dependencyGraph.put(3, 5);
    dependencyGraph.put(4, 2);
    dependencyGraph.put(4, 5);
    dependencyGraph.put(6, 1);
    dependencyGraph.put(7, 1);
    Multimap<Integer, Integer> dependencies = 
            findDependencies(ImmutableList.of(4, 5, 1), dependencyGraph);
    System.out.println(dependencies);
    // prints {1=[1, 2, 3, 5], 4=[1, 2, 3, 4, 5], 5=[5]}
}
2
你可以从邻接表构建一个可达性矩阵来进行快速搜索。我刚刚找到了一篇论文《CS336：图论课程笔记-Jayadev Misra》，该论文讲述了如何从邻接矩阵构建可达性矩阵。
如果A是你的邻接矩阵，可达性矩阵将为R = A + A² + ... + A^n，其中n为图中节点的数量。A², A³, ...可以通过以下方式计算：
  • A² = A |x| A
  • A³ = A |x| A²
  • ...
在矩阵乘法中使用逻辑或代替+，使用逻辑与代替x。时间复杂度为O(n^4)。
有趣的是，但我的“badlist”与图中节点总数相比非常少（badlist通常具有4-10个大小，而节点总数在数万个左右），因此我不确定这对于我的目的是否既有效又易于实现。 - Jason S
1
这是一个可用的Java解决方案：
// build the example graph
Map<Node, Collection<Node>> graph = new HashMap<Node, Collection<Node>>();
graph.put(n1, Arrays.asList(new Node[] {n2}));
graph.put(n2, Arrays.asList(new Node[] {n3}));
graph.put(n3, Arrays.asList(new Node[] {n1, n5}));
graph.put(n4, Arrays.asList(new Node[] {n2, n5}));
graph.put(n5, Arrays.asList(new Node[] {}));
graph.put(n6, Arrays.asList(new Node[] {n1}));
graph.put(n7, Arrays.asList(new Node[] {n1}));

// compute the badmap
Node[] badlist = {n4, n5, n1};
Map<Node, Collection<Node>> badmap = new HashMap<Node, Collection<Node>>();

for(Node bad : badlist) {
    Stack<Node> toExplore = new Stack<Node>();
    toExplore.push(bad);
    Collection<Node> reachable = new HashSet<Node>(toExplore);
    while(toExplore.size() > 0) {
        Node aNode = toExplore.pop();
        for(Node n : graph.get(aNode)) {
            if(! reachable.contains(n)) {
                reachable.add(n);
                toExplore.push(n);
            }
        }
    }

    badmap.put(bad, reachable);
}

System.out.println(badmap);
1

普通的深度优先搜索或广度优先搜索可以解决问题：针对每个坏节点执行一次。

0
就像Christian Ammer一样，您可以将邻接矩阵作为A，并在以下操作中使用布尔算术，其中I是单位矩阵。
    B = A + I;
    C = B * B;
    while (B != C) {
        B = C;
        C = B * B;
    }
    return B;

此外，标准矩阵乘法（包括算术和逻辑）的时间复杂度为O(n^3)，而不是O(n^2)。但是，如果n <= 64，你可以在现代的64位机器上并行处理64位，从而消除一个因子n。对于更大的图形，64位并行性也很有用，但着色器技术可能会更好。
编辑：使用SSE指令可以并行处理128位，使用AVX甚至可以处理更多。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接