建造 "connected matrix" 的成本

Question

我敢肯定，有大量关于如何准确执行我所追求的信息，但问题是不知道它的技术术语。基本上我想创建的是有向图的邻接矩阵，而不是简单地存储每个顶点对是否具有 direct 邻接，对于我想要的矩阵中的每个顶点对存储是否有连接两者的任何路径（以及这些路径是什么）。

这会给我恒定的查找时间复杂度，这是可取的，但是我不是很清楚构建这个矩阵的预期最佳时间复杂度是多少。

另外，这样的矩阵有正式的名称吗？

我脑子里想了想，这似乎是一个动态规划问题。如果我想知道 A 是否连接到 Z，我应该能够询问 A 的每个邻居 B、C 和 D 是否（以某种方式）连接到 Z，如果是，那么我知道 A 是。如果 B 没有存储这个答案，那么他会向他的直接邻居提出同样的问题，依此类推。我会一路记住结果，因此后续查找将保持不变。

我还没有花时间来实现这个，因为构建一个完整的矩阵感觉就像 ϴ(n^n)，所以我的问题是我是否正在以正确的方式进行此操作，并且如果确实有一种成本更低的方法来构建这样的矩阵？

Answer 1

图的传递闭包 (https://en.wikipedia.org/wiki/Transitive_closure#In_graph_theory) can indeed be computed by dynamic programming with a variation of Floyd Warshall algorithm: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm.

使用|V|不过，DFS（或 BFS）效率更高。

Answer 2

使用网络x connected components

G = nx.path_graph(4)
G.add_path([10, 11, 12])
d = {}
for group in idx, group in enumerate(nx.connected_components(G)):
    for node in group:
        d[node] = idx

def connected(node1, node2):
    return d[node1]==d[node2]

生成应该是 O(N) 查找应该是 O(1)

建造 "connected matrix" 的成本

Cost of building a "connected matrix"

algorithm

graph-theory

graph