假设我们找到一个最小生成树。现在，我们只需要在MST中找到一条从a到Z的路径。我们如何在O（n^2）时间内做到这一点？
我们从根A开始，然后我们观察形式为Ax的树中的所有边（其中x是任何顶点）。
然后，假设我们找到：AB、AC、AD等。。。然后，对于每一个，我们寻找形式的边：Bx，Cx，Dx。。。这显然不是O（n^2）。
那么，在给定MST的情况下，找到路径a->Z的更好/有效的方法是什么呢？
感谢
深度优先搜索就足够了，在最坏的情况下是O（|V|+|E|）。事实上，您的输入是MST，这意味着您不必像在一般图中那样担心任何循环检测。
查找最小生成树，您会发现它是一个将所有顶点连接在一起的最小子图。这意味着每条边将在处最多使用一次。您可以使用DFS或BFS来查找所需的路径，而无需检查周期，因为您已经拥有MST。
在MST创建期间，您可以填充parent[]，因此之后使用简单的回溯可以在没有DFS的情况下找到路径。
如果你仔细想想，Prim的MST算法实际上只是Dijkstra的伪装。因此，如果你找到了MST，MST已经为你提供了最短的路径（如上所述，想想DFS）。