Sollin算法可以看作是Kruskal算法和Prim算法的综合

基本思想是：

1. 从所有节点都孤立的森林开始，通过合并树来得到最小生成树

2. 每次合并树的边都是用最小权重的割边

程序具体实现思路：

初始化，update所有点（update函数只在开始处使用一次，以后就不用了）（update的具体操作类似于prim算法里的update）

循环一：找最小割边（FindMin）

循环二：1.根据每棵树都的最小割边进行合并

2.V[gen]中删除S[gen_other]中的所有元素

3.S[gen]中增加S[gen_other]中的所有元素

4.更新d值，在V[gen]中比较d[gen][i]和d[gen_other][i],取小值

和prim算法相比，这里的V和S都是有维度的，还有d也从一维变成了二维，增加的维度是对每棵树的标示

我用C++实现的Sollin算法源程序如下：

（1）common.h 主要是程序的头文件

（2）sollin.cpp 图的创建和算法启动点

（3）resources.h 图类、边类、点类，其中图类中包含了整个程序的核心部分

(1)common.h

#define _COMMON_H_#include 

(2)sollin.cpp

#include "resources.h"CEdge::CEdge(int a, int b, int c, int d){	tail=a;	head=b;	weight=c;	capacity=d;}CEdge::CEdge(int a, int b, int c){	head=b;	tail=a;	weight=c;}CEdge::CEdge(CEdge & x){	tail=x.getTail();	head=x.getHead();	weight=x.getWeight();	capacity=x.getCap();}CGraph::CGraph(list
    
      listEdge){	IncidentList=listEdge;	numVertex=N;	numEdge=listEdge.size();}void main(){	list
     
       listEdge;		CEdge* e1= new CEdge(1,2,35,10);	CEdge* e2= new CEdge(1,3,40,10);	CEdge* e3= new CEdge(2,3,25,10);	CEdge* e4= new CEdge(2,4,10,10);	CEdge* e5= new CEdge(3,4,20,10);	CEdge* e6= new CEdge(3,5,15,10);	CEdge* e7= new CEdge(4,5,30,10);		CEdge* e8= new CEdge(2,1,35,10);	CEdge* e9= new CEdge(3,1,40,10);	CEdge* e10= new CEdge(3,2,25,10);	CEdge* e11= new CEdge(4,2,10,10);	CEdge* e12= new CEdge(4,3,20,10);	CEdge* e13= new CEdge(5,3,15,10);	CEdge* e14= new CEdge(5,4,30,10);	listEdge.push_back(e1);	listEdge.push_back(e2);	listEdge.push_back(e3);	listEdge.push_back(e4);	listEdge.push_back(e5);	listEdge.push_back(e6);	listEdge.push_back(e7);		listEdge.push_back(e8);	listEdge.push_back(e9);	listEdge.push_back(e10);	listEdge.push_back(e11);	listEdge.push_back(e12);	listEdge.push_back(e13);	listEdge.push_back(e14);	CGraph g(listEdge);	g.p3();	g.p4();	g.solin();	getchar();}
     
    

(3)resources.h

#include "common.h"int set1[110]={0};int FindSet(int x){	if(x==set1[x])		return x;	else		return set1[x]=FindSet(set1[x]);}void UnionSet(int x, int y){	int fx=FindSet(x);	int fy=FindSet(y);	set1[fy]=fx;}class CEdge{private:	int tail, head;	int weight, capacity;public:	CEdge(int a, int b, int c, int d);	CEdge(int a, int b, int c);	CEdge(CEdge &x);	int getHead(){return head;}	int getTail(){return tail;}	int getWeight(){return weight;}	int getCap(){return capacity;}	};bool cmp(CEdge* a, CEdge* b){	if(a->getWeight()
    
     getWeight())		return 1;	else		return 0;}class CGraph{private:	int numVertex;	int numEdge;	list
     
       IncidentList;public:	CGraph(char* inputFile);	CGraph(list
      
        listEdge);	CGraph(CGraph &);	map
       
        
         > nelist;	vector
         
          
           > adjmatrix; int d[N+10][N+10]; set
           
             S[N+10];//被永久标记的点集 set
            
              V[N+10];//初始点集 int getNumVertex(){ return numVertex; } int getNumEdge(){ return numEdge; } void p3(){ list
             
              ::iterator it,iend; iend=IncidentList.end(); CEdge* emptyedge=new CEdge(-1,-1,-1,-1); for(int i=0;i<=numVertex;i++) { vector
              
                vec; for(int j=0;j<=numVertex;j++) { vec.push_back(emptyedge); } adjmatrix.push_back(vec); } for(it=IncidentList.begin();it!=iend;it++){ adjmatrix[(*it)->getTail()][(*it)->getHead()] = *it ; } } void p4(){ list
               
                ::iterator it,iend; iend=IncidentList.end(); for(it=IncidentList.begin();it!=iend;it++) nelist[(*it)->getTail()].push_back(*it); list
                
                 ::iterator it2,iend2; iend2=nelist[3].end(); } void Update(int k, int i){ list
                 
                  ::iterator it,iend; it=nelist[i].begin(); iend=nelist[i].end(); for(;it!=iend;it++) if((*it)->getWeight()
                  
                   getHead()]){ d[k][(*it)->getHead()]=(*it)->getWeight(); } } int FindMin(int k){ set
                   
                    ::iterator vi,vend; vend=V[k].end(); int mini=10000000; int loc=0; for(vi=V[k].begin();vi!=vend;vi++) if(mini>=d[k][*vi]) {mini=d[k][*vi];loc=*vi;} return loc; } void solin(){ printf("sollin:\n"); for(int i=1;i<=N;i++) set1[i]=i; list
                    
                      T; int e[N+10]; //初始化操作 int j,k; for(k=1;k<=N;k++) for(j=1;j<=N;j++){ V[k].insert(j); d[k][j]=INF; } for(k=1;k<=N;k++){ S[k].insert(k); V[k].erase(k); d[k][k]=0; Update(k,k); } while(T.size()<(N-1)) { for(int i=1;i<=N;i++) { if(i!=FindSet(i)) continue; e[i]=FindMin(i); }//1 for 查找N(k)与V–N(k)之间的最小割边 for(int i=1;i<=N;i++) { if(i!=FindSet(i)) continue; if(FindSet(e[i])!=FindSet(i)) { UnionSet(e[i],i);//合并树 //V[gen]中删除S[gen_other]中的所有元素 //S[gen]中增加S[gen_other]中的所有元素 int gen,gen_other; gen=FindSet(i); if(gen==i) gen_other=e[i]; else gen_other=i; set
                     
                      ::iterator it,iend; iend=S[gen_other].end(); for(it=S[gen_other].begin();it!=iend;it++){ V[gen].erase(*it); S[gen].insert(*it); } //更新d值，在V[gen]中比较d[gen][i]和d[gen_other][i],取小值 iend=V[gen].end(); for(it=V[gen].begin();it!=iend;it++) if(d[gen][*it]>d[gen_other][*it]) d[gen][*it]=d[gen_other][*it]; T.push_back(adjmatrix[e[i]][i]); printf("%d---%d\n",e[i],i); } }//2 for 合并两棵树 }//while循环 }//sollin算法};//graph类