本文主要是介绍【算法概论】贪心算法：反馈边集总权重最小，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
无向图 G = (V, E) 的反馈边集 E' 是边集 E 的一个子集，该子集与图中所有的环相交。因此，移除 E' 中的边将使得 G 无环。
请对如下问题给出一个高效的算法。
输入：具有正边权重 we 的无向图 G = (V, E)。
输出：一个反馈边集 E‘ E，使其权重和最小。
❗算法描述❗：
题目要求输出的反馈边集总权重最小，即该无向图的生成树的边总权重最大。
将Kruskal算法进行改动：
Kruskal算法先将全部边按照权值大小进行排序，然后按权值从小到大的顺序考虑每条边，来构成最小生成树。在这道题中，按权值从大到小的顺序考虑每条边构成最大生成树，之后用总边集减去最大生成树的边集，就是总权重最小的反馈边集。
❗涉及知识点❗：
① Kruskal算法；
② 并查集（推荐《啊哈算法》中的讲解，很详细很容易懂，书上也有源码，注释很全面！）
这篇关于【算法概论】贪心算法：反馈边集总权重最小的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
