给定图找到一个生成树是不是最小

Question

如何找到一个生成树这是不是最小的图形（如果possiblr）

Answer 1

Kruskal algorithm发现最小生成树重量，命令所有的边缘，选择他们从最轻到最重，并且只有在不形成循环时才将其添加到解决方案中。当您达到等于顶点数减1的边数时，您将拥有最小生成树。

要获得不是最小值的生成树，只需应用相同的算法，而无需预先排序边的列表，或者在开始之前随机地乱序列表。

Answer 2

如果你的目标是找到任意的生成树，不管它是否是最小的，你总是可以使用简单的香草DFS或BFS来搜索图形，通过添加新的边缘来创建生成树节点。它的运行时间与图形大小呈线性关系，在实践中速度很快，并且编码起来很简单。

如果您的目标是找到一个特别不是MST的生成树，您可以考虑只运行一个常规MST算法，但在比较边缘权重时，始终会反转比较结果。这最终会找到最大的生成树，除非图中的每个生成树碰巧最小，否则将不是最小生成树。这需要与运行常规MST算法相同的时间，因此您可以选择要使用哪一个算法。