我有以下算法：对于给定的（有限无向简单）图g=（v，e），边上有正权函数：
运行dfs（depth first search）直到找到一条向后的边或dfs停止。如果停止，返回G。
在由后向边缘构成的圆上，找到最重的边缘，并将其从G中移除。
返回到1。
现在我需要了解这个算法在做什么。我已经证明了算法给了我一个g的生成树，我相信它是一个最小生成树，但是我没有证明。请帮我证明一下。
最佳答案
证明当e是G循环中最重的边时，G-e的MST的代价不大于G的MST的代价（设T为G的MST，用T和e构造G-e的生成树T’的假设，代价（T’）
关于algorithm - 使用DFS查找MST的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8451389/