最小生成树两个重要的算法：Prim 和 Kruskal。

Prim：时间复杂度O(n^2)，适用于边稠密的网络。

Kruskal：时间复杂度为O(e*log(e))，适用于边稀疏的网络。

【Prim主要算法思想和函数】

注：扩展了部分功能，根据需要可以选择得到算法结束时哪些边被选择。

 

 

1 #include 
     
       2 using namespace std; 3  4 const int N=101; 5  6 struct Edge 7 { 8     int from; 9     int to;10 };11 12 int matrix[N][N];
     

 

/*

最小生成树之Prim算法:

算法思想:选定一点到当前树集合,迭代合并距离当前树最近的点,同时更新剩余的点到当前树的"距离"

n:点的个数;

cost:边的权值,无边用0x3f3f3f3f表示无穷大;(建议初始化cost的时候:memset(cost,0x3f,sizeof(cost));)

edge_arr存放结果选定的边(此功能可选,默认参数为不选)

*/

1 template 
     
       2 T MST_Prim(const int & n,T cost[][N],Edge * edge_arr=NULL) 3 { 4     int i,j; 5     T ans=0; 6     T dis[N]; //用于记录当前每个点到当前的树的距离 7     int pre[N]; 8     bool vst[N]={
   false}; //用于标记点是否在当前树上 9     for(vst[0]=true,i=0;i
     

 

【Kruskal算法思想和函数】

/*

并查集的一个特性:

用一个数组p[]表示每一个元素的父级元素

最父级的元素的父级元素是一个负数,这个负数的绝对值是这个集合下的元素的个数

*/

 

1 template 
     
       2 bool operator <(const Edge
      
        & a,const Edge
       
         & b) 3 { 4     return a.cost
        
         =0) //找到x所在集合的代表元素15         px=p[px];16     /*17     路径压缩,可选,如果需要频繁查询,压缩之后可以提高速度18     即把从x到代表元素路径上的所有的元素的父节点都表示为代表元素19     */20     while(p[x]>=0)21     {22         tmp=p[x];23         p[x]=px;24         x=tmp;25     }26     return px; //x元素所在集合的代表元素27 }28 29 /*30 合并x和y所在的集合.31 */32 void UnionSet(int * p,int x,int y)33 {34     int tmp;35     x=FindSet(p,x);36     y=FindSet(p,y);37     if(x==y)38         return ;39     tmp=p[x]+p[y];40     if(p[x]>p[y]) //将小树合并到大树下41     {42         p[y]=tmp;43         p[x]=y;44     }45     else46     {47         p[x]=tmp;48         p[y]=x;49     }50     return ;51 }
        
       
      
     

 

/*

最小生成树算法之Kruskal算法:

算法思想:每次找最小的边,如果在已有的森林中加入该边后会形成回路,则舍弃,否则加入然后合并森林

n:点的个数;

edge_cnt:边的个数

edge[]:保存边的数组

edge_arr:保存选择边的数组,可选功能

*/

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 const int N=1001; //定义能处理的最大点的个数 6  7 template 
       
         8 struct Edge 9 {10     int from;11     int to;12     T cost;13 };14 15 template 
        
         16 T MST_Kruskal(const int & n,const int & edge_cnt,Edge
         
           edge[],Edge
          
            * edge_arr=NULL)17 {18 T ans=0;19 int i,x,y,p[N],cnt=0;20 memset(p,-1,sizeof(p));21 sort(edge,edge+edge_cnt);22 for(i=0;i