本文共 1676 字，大约阅读时间需要 5 分钟。

问题描述：

       无向图 G = (V, E) 的反馈边集 E' 是边集 E 的一个子集，该子集与图中所有的环相交。因此，移除 E' 中的边将使得 G 无环。

       请对如下问题给出一个高效的算法。

       输入：具有正边权重 we 的无向图 G = (V, E)。

       输出：一个反馈边集 E‘  E，使其权重和最小。

❗算法描述❗：

       题目要求输出的反馈边集总权重最小，即该无向图的生成树的边总权重最大。

       将Kruskal算法进行改动：

       Kruskal算法先将全部边按照权值大小进行排序，然后按权值从小到大的顺序考虑每条边，来构成最小生成树。在这道题中，按权值从大到小的顺序考虑每条边构成最大生成树，之后用总边集减去最大生成树的边集，就是总权重最小的反馈边集。

❗涉及知识点❗：

       ① Kruskal算法；

       ② 并查集（推荐《啊哈算法》中的讲解，很详细很容易懂，书上也有源码，注释很全面！）

代码：

#include 
   
    #include 
    
     #include 
     
      using namespace std;//无向图的边的定义struct edge{	int weight;	int vex1;	int vex2;};int merge(int v1, int v2);int getf(int v);bool comp(edge &a, edge &b);#define vexnum 6#define num 10vector
      
        edges(num);vector
       
         vexs(vexnum);int main(){	cout << "请输入各边的信息(顶点、权值):" << endl;	for (int i = 0; i < num; ++i)	{		cin >> edges[i].vex1 >> edges[i].vex2 >> edges[i].weight;	}	//按边的权值进行排序	sort(edges.begin(), edges.end(), comp);	//并查集初始化	for (int i = 0; i < vexnum; ++i)	{		vexs[i] = i;	}	//从大到小枚举每一条边	//cout << "最大生成树中的边:" << endl;	cout << "最小权重的反馈边集:" << endl;	for (int i = num - 1; i >= 0; --i)	{		//如果加入该边后，图仍不连通，选用这条边		if (merge(edges[i].vex1, edges[i].vex2))		{			//cout << edges[i].vex1 << ' ' << edges[i].vex2 << ' ' << edges[i].weight << endl;		}		else		{			cout << edges[i].vex1 << ' ' << edges[i].vex2 << ' ' << edges[i].weight << endl;		}	}	return 0;}//并查集合并两集合的函数int merge(int v1, int v2){	int t1, t2;	t1 = getf(v1);	t2 = getf(v2);	if (t1 != t2)		//判断两点是否在一个集合中	{		vexs[t2] = t1;		return 1;	}	return 0;}//并查集查找祖先的函数int getf(int v){	if (vexs[v] == v)	{		return v;	}	else	{		//路径压缩		vexs[v] = getf(vexs[v]);		return vexs[v];	}}bool comp(edge &a, edge &b){	return a.weight < b.weight;}
       
      
     
    
   

代码检验?：

转载地址：http://kxtai.baihongyu.com/