从给定的邻接矩阵生成可达性矩阵

Question

从给定的邻接矩阵生成可达性矩阵的最佳算法是什么？有warshall算法，但它不是最好的方法。还有一些其他方法，但过程更加理论化。是否有任何模块或可以使用它轻松创建可达性矩阵。我正在研究 python 2.7。

Answer 1

我认为在有向图的一般情况下没有办法比 O(n\xc2\xb3) 更快。

\n

话虽如此，您可以尝试使用巧妙的技术来减少常数。

\n

例如，您可以执行以下操作：

\n

\n

1. 通过查找所有强连接组件并将其替换为单个顶点，将图转换为DAG 。这可以在 \xce\x98(V + E) 或 \xce\x98(V\xc2\xb2) 中完成

   \n
\n

2. 在新图上，运行 DFS 来计算所有顶点的可达性，但是，在更新顶点的可达性集时，请以快速矢量化方式进行。从技术上讲，这是 \xce\x98( (V + E) * V ) 或 \xce\x98(V\xc2\xb3)，但常数会很低（见下文）。

   \n
\n

\n

所提出的矢量化方法是将每个顶点的可达性集表示为位向量，驻留在 GPU 上。这样，两个集合的并集计算就可以在 GPU 上以极快的并行方式执行。您可以使用任何 GPU 张量库，例如tf.bitwise。

\n

在计算出 GPU 上每个顶点的可达性位向量后，您可以在 \xce\x98(V\xc2\xb2) 时间内将它们提取到 CPU 内存中。

\n