data-structures - 给定一个图找到一个不是最小的生成树

Question

如何在图中找到不是最小值的生成树（如果可能）

Answer 1

如果您的目标是找到任意生成树，无论它是否最小，您总是可以使用普通的 DFS 或 BFS 来搜索图，通过向新发现的节点添加边来构建生成树。这在时间上与图的大小呈线性关系，在实践中速度很快，并且易于编码。

如果您的目标是找到特别不是 MST 的生成树，您可以考虑只运行常规 MST 算法，但在比较边上的权重时，请始终反转比较结果。这最终找到了一个最大生成树，除非图中的每个生成树都恰好是最小值，否则它不会是最小生成树。这与运行常规 MST 算法所花费的时间相同，因此您可以选择要使用的算法。

Answer 2

Kruskal 算法找到最小生成树，将所有边按权重排序，从最轻到最重选择它们，只有当它们不形成循环时才将它们添加到解决方案中。当你达到的边数等于顶点数减一时，你就有了最小生成树。

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