首页 > 代码库 > 图的最小生成树:Kruskal算法实现
图的最小生成树:Kruskal算法实现
图的最小生成树,就是基于图,假设其有n的顶点,那么就要构建一颗连通树,使其各边权重和最小。最小生成树的实现算法主要有两种:Prim算法和Kruskal算法。Prim算法在前面已经介绍过,本文着重介绍Kruskal算法及其实现,其中图的实现以及相关操作,采用前面博文C++ 图的实现中的实现方式,由于本文重点在于Kruskal算法的实现,所有就不在图的构建以及相关操作中过多赘述。
对于Kruskal算法,维基的解释其实已经很详细了,算法思想很好理解,不多说明,直接看实现。
/* *无向图查找最小树:Kruskal算法 *不断找最小值,在不形成环的前提下,加入边 *----- By F8Master */ #include "Graphmtx.h" #include<iostream> #include<vector> using namespace std; struct EdgeByInt { int v1,v2; EdgeByInt(){}; EdgeByInt (int v11,int v22){ v1 = v11; v2 = v22; } }; template<class T ,class E> void Kruskal(Graphmtx<T,E> &G,vector<EdgeByInt> &v)//参数分别为图,存储最小树的边的vector { int numV = G.NumberOfVertices();//获得顶点数 int *setV = new int[numV]; for(int i = 0;i<numV;i++)//初始时候每个点自成一组 { setV[i]=i; } v.clear();//vector清空 int j = 1;//用于记录确定的边的数目 while(j<numV ) { E min = INF; int left = -1; int right = -1; for(int m = 0;m<numV;m++)//首先找到现存的最小值 { for (int n = m+1;n<numV;n++) { if (G.getWeight(m,n)<min) { min = G.getWeight(m,n); left = m; right = n; } } } G.removeEdge(left,right);//删除边 if(setV[left]!=setV[right])//如果不在同一个集合,也就不形成回路 { EdgeByInt temp(left,right); v.push_back(temp); int SetofLeft = setV[left]; int SetofRight = setV[right]; for(int k=0;k<numV;k++)//更新集合分组信息 { if(setV[k]==SetofRight) setV[k] = SetofLeft; } j++; } } }; template <class T ,class E> void printMinTree(Graphmtx<T,E> & G,vector<EdgeByInt> &v) { int size = v.size(); EdgeByInt temp; int left,right; for(int i = 0;i<size;i++) { temp = v[i]; left = v[i].v1; right = v[i].v2; cout<<"("<<G.getValue(left)<<" , "<<G.getValue(right)<<")"<<endl; } }; //测试程序 void test_Kruskal() { Graphmtx<char,int> G ; G.inputGraph(); vector<EdgeByInt> v(G.NumberOfEdges()-1); Kruskal(G,v); printMinTree(G,v); }
看两组实现的例子:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。