network.cpp

这是本人精心搜集的关于常用图论算法的一套源码

#include "Network.h"
#include <iostream.h>

//构造函数
template <class TYPE, class KTYPE> 
Network<TYPE, KTYPE> :: Network()
{  first=NULL;   count=0;}

//析构函数
template <class TYPE, class KTYPE> 
Network<TYPE, KTYPE> :: ~Network()
{  Vertex<TYPE> *verDltPtr;   
   Edge<TYPE> *edgeDltPtr;   
   if(first) //非空网的删除   
    { while(count > 0) //网中还存在节点，就继续删除	 
       {  verDltPtr = first;         
          first = first->pNextVertex;	    
          while (verDltPtr->pEdge)	    
           {  edgeDltPtr = verDltPtr->pEdge;	       
              verDltPtr->pEdge  = edgeDltPtr->pNextEdge;	       
              delete edgeDltPtr;	    
           }	    
          delete verDltPtr;	    
          count--;	 
       }   
    }
}

//在网中插入一个新顶点,其数据信息预存在输入参数dataIn中
template <class TYPE, class KTYPE> 
void Network<TYPE, KTYPE>::insertVertex(TYPE dataIn)
{ Vertex<TYPE>  *newPtr;   
  newPtr = new Vertex<TYPE>;   
  newPtr->data=dataIn; newPtr->degree=0; newPtr->pEdge=NULL;   
  newPtr->inTree=0; //起始状态下,该顶点不在最小成树中   
  count++;      
  newPtr->pNextVertex=first; first = newPtr; //为简单起见,直接在链头插入
} 

//边的插入操作:该边的两个顶点关键字预存在输入参数fromKey和toKey中,权值存在w中
//返回值:true代表插入成功;false代表指定关键字对应的顶点不存在
template <class TYPE, class KTYPE> 
bool Network<TYPE, KTYPE> :: insertEdge(KTYPE fromKey, KTYPE toKey, int w)
{ Edge<TYPE>  *newPtr;   
  Vertex<TYPE>  *vertFromPtr, *vertToPtr;   
  vertFromPtr = first;   
  while(vertFromPtr && fromKey != (vertFromPtr->data).key)      
  	vertFromPtr = vertFromPtr->pNextVertex;   
  if(!vertFromPtr)      
  	return false;  //指定关键字顶点不存在   
  vertToPtr = first;   
  while(vertToPtr && toKey != (vertToPtr->data).key)      
  	vertToPtr = vertToPtr->pNextVertex;   
  if(!vertToPtr)      
  	return false; //指定关键字顶点不存在   
  ++vertFromPtr->degree; ++vertToPtr->degree;   
  newPtr = new Edge<TYPE>;   
  newPtr->weight=w; newPtr->inTree=0; //初始状态下,该边不在最小生成树中
  newPtr->destination = vertToPtr;   
  newPtr->pNextEdge = vertFromPtr->pEdge;    
  vertFromPtr->pEdge = newPtr;   
  newPtr = new Edge<TYPE>; //一条边对应两个节点   
  newPtr->weight=w; newPtr->inTree=0; //初始状态下,该边不在最小生成树中
  newPtr->destination = vertFromPtr;   
  newPtr->pNextEdge = vertToPtr->pEdge;    
  vertToPtr->pEdge = newPtr;   
  return true;
}

//最小生成树,Kruskal算法
template <class TYPE, class KTYPE> 
void Network<TYPE, KTYPE> :: MSTKruskal()
{ Edge<TYPE>  *edgePtr, *minEdgePtr;   
  Vertex<TYPE>  *walkerPtr, *vertexPtr; 
  if(first==NULL) return;
  int times=1; 
  for(walkerPtr=first; walkerPtr; walkerPtr=walkerPtr->pNextVertex)   
     { walkerPtr->inTree=times; times++;  }//初始化,每个顶点自己是一个独立的连通分量   
  
  int minEdge;   
  for(int edgeCount=1; edgeCount<count; edgeCount++) //找到N-1条边即可   
     {walkerPtr=first; times=1;      
      while(walkerPtr)       
       { for(edgePtr=walkerPtr->pEdge; edgePtr; edgePtr=edgePtr->pNextEdge) 
          if(edgePtr->inTree==0 )                
            if(walkerPtr->inTree == edgePtr->destination->inTree)
              edgePtr->inTree=-1; //该边两顶点已属于同一连通分量，以后不再考虑
            else                   
             if(times==1) //本轮第一次碰到的边假定为最小值
               { minEdgePtr=edgePtr; minEdge=edgePtr->weight;
                 vertexPtr=walkerPtr; times++;
               }                 
             else  //寻找本轮真正的最小边
              if(edgePtr->weight< minEdge)
                {minEdgePtr=edgePtr; minEdge=edgePtr->weight; 
                 vertexPtr=walkerPtr;
                }         
         walkerPtr=walkerPtr->pNextVertex;      
       } //找到本轮最小值      
      if(minEdgePtr)//插入最小边到树中     
        {  minEdgePtr->inTree=1;          
           //网中一条边对应两个边节点,已处理完一个边节点,将另一个边节点置为不可用         
          edgePtr= minEdgePtr->destination->pEdge;         
          while(edgePtr)
           { 
            if((vertexPtr->data).key==(edgePtr->destination->data).key) 
               edgePtr->inTree=-1;            
            edgePtr=edgePtr->pNextEdge;         
           }
          //-----------------
          cout<<minEdgePtr->weight<<":(";
          cout<<(vertexPtr->data).key;
          cout<<"-->";
          cout<<(minEdgePtr->destination->data).key;
          cout<<")"<<endl;
          //合并两个连通分量         
          for(walkerPtr=first; walkerPtr; walkerPtr=walkerPtr->pNextVertex)
          if(walkerPtr->inTree== minEdgePtr->destination->inTree)               
            walkerPtr->inTree= vertexPtr->inTree;      
	}   
     }
}

//最小生成树,Prim算法
template <class TYPE, class KTYPE> 
void Network<TYPE, KTYPE> :: MSTPrim()
{  Edge<TYPE>  *edgePtr=NULL, *minEdgePtr=NULL;   
   Vertex<TYPE>  *walkerPtr=NULL;
   Vertex<TYPE>  *vertexPtr=NULL;//输出时用到   
   if(first==NULL) return;   
   int minEdge, times;
   first->inTree=1; //首顶点放入树中
   for(int edgeCount=1; edgeCount<count; edgeCount++) //找到N-1条边即可   
     { walkerPtr=first; times=1;      
       while(walkerPtr)       
        {  if(walkerPtr->inTree)         
             {edgePtr=walkerPtr->pEdge;            
   	      for( ; edgePtr; edgePtr=edgePtr->pNextEdge)               
               if(edgePtr->inTree==0 )                   
                 if(edgePtr->destination->inTree)
                  edgePtr->inTree=-1; //该边两顶点都已放入树中，以后不再考虑
                 else                      
                  if(times==1) //本轮第一次碰到的边假定为最小值
                    { minEdgePtr=edgePtr; minEdge=edgePtr->weight; times++; 
                      vertexPtr=walkerPtr; //输出时用到
                    }
                  else  //寻找本轮真正的最小边 
                   if(edgePtr->weight< minEdge) 
                    {  minEdgePtr=edgePtr; minEdge=edgePtr->weight; 
                       vertexPtr=walkerPtr; //输出时用到
                    }         
             } //if         
           walkerPtr=walkerPtr->pNextVertex;      
        } //找到本次最小值      
       if(minEdgePtr!=NULL)       
         { minEdgePtr->inTree=1; minEdgePtr->destination->inTree=1; 
           //--------------
           cout<<minEdgePtr->weight<<":(";
           cout<<(vertexPtr->data).key;
           cout<<"-->";
           cout<<(minEdgePtr->destination->data).key;
           cout<<")"<<endl;
           //-----------------
         }   
     }
}

//网络的输出
template <class TYPE, class KTYPE> 
void Network<TYPE, KTYPE> :: outputNetwork()
 { Vertex<TYPE>  *curVertexPtr;   
   Edge<TYPE>  *curEdgePtr;   
   if(first) 
    { cout<<"Network content:"<<endl;
      curVertexPtr = first;   
      while(curVertexPtr != NULL)
       { cout<<"Vertex:"<<curVertexPtr->data.key<<endl;
         curEdgePtr=curVertexPtr->pEdge; 
         while(curEdgePtr != NULL) 
          { cout<<curEdgePtr->weight<<":";
            cout<<curVertexPtr->data.key;
            cout<<"--->";
            cout<<curEdgePtr->destination->data.key<<endl;
            curEdgePtr=curEdgePtr->pNextEdge;
          }
         curVertexPtr=curVertexPtr->pNextVertex;
       }
    }
   else cout<<"Network is empty."<<endl;
}


struct TestType
 { int key; };

void testVisiting(TestType &data) 
{  cout<<data.key<<endl; }

void main()
{ Network<TestType,int> n1;
  for(int i=6; i>=1; i--) 
     { TestType tt; 
       tt.key=i;
       n1.insertVertex(tt);
     }
  n1.insertEdge(1,2,6);
  n1.insertEdge(1,3,5);
  n1.insertEdge(1,4,1);
  n1.insertEdge(2,4,5);
  n1.insertEdge(3,4,5);
  n1.insertEdge(5,4,6);
  n1.insertEdge(6,4,4);
  n1.insertEdge(2,5,3);
  n1.insertEdge(3,6,2);
  n1.insertEdge(5,6,6);
  n1.MSTKruskal();
  n1.outputNetwork();
  n1.MSTPrim();
  n1.outputNetwork();

}