我确信有大量关于如何做我所追求的事情的信息，但这是一个不知道它的技术术语的问题。基本上我想要创建的是一个有向图的邻接矩阵，但是不是简单地存储每个顶点对是否具有直接邻接，对于矩阵中的每个顶点对，如果有任何连接两者的路径，我想存储（以及这些路径是什么）。
这将为我提供恒定的查找时间复杂度，这是可取的，但是我并不清楚构建此矩阵的预期最佳时间复杂度是多少。
另外，这样的矩阵有正式名称吗？
在我的脑海里，这似乎是一个动态规划问题。如果我想知道 A 是否与 Z 相连，我应该能够询问 A 的每个邻居 B、C 和 D 是否（以某种方式）与 Z 相连，如果是，那么我知道 A 是。如果 B 没有存储这个答案，那么他会问他的直接邻居同样的问题，依此类推。我会在此过程中记住结果，因此后续查找将保持不变。
我还没有花时间来实现这一点，因为感觉就像 ϴ(n^n) 来构建一个完整的矩阵，所以我的问题是我是否以正确的方式来解决这个问题，如果确实存在构建这样一个矩阵的低成本方法？
图 ( https://en.wikipedia.org/wiki/Transitive_closure#In_graph_theory )的传递闭包确实可以通过动态规划和 Floyd Warshall 算法的变体来计算：https : //en.wikipedia.org/wiki/ Floyd%E2%80%93Warshall_algorithm。
使用 |V| 不过，DFS（或 BFS）效率更高。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句