与深度优先搜索创建MST？

本文介绍了与深度优先搜索创建MST？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有一个对称的图形，并创建了一个树所有的最短路径随机顶点到其它任何顶点。我可以用树来构造一个最小生成树（MST）？我的算法类似于深度优先算法。

I have a symmetrical graph and created a tree with all shortest path from a random vertex to any other vertex. Can I use the tree to construct a Minimum Spanning Tree(MST)? My algorithm is similar to depth-first algorithm.

推荐答案

在最坏的情况下，最短路径树没有找到一个最小生成树帮助。考虑在这里我们要查找的MST图。添加源顶点与一个相同长度大的边缘彼此顶点。来自该源的最短路径树包含非常长的边缘，这是我们知道先验的，因此最短路径树不是在这种情况下是有用的。

In the worst case, a shortest path tree does not help in finding a minimum spanning tree. Consider a graph where we want to find the MST. Add a source vertex with edges of an identical large length to each other vertex. The shortest path tree from that source consists of the very long edges, which we knew a priori, hence the shortest path tree is not useful in this case.