fibhead.h

应用斐波纳契堆和邻接表改进单源最短路径算法

/////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////
enum Boolean{FALSE,TRUE};
const int nmax=40;
template<class Type>
class FibHeap;
///////////////////////////////////////////////////////////////////////////////////////

template<class Type>
struct Element{
	Type key;
	Type id;
};
/////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////堆节点定义//////////////////////////////////////////////

template<class Type>
class FibNode
{
	friend class Graph;
	friend class FibHeap<Type>;
public:
	FibNode(){child=parent=leftlink=rightlink=0;};
	~FibNode(){};
private:
	Element<Type> data;
	FibNode<Type>*child,*leftlink,*rightlink;
	FibNode<Type> *parent;
		
	bool ChildCut;
	int degree;
		
};

/////////////////////////////////////////////////////////////////////////////
//////////////////////////////////堆定义/////////////////////////////////////
template<class Type>
class FibHeap
{
		friend class Graph;
	public:
		FibHeap(FibNode<Type>*init=0){
			min=init;
			Size=0;
		}

		void Insert(const Element<Type>&x);                      //插入数据	
		Element<Type> *DeleteMin(Element<Type>&);                //删除最小元素结点
		void Minus(FibNode<Type>*,int minus);                    //key值减少
		Element<Type>*Delete(FibNode<Type>*);                    //删除任意元素结点
		void display36(FibNode<Type>* p,int n);
		~FibHeap(){};

	private:
		void CastcadingCut(FibNode<Type>*);                        //瀑布修剪
		FibNode<Type>* JoinMinTree(FibNode<Type> *p,FibNode<Type> *q);
		void Move(FibNode<Type> *b);                               //将b变作根结点
		FibNode<Type>*min;
		void Display(FibNode<Type>* root);	
		FibNode<int> *ps1[nmax];
		int Size;                                 //所有结点的个数
		int MaxDegree;	
};

///////////////////////////////////////////////////////////////////////////////////////
////////////////////////插入//////////////////////////////////////////////////////////
template<class Type>
void FibHeap<Type>::Insert(const Element<Type>&x)
{   
	FibNode<Type>*p=new FibNode<Type>;  
	ps1[x.id]=p;
	p->data.key=x.key;
	p->data.id=x.id;        
	p->child=0;                                                  
	p->parent=0;
	p->degree=0;
	p->ChildCut=false;
	
	if(min==0)
	{
		min=p;
		min->rightlink=min->leftlink=p;
	}
	else
	{
		p->leftlink=min;
		p->rightlink=min->rightlink;
		min->rightlink->leftlink=p;
		min->rightlink=p;
	}

	if(min->data.key>p->data.key)
		min=p;
	Size++ ;                                                   
}

//////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////key值减少///////////////////////////////////////
template<class Type>
void FibHeap<Type>::Minus(FibNode<Type>*b,int a)                   
{
	b->data.key-=a;
	if(b->parent)                                
	{
		if(b->data.key<b->parent->data.key)                 
		{
			Move(b);
		}
	}
	if(b->data.key<min->data.key)                      
	{
		min=b;
	}
}

/////////////////////////////////////////////////////////////////////////////
/////////////////////////////////瀑布修剪///////////////////////////////////
template<class Type>
void FibHeap<Type>::CastcadingCut(FibNode<Type>*b)
{
	if(!b->parent)                                                                     
		return;
    Move(b);                                  
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////根节点归并//////////////////////////////////////
template<class Type>
void FibHeap<Type>::Move(FibNode<Type> *b)                           
{
	b->leftlink->rightlink=b->rightlink;             
	b->rightlink->leftlink=b->leftlink;
	min->rightlink->leftlink=b;
	b->rightlink=min->rightlink;
	b->leftlink=min;
	min->rightlink=b;
	b->parent->degree--;                             
	b->parent=0;                                    
}

////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////删除最小节点//////////////////////////////////////
template<class Type>
Element<Type>* FibHeap<Type>::DeleteMin(Element<Type>&x)                   
{
	if(!min){
		cout<<"It's empty."<<endl;
		Size--;
		return 0;
	}
	x=min->data;
	FibNode<Type> *d=min;
	FibNode<Type> *y=min->child;
	FibNode<Type> *s=y;
	FibNode<Type> *xx=min->rightlink;
 	if(min==min->rightlink){
		if(y){  //如果min有子女
			min=y;
			do{
				y->parent=0;
				y=y->rightlink;
			}while(y!=s->leftlink);
			s->parent=0;
			delete d;
		}
		else{
			min=0;
			delete d;
		}
	}
	else{                                           
		min->leftlink->rightlink=min->rightlink;                         
		min->rightlink->leftlink=min->leftlink;
		min=xx;
		if(y){               //如果min有子女
			y->parent=0;
			for(FibNode<Type>* a=y->rightlink;a!=y;a=a->rightlink)
				a->parent=0;

			y->rightlink->leftlink=min;
			min->rightlink->leftlink=y;
			FibNode<Type>* kk=min->rightlink;
			min->rightlink=y->rightlink; 
			y->rightlink=kk ;
		}
 		delete d;
	}
	Size--; 
	MaxDegree=int(log(Size)/log(1.618))+1;           
	FibNode<Type>** Tree=new FibNode<Type>*[MaxDegree];	 

	for(int v=0;v<MaxDegree;v++)
		Tree[v]=0;

    int d1=0;    
	Tree[min->degree]=min;             
	FibNode<Type> *ps=0;
	for(FibNode<Type> *p=min->rightlink;p!=min;p=ps){
		ps=p->rightlink;
		for(d1=p->degree;Tree[d1];d1++){                                           
			p=JoinMinTree(p,Tree[d1]);
			Tree[d1]=0;
		}
        Tree[d1]=p;
	}
	int k=0;                                               
	while(!Tree[k])
		k++;   
	
    FibNode<Type> *t1=Tree[k];
	min=Tree[k];					
	for(int i=k+1;i<MaxDegree;i++){                                                            
		if(Tree[i]){
			t1->rightlink=Tree[i];
			Tree[i]->leftlink=t1;

			if(min->data.key>Tree[i]->data.key)              //顺便确定最小结点
				min=Tree[i];             

		t1=Tree[i];  
		} 
	}
   	t1->rightlink=Tree[k];     
	Tree[k]->leftlink=t1;
	delete []Tree;
	return &x;
}

/////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////合并最小树/////////////////////////////////////////////
template<class Type>
FibNode<Type>* FibHeap<Type>::JoinMinTree(FibNode<Type> *p,FibNode<Type> *q)
{
	if(!q)                          
		return p;
	if(p->data.key < q->data.key)     {
		if(!p->child){		
			p->child=q;
			q->leftlink=q;
			q->rightlink=q;
		}
		else{
			if(p->degree==1){			
				p->child->rightlink=q;
				p->child->leftlink=q;
				q->leftlink=p->child;
				q->rightlink=p->child;
			}
			else{
			    p->child->rightlink->leftlink=q;
			    q->rightlink=p->child->rightlink;
			    q->leftlink=p->child;
			    p->child->rightlink=q;
			}
		}
		p->parent=0;
		q->ChildCut=false;
		q->parent=p;                           //p成为q的父母，则p的子女个数加1
		p->degree++;			
	}
	else {
		if(!q->child){
			q->child=p;
			p->leftlink=p;
			p->rightlink=p;
		}
		else{
			if(q->degree==1){		
				q->child->rightlink=p;
				q->child->leftlink=p;
				p->leftlink=q->child;
				p->rightlink=q->child;
			}
			else{				
		        q->child->rightlink->leftlink=p;
	        	p->rightlink=q->child->rightlink;
				p->leftlink=q->child;
		        q->child->rightlink=p;
			}
		}
		q->parent=0;
		p->ChildCut=false;
		p->parent=q;
		q->degree++;                        
	 	p=q;
	}
 return p;                         
}
///////////////////////////////////////////////////////////////////////////////////////////////