与深度优先搜索创建MST？ [英] Create a MST with depth-first search?

问题描述

我有一个对称的图形，并创建了一个树所有的最短路径随机顶点到其它任何顶点。我可以用树来构造一个最小生成树（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.

这篇关于与深度优先搜索创建MST？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！