检查 DAG 的两个节点是否在恒定时间内位于同一条路径上

Question

我有一个 DAG（有向无环图），它由边列表表示，例如

edges = [('a','b'),('a','c'),('b','d')]

将给出图表

a - > b -> d
|
v
c

我正在执行许多操作，我必须检查两个节点是否位于同一路径上（b并且d位于同一路径上，b而 和c不是来自上面的示例），这反过来又减慢了我的程序。我希望我能以某种方式遍历该图一次并保存所有路径，这样我就可以在恒定的时间内检查它。

这种加速可能吗？我将如何在 python 中实现它？

编辑：请注意，我需要检查两个方向，因此如果我有一对节点，(a,b)我需要检查atob和bto a。

Answer 1

您实际上想要找到图的传递闭包。

在计算机科学中，传递闭包的概念可以被认为是构建一个可以回答可达性问题的数据结构。也就是说，是否可以通过一跳或多跳从节点 a 到达节点 d？

有多种方法可以找到图的传递闭包。最简单的方法是使用floyd-warshall算法O(|V| ³ )。这里解释一下。

另一种方法是从每个节点执行 DFS，并将您访问的所有节点标记为从当前节点可达。这里解释一下。

还有一种方法仅适用于 DAG。首先对 DAG 执行拓扑排序。然后将拓扑排序表和OR当前节点的子节点的传递闭包一起逆向运算，得到当前节点的传递闭包。这里解释一下。

下面是基于 DFS 的方法的 Python 实现：

def create_adj_dict_from_edges(edges):
    adj_dict = {}

    for e in edges:
        for u in e:
            if u not in adj_dict:
                adj_dict[u] = []

    for e in edges:
        adj_dict[e[0]].append(e[1])
    return adj_dict

def transitive_closure_from_adj_dict(adj_dict):

    def dfs(node, visited):
        if node not in adj_dict:
            return
        for next in adj_dict[node]:
            if next in visited:
                continue
            visited.add(next)
            dfs(next,visited)

    reachable = {}
    for node in adj_dict:
        visited = set(node,)
        dfs(node,visited)
        reachable[node] = visited

    return reachable

def main():
    edges = [('a','b'),('a','c'),('b','d')]
    adj_dict = create_adj_dict_from_edges(edges)
    tc = transitive_closure_from_adj_dict(adj_dict)
    print tc
    # is there a path from (b to d) or (d to b)
    print 'd' in tc['b'] or 'b' in tc['d']
    # is there a path from (b to c) or (c to b)
    print 'c' in tc['b'] or 'b' in tc['c']


if __name__ == "__main__":
    main()

输出

{'a': set(['a', 'c', 'b', 'd']), 'c': set(['c']), 'b': set(['b', 'd']), 'd': set(['d'])}
True
False