假设我们找到了一个最小生成树。现在，我们只需要 MST 中从 A 到 Z 的路径。我们如何在 O(n^2) 时间内做到这一点？
我们从根 A 开始。然后我们查看 Ax 形式的树中的所有边（其中 x 是任何顶点）。
然后，假设我们找到：AB、AC、AD 等......然后对于每一个，我们寻找形式的边：Bx、Cx、Dx......这显然不是 O(n^2)。
那么在给定 MST 的情况下，找到路径 A -> Z 的更好/有效方法是什么？
谢谢
问问题
4058 次
4 回答
5
Depth-first search will be sufficient, it is in the worst case O(|V| + |E|). The fact that your input is a MST means that you don't have to worry about any loop detection, as you would have in a general graph.
于 2012-07-09T16:13:28.700 回答
0
查找最小生成树，你会发现它是一个将所有顶点连接在一起的最小子图。这意味着每条边最多只能使用一次。您可以只使用 DFS 或 BFS 来查找所需的路径，而无需检查循环，因为您已经拥有 MST。
于 2012-07-09T16:14:32.927 回答
0
如果你仔细想想，Prim 寻找 MST 的算法实际上只是 Dijkstra 的伪装。因此，如果您找到一条，MST 已经为您提供了最短路径（如上所述，想想 DFS）。
于 2012-07-09T18:12:51.160 回答
0
在 MST 创建期间，您可以填写 parent[]，因此之后使用简单的回溯，您将能够找到没有 DFS 的路径。
于 2012-07-09T18:03:16.863 回答