graph.cpp

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

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

#include "SQStack.h" //第三章的顺序栈
#include "SQQueue.h" //第三章的顺序队列


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

//判空操作:若图为空,返回true;否则,返回false
template <class TYPE, class KTYPE> 
bool Graph<TYPE, KTYPE> :: emptyGraph()
{  return (count == 0);
}

//求图中顶点个数
template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> :: graphCount()
{  return (count);
}

//在图中找出关键字为key的顶点,将该顶点数据信息存入dataOut中
//返回值：-1表示图为空; 1表示找到该顶点; -2表示没有找到该顶点
template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> :: retrieveVertex(KTYPE key, TYPE& dataOut)
{  Vertex<TYPE> *walkPtr;   
	if(!first) return -1;   
	walkPtr=first;   
	while(walkPtr && key > (walkPtr->data).key)      
		walkPtr = walkPtr->pNextVertex;   
	if (key == (walkPtr->data).key)   
	{  dataOut = walkPtr->data;      
		return 1;   
	}else	 return -2;
}

//求指定关键字对应顶点的第一条弧,该弧弧头顶点的数据存入dataOut中
//返回值：-1表示图为空; 1表示操作成功; 
//返回值：-2表示没有找到关键字对应的顶点; -3表示该顶点出度为零
template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> :: firstArc(KTYPE key,   TYPE& dataOut)
{  Vertex<TYPE>  *walkPtr;   
	Arc<TYPE> *toPtr;   
	if(!first) return -1;   
	walkPtr = first;   
	while(walkPtr && key > walkPtr->data.key)      
		walkPtr = walkPtr->pNextVertex;   
	if(key == (walkPtr->data).key)      
		if(walkPtr->pArc)      
		{  toPtr = walkPtr->pArc;         
			dataOut = toPtr->destination->data;	    
			return 1;	 
		}else return -3; //该顶点出度为零   
	else return -2; //没有找到关键字对应的顶点
}

//析构函数
template <class TYPE, class KTYPE> 
Graph<TYPE, KTYPE> :: ~Graph()
{  Vertex<TYPE> *verDltPtr;   
	Arc<TYPE> *arcDltPtr;   
	if(first) //非空图的删除   
	{  while(count > 0) //图中还存在节点，就继续删除	 
		{  verDltPtr = first;         
			first = first->pNextVertex;	    
			while (verDltPtr->pArc)	    
			{  arcDltPtr  = verDltPtr->pArc;	       
				verDltPtr->pArc  = arcDltPtr->pNextArc;	       
				delete arcDltPtr;	    
			}	    
			delete verDltPtr;	    
			count--;	 
		}   
	}
}



//在图中插入一个新顶点,其数据信息预存在输入参数dataIn中
template <class TYPE, class KTYPE> 
void Graph<TYPE, KTYPE> ::  insertVertex(TYPE dataIn) 
{  Vertex<TYPE>  *newPtr, *locPtr, *predPtr;   
	newPtr = new Vertex<TYPE>;   
	newPtr->pNextVertex=NULL; newPtr->data=dataIn; newPtr->pArc=NULL;
   newPtr->inDegree=0; newPtr->outDegree=0; newPtr->processed=0;   
	count++;   
	locPtr = first;   
	if (!locPtr) first = newPtr; //原来是空图   
	else   
	{  predPtr = NULL;	 
		while(locPtr && dataIn.key > (locPtr->data).key)	 
		{  predPtr=locPtr; locPtr=locPtr->pNextVertex;	 
		}	 
		if(!predPtr) first = newPtr; //插在最前端	 
		else predPtr->pNextVertex = newPtr;	 
		newPtr->pNextVertex = locPtr;   
	}
} 

//删除顶点,待删顶点的关键字在输入参数dltKey中指定
//返回值:-2表示不存在待删顶点;-1表示该顶点的度不为零,不能删除;1表示删除操作成功
template <class TYPE, class KTYPE> 
int  Graph<TYPE, KTYPE> :: deleteVertex(KTYPE dltKey)
{  Vertex<TYPE>  *predPtr, *walkPtr;   
	if(!first) return -2; //图为空, 不存在待删顶点   
	predPtr = NULL; walkPtr = first;   
	while(walkPtr && dltKey > (walkPtr->data).key)   
	{  predPtr = walkPtr; walkPtr = walkPtr->pNextVertex;   
	}   
	if(!walkPtr || dltKey != (walkPtr->data).key) return -2; //不存在待删顶点   
	if((walkPtr->inDegree > 0) || (walkPtr->outDegree > 0)) return -1;   
	if(!predPtr) first = walkPtr->pNextVertex;   
	else predPtr->pNextVertex = walkPtr->pNextVertex;   
	count--;   
	delete walkPtr;   
	return 1;
}

//弧的插入操作:弧尾与弧头的关键字预存在输入参数fromKey和toKey中
//返回值:1代表插入成功;-1代表指定弧尾顶点不存在;-2代表指定弧头顶点不存在
template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> :: insertArc(KTYPE fromKey, KTYPE toKey)
{  Arc<TYPE>  *newPtr, *arcPredPtr, *arcWalkPtr;   
	Vertex<TYPE>  *vertFromPtr, *vertToPtr;   
	newPtr = new Arc<TYPE>;   
	vertFromPtr = first;   
	while(vertFromPtr && fromKey > (vertFromPtr->data).key)      
		vertFromPtr = vertFromPtr->pNextVertex;   
	if(!vertFromPtr || fromKey != (vertFromPtr->data).key)      
		return (-1);  //无指定弧尾顶点   
	vertToPtr = first;   
	while(vertToPtr && toKey > (vertToPtr->data).key)      
		vertToPtr   = vertToPtr->pNextVertex;   
	if(!vertToPtr  || toKey !=  (vertToPtr->data).key)      
		return (-2); //无指定的弧头顶点   
	++vertFromPtr->outDegree; ++vertToPtr->inDegree;   
	newPtr->destination = vertToPtr;   
	if(!vertFromPtr->pArc)   
	{  vertFromPtr->pArc=newPtr; newPtr->pNextArc=NULL;      
		return 1;   
	}   
	arcPredPtr=NULL; arcWalkPtr=vertFromPtr->pArc;   
	while(arcWalkPtr && toKey >= (arcWalkPtr->destination->data).key)   
	{  arcPredPtr=arcWalkPtr; arcWalkPtr=arcWalkPtr->pNextArc;   
	}    
	if(!arcPredPtr) vertFromPtr->pArc=newPtr;   
	else arcPredPtr->pNextArc=newPtr;   
	newPtr->pNextArc=arcWalkPtr;   
	return 1;
}

//弧的删除操作:弧尾与弧头的关键字预存在输入参数fromKey和toKey中
//返回值:1代表删除成功;-1代表图为空;-2代表无指定的弧尾顶点;-3代表无指定的弧头顶点
template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> :: deleteArc (KTYPE  fromKey, KTYPE  toKey)
{  Vertex<TYPE>  *fromVertexPtr, *toVertexPtr;   
	Arc<TYPE>  *preArcPtr, *arcWalkPtr;   
	if(!first) return -1;   
	fromVertexPtr = first;   
	while(fromVertexPtr && fromKey > (fromVertexPtr->data).key)      
		fromVertexPtr=fromVertexPtr->pNextVertex;   
	if(!fromVertexPtr || fromKey != (fromVertexPtr->data).key) return -2;   
	if(!fromVertexPtr->pArc) return -3; //该顶点出度为零,故找不到待删的弧   
	preArcPtr=NULL; arcWalkPtr=fromVertexPtr->pArc;   
	while(arcWalkPtr && toKey > (arcWalkPtr->destination->data).key)   
	{  preArcPtr=arcWalkPtr;      
		arcWalkPtr=arcWalkPtr->pNextArc;   
	}    
	if(!arcWalkPtr || toKey != (arcWalkPtr->destination->data).key)      
		return -3;   
	toVertexPtr = arcWalkPtr->destination;   
	--fromVertexPtr->outDegree; --toVertexPtr->inDegree;    
	if(!preArcPtr) fromVertexPtr->pArc = arcWalkPtr->pNextArc;   
	else preArcPtr->pNextArc = arcWalkPtr->pNextArc;   
	delete arcWalkPtr;   
	return 1;
} 

//图的遍历:深度优先搜索法
template <class TYPE, class KTYPE> 
void Graph<TYPE, KTYPE> :: depthFirstTraverse(void (*visit)(TYPE &info)) {
	Vertex<TYPE> *walkPtr, *vertexPtr, *vertToPtr;   
	sqStack<Vertex<TYPE>*>  nodes; //使用第三章的栈   
	Arc<TYPE> *arcWalkPtr;   
	if (!first) return; //图为空时,返回   
	walkPtr=first;   
	while(walkPtr) //将已访问标记清零，表示尚未访问   
	{  walkPtr->processed=0; walkPtr=walkPtr->pNextVertex;   
	}    
	walkPtr=first;   
	while(walkPtr)   
	{  if(walkPtr->processed < 2)      
		{  if(walkPtr->processed < 1)         
			{  nodes.Push(walkPtr);            
				walkPtr->processed=1; //已入栈,是第一次访问顶点	    
			} // if processed < 1 	    
			while(!nodes.isEmpty())	    
			{  nodes.GetTop(vertexPtr); nodes.Pop(); //弹出栈顶元素并使用
				visit(vertexPtr->data);	       
				vertexPtr->processed=2; //已出栈并进行处理,是第二次访问顶点
				arcWalkPtr=vertexPtr->pArc; //准备找与由顶点指向的其他顶点
				while(arcWalkPtr)	       
				{  vertToPtr=arcWalkPtr->destination;	          
					if(vertToPtr->processed == 0) //发现新顶点,由当前顶点指向它
					{  nodes.Push(vertToPtr);	             
						vertToPtr->processed=1;	          
					} // if vertToPtr               
					arcWalkPtr=arcWalkPtr->pNextArc;            
				} // while arcWalkPtr         
			} //  while !emptyStack      
		} // if processed < 2      
		walkPtr=walkPtr->pNextVertex; //保证非连通图中其他连通分量也能被遍历   
	} // while walkPtr
}

//图的遍历:广度优先搜索法
template <class TYPE, class KTYPE> 
void Graph<TYPE, KTYPE> ::  breadthFirstTraverse(void (*visit)(TYPE &info))
{  Vertex<TYPE>  *walkPtr, *vertexPtr, *vertToPtr;   
	Arc<TYPE> *arcWalkPtr;   
	sqQueue<Vertex<TYPE>*> nodes; //使用第三章的队列   
	if(!first) return; //空图无需遍历   
	walkPtr=first;   
	while(walkPtr) //将已访问标记清零，表示尚未访问   
	{  walkPtr->processed=0; walkPtr=walkPtr->pNextVertex;   
	} // while    
	walkPtr=first;   
	while(walkPtr)   
	{  if(walkPtr->processed < 2)	 
		{  if(walkPtr->processed < 1) //发现新顶点	    
			{  nodes.EnQueue(walkPtr); //入队列是第一次访问顶点,假定入队操作不会失败
				walkPtr->processed=1;	    
			} // if processed < 1          
			while(!nodes.isEmpty())	    
			{  nodes.GetFront(vertexPtr); nodes.DelQueue();            
				visit(vertexPtr->data);            
				vertexPtr->processed=2; //出队列并处理是第二次访问
				arcWalkPtr=vertexPtr->pArc; //查找所有与当前顶点邻接的其他顶点
				while(arcWalkPtr)	       
				{  vertToPtr=arcWalkPtr->destination;	          
					if(vertToPtr->processed == 0) //发现新顶点	          
					{  nodes.EnQueue(vertToPtr); 	             
						vertToPtr->processed=1;	          
					} // if vertToPtr                
					arcWalkPtr = arcWalkPtr->pNextArc; 	       
				} // while arcWalkPtr 	    
			} // while !emptyQueue       
		} // if processed < 2      
		walkPtr = walkPtr->pNextVertex; //保证非连通图中其他连通分量也能被遍历
	} // while walkPtr
} // breadthFirst

//拓扑排序:深度优先搜索
template <class TYPE, class KTYPE> 
void Graph<TYPE,KTYPE>::toplogicalSortDepthFirst(void (*visit)(TYPE &data)) {  
	Vertex<TYPE> *walkPtr, *vertToPtr;   
	sqStack<Vertex<TYPE>*>  nodes; //使用第三章的栈   
	Arc<TYPE> *arcWalkPtr;   
	if (!first) return; //空图无需进行拓扑排序   
	for(walkPtr=first; walkPtr; walkPtr=walkPtr->pNextVertex)      
		if(walkPtr->inDegree==0) nodes.Push(walkPtr); //栈中存放入度为零的顶点   
	while(!nodes.isEmpty())   
	{  nodes.GetTop(walkPtr); nodes.Pop();      
		visit(walkPtr->data); //可以直接简单输出      
		arcWalkPtr=walkPtr->pArc; //该顶点直接指向的所有顶点入度降1
		while(arcWalkPtr)      
		{  vertToPtr=arcWalkPtr->destination;         
			if (vertToPtr->inDegree>0) //发现没处理的顶点         
			{  vertToPtr->inDegree--;	       
				if (vertToPtr->inDegree==0) nodes.Push(vertToPtr);
			} // if vertToPtr         
			arcWalkPtr = arcWalkPtr->pNextArc;      
		} // while arcWalkPtr   
	} //  while !emptyStack
}

//图的输出
template <class TYPE, class KTYPE> 
void Graph<TYPE, KTYPE> :: outputGraph() {
	Vertex<TYPE>  *curVertexPtr;   
	Arc<TYPE>  *curArcPtr;   
	if(first) {
		cout<<"Graph content:"<<endl;
		curVertexPtr = first;   
		while(curVertexPtr != NULL) {
			cout<<"Vertex:"<<curVertexPtr->data.key<<endl;
			curArcPtr=curVertexPtr->pArc; 
			while(curArcPtr != NULL) {
				cout<<curVertexPtr->data.key;
				cout<<"--->";
				cout<<curArcPtr->destination->data.key<<endl;
				curArcPtr=curArcPtr->pNextArc;
			}
			curVertexPtr=curVertexPtr->pNextVertex;
		}
	}else {
		cout<<"Graph is empty."<<endl;
	}
}


struct TestType {
	int key;
};

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

void main() {
	Graph<TestType,int> g1;
	if(g1.emptyGraph()) cout<<"Graph is empty.\n";
	else cout<<"Graph is not empty.\n";
	TestType tt1;
	tt1.key=1;
	g1.insertVertex(tt1);
	cout<<"after insert vertex 1"<<endl;
	if(g1.emptyGraph()) cout<<"Graph is empty.\n";
	else cout<<"Graph is not empty.\n";
	cout<<g1.graphCount()<<endl;
	g1.outputGraph();
	cout<<"......"<<endl;

	TestType tt2;
	tt2.key=2;
	g1.insertVertex(tt2);
	cout<<"after insert vertex 2"<<endl;
	cout<<g1.graphCount()<<endl;
	g1.outputGraph();
	
	cout<<"......"<<endl;

	TestType tt3;
	tt3.key=3;
	g1.insertVertex(tt3);
	cout<<"after insert vertex 3"<<endl;
	cout<<g1.graphCount()<<endl;
	g1.outputGraph();
	g1.insertArc(1,3);
	cout<<"after insert Arc(1,3)"<<endl;
	g1.outputGraph();
	TestType tt4;
	g1.firstArc(1,tt4);
	cout<<"first arc of vertex 1:1-->"<<tt4.key<<endl;
	

	g1.insertArc(3,2);
	cout<<"after insert Arc(3,2)"<<endl;
	g1.outputGraph();

	g1.retrieveVertex(3,tt4);
	cout<<"the key of vertex 3 is:"<<tt4.key<<endl;

	tt4.key=4;
	g1.insertVertex(tt4);
	cout<<"after insert vertex 4"<<endl;
	cout<<g1.graphCount()<<endl;
	g1.outputGraph();
	g1.insertArc(1,4);
	cout<<"after insert Arc(1,4)"<<endl;
	g1.outputGraph();
	
	g1.insertArc(2,4);
	cout<<"after insert Arc(2,4)"<<endl;
	g1.outputGraph();

	cout<<"BreadthFirstTraverse:"<<endl;
	g1.breadthFirstTraverse(&testVisiting);
	cout<<"DepththFirstTraverse:"<<endl;
	g1.depthFirstTraverse(&testVisiting);
	cout<<"ToplogicalSortDepththFirst:"<<endl;
	g1.toplogicalSortDepthFirst(&testVisiting);

	/*g1.deleteArc(1,2);
	cout<<"after delete Arc(1,2)"<<endl;
	g1.outputGraph();



	int result=g1.deleteVertex(1);
	if(result==1) g1.outputGraph();
	else {
		g1.deleteArc(1,3);
		g1.deleteArc(1,2);
		cout<<"after delete Arc(1,3),Arc(2,3)"<<endl;
		g1.outputGraph();
		result=g1.deleteVertex(1);
		g1.outputGraph();
	}

	if(g1.emptyGraph()) cout<<"Graph is empty.\n";
	else cout<<"Graph is not empty.\n";
	cout<<g1.graphCount()<<endl;

	g1.deleteVertex(2);
	g1.deleteVertex(3);
    if(g1.emptyGraph()) cout<<"Graph is empty.\n";
	else cout<<"Graph is not empty.\n";
	cout<<g1.graphCount()<<endl;
	*/
}