graph.cpp

数据结构--图的常见算法实现

#define UNVISITED 0
#define VISITED 1
#define INFINITY 9999999
#define ROOT -1

#include <iostream.h>
#include <fstream.h>
#include "LList.h"
#include "minheap.h"
#include <queue>


//数据结构部分:

/**************** 图的边的定义 ***************/
class Edge
{
public:
	int from,to,weight;    //from是边的始点,to是边的终点,weight是边的权

	Edge()                 //构造函数
	{
		from=-1;   
		to=-1;  
		weight=0;
	}
	
	Edge(int f,int t,int w)  //构造函数
	{
		from=f;   
		to=t;   
		weight=w;
	}

	bool operator >(Edge oneEdge)   //定义比较运算符>,边的大小比较即为边的权的大小比较
	{
		return weight>oneEdge.weight;
	}

	bool operator <(Edge oneEdge)  //定义比较运算符<,边的大小比较即为边的权的大小比较
	{
		return weight<oneEdge.weight;
	}
};

/**************** 图的定义 ***************/
//注意：该数据结构将有向图和无向图统一处理，无向图中的一条边将相当于有向图中的两条边
class Graph
{
public:
	int numVertex;	//图的顶点的个数
	int numEdge;    //图的边的个数
	int *Mark;      //Mark指针指向保存有图的顶点的标志位的数组,标志位用来标记某顶点是否被访问过
	int *Indegree;  //Indegree指针指向保存有图的顶点的入度的数组	
	
	Graph(int numVert)               //构造函数
	{
		numVertex=numVert;           //确定图的顶点的个数
		numEdge=0;                   //确定图的边数的个数
		Indegree=new int[numVertex]; //为保存图的顶点的入度申请数组,Indegree为数组指针
		Mark=new int[numVertex];     //为图的顶点的标志位申请数组,Mark为数组指针
		for(int i=0;i<numVertex;i++) //确定图的顶点的标志位和入度,即所有顶点的标志位初始化为未被访问过,入度初始化为0
		{
			Mark[i]=UNVISITED;
			Indegree[i]=0;
		}
	}

	~Graph()                         //析构函数
	{
		delete [] Mark;              //释放Mark数组
		delete [] Indegree;          //释放Indegree数组
	}

	virtual Edge FirstEdge(int oneVertex)=0;  //返回与顶点oneVertex相关联的第一条边
    virtual Edge NextEdge(Edge preEdge)=0;    //返回与边PreEdge有相同关联顶点oneVertex的下一条边

    int VerticesNum()              //返回图的顶点个数
	{
		return numVertex;
	}

    int EdgesNum()                 //返回图的边数
	{
		return numEdge;
	}
    
    bool IsEdge(Edge oneEdge)      //如果oneEdge是边则返回TRUE，否则返回FALSE
	{
		if(oneEdge.weight>0&&oneEdge.weight<INFINITY&&oneEdge.to>=0) 
			return true;
		else 
			return false;
	}

	int FromVertex(Edge oneEdge)   //返回边oneEdge的始点
	{
		return oneEdge.from;
	}

	int ToVertex(Edge oneEdge)     //返回边oneEdge的终点
	{
		return oneEdge.to;
	}

	int Weight(Edge oneEdge)	   //返回边oneEdge的权
	{
		return oneEdge.weight;
	}
	virtual void setEdge(int from,int to,int weight)=0;
	virtual void delEdge(int from,int to)=0;
};


/**************** 相邻矩阵方式实现的图 ***************/
class Graphm: public Graph   
{
private:
	int **matrix;           //指向相邻矩阵的指针
	
public:
	
	Graphm(int numVert):Graph(numVert)    //构造函数
	{
		int i,j;                          //i,j仅仅作为for循环中的计数器		

		matrix=(int**)new int*[numVertex];     //申请matrix数组,该数组有numVertex个元素,每个元素是整型指针类型
		for(i=0;i<numVertex;i++)               //matrix数组的每个元素,都指向一个具有numVertex个元素的数组
			matrix[i] = new int[numVertex];
		for(i=0;i<numVertex;i++)               //相邻矩阵的所有元素都初始化为0,如果矩阵元素matrix[i][j]不为0,则表明顶点i与顶点j之间有一条边,边的权即为matrix[i][j]的值
			for(j=0;j<numVertex;j++)
				matrix[i][j]=0;
	}

	~Graphm()                        //析构函数
	{
		for(int i=0;i<numVertex;i++) //释放每个matrix[i]申请的空间
			delete [] matrix[i];
		delete [] matrix;            //释放matrix指针指向的空间
	}

	Edge FirstEdge(int oneVertex)    //返回顶点oneVertex的第一条边
	{
		Edge myEdge;                 //边myEdge将作为函数的返回值
		myEdge.from=oneVertex;       //将顶点oneVertex作为边myEdge的始点
		for(int i=0;i<numVertex;i++) //寻找第一个使得matrix[oneVertex][i]不为0的i值,那么(oneVertex,i)或者<oneVertex,i>即为顶点oneVertex的第一条边
		{
			if(matrix[oneVertex][i]!=0)
			{
				myEdge.to=i;         //将顶点i作为边myEdge的终点
				myEdge.weight=matrix[oneVertex][i];   //边myEdge的权为矩阵元素matrix[oneVertex][i]的值
				break;
			}			
		}
		return myEdge;               //如果找到了顶点oneVertex的第一条边,则返回的myEdge确实是一条边;如果没有找到顶点oneVertex的第一条边,则myEdge的成员变量to为-1,根据IsEdge函数判断可知myEdge不是一条边
	}

	Edge NextEdge(Edge preEdge)      //返回与边PreEdge有相同关联顶点oneVertex的下一条边
	{
		Edge myEdge;                 //边myEdge将作为函数的返回值
		myEdge.from=preEdge.from;    //将边myEdge的始点置为与上一条边preEdge的始点相同
	   
		for(int i=preEdge.to+1;i<numVertex;i++) //寻找下一个使得matrix[preEdge.from][i]不为0的i值,那么(preEdge.from,i)或者<preEdge.from,i>即为顶点preEdge.from的下一条边
		{
			if(matrix[preEdge.from][i]!=0)
			{
				myEdge.to=i;
				myEdge.weight=matrix[preEdge.from][i];
				break;
			}
		}
		
		return myEdge;                //如果找到了顶点preEdge.from的下一条边,则返回的myEdge确实是一条边;如果没有找到顶点preEdge.from的下一条边,则myEdge的成员变量to为-1,根据IsEdge函数判断可知myEdge不是一条边
	}

	void setEdge(int from,int to,int weight)      //为图设定一条边
	{
		if(matrix[from][to]==0)                   //如果matrix[from][to]==0，则边(from,to)或者<from,to>将是新增的一条边，否则该边已经存在（现在只是对该边进行修改）
		{
			numEdge++;
			Indegree[to]++;
		}
		matrix[from][to]=weight;  		      
	}

	void delEdge(int from,int to)               //删掉图的一条边
	{
		if(matrix[from][to]!=0)					//如果matrix[from][to]!=0，则边(from,to)或者<from,to>确实存在，否则该边实际上并不存在（从而不必对图的边数和顶点to的入度进行修改）
		{
			numEdge--;
			Indegree[to]--;
		}
		matrix[from][to]=0;		     
	}
};


/**************** 邻接表方式实现的图 ***************/
struct listUnit      //邻接表表目中数据部分的结构定义
{
	int vertex;      //边的终点
	int weight;      //边的权
};


class Graphl: public Graph                    
{
	friend class Graphdup;       //Graphdup是下面我们将讨论的邻接多重表的实现方式

private:
	LList<listUnit> *graList;    //graList是保存所有边表的数组
	
public:
	Graphl(int numVert):Graph(numVert)          //构造函数
	{
		graList=new LList<listUnit>[numVertex]; //为graList数组申请空间，图有numVertex个顶点，则有numVertex个边表
	}

	~Graphl()                                   //析构函数
	{
		delete [] graList;						//释放空间
	}
	
	Edge FirstEdge(int oneVertex)              //返回顶点oneVertex的第一条边
	{
		Edge myEdge;                           //边myEdge将作为函数的返回值
		myEdge.from=oneVertex;                 //将顶点oneVertex作为边myEdge的始点
		Link<listUnit> *temp=graList[oneVertex].head;  //graList[oneVertex].head保存的是顶点oneVertex的边表，temp->next指向顶点oneVertex的第一条边(如果temp->next不为null)
		if(temp->next!=NULL)                   //如果顶点oneVertex的第一条边确实存在
		{
			myEdge.to=temp->next->element.vertex;
			myEdge.weight=temp->next->element.weight;
		}
		return myEdge;	                      //如果找到了顶点oneVertex的第一条边,则返回的myEdge确实是一条边;如果没有找到顶点oneVertex的第一条边,则myEdge的成员变量to为-1,根据IsEdge函数判断可知myEdge不是一条边
	}
	
	Edge NextEdge(Edge preEdge)               //返回与边PreEdge有相同关联顶点oneVertex的下一条边
	{
		Edge myEdge;                          //边myEdge将作为函数的返回值
		myEdge.from=preEdge.from;             //将边myEdge的始点置为与上一条边preEdge的始点相同
		Link<listUnit> *temp=graList[preEdge.from].head;           //graList[oneVertex].head保存的是顶点oneVertex的边表，temp->next指向顶点oneVertex的第一条边(如果temp->next不为null)
		while(temp->next!=NULL&&temp->next->element.vertex<=preEdge.to)  //确定边preEdge在边表中的位置,如果边preEdge的下一条边确实存在，则temp->next指针指向下一条边的表目
			temp=temp->next;
		if(temp->next!=NULL)                 //边preEdge的下一条边存在			                                
		{
			myEdge.to=temp->next->element.vertex;
			myEdge.weight=temp->next->element.weight;			
		}
		return myEdge;
	}
	
	void setEdge(int from,int to,int weight)   //为图设定一条边
	{
		Link<listUnit> *temp=graList[from].head;  //graList[from].head保存的是顶点from的边表，temp->next指向顶点from的第一条边(如果temp->next不为null)
		while(temp->next!=NULL&&temp->next->element.vertex<to)   //确定边(from,to)或<from,to>在边表中的位置,如果不存在,则边(from,to)或<from,to>为新加的一条边
			temp=temp->next;
		if(temp->next==NULL)                //边(from,to)或<from,to>在边表中不存在且在边表中其后已无其它边,则在边表中加入这条边
		{
			temp->next=new Link<listUnit>;
			temp->next->element.vertex=to;
			temp->next->element.weight=weight;
			numEdge++;
			Indegree[to]++;
			return;
		}
		if(temp->next->element.vertex==to) //边(from,to)或<from,to>在边表中已存在,故只需要改变边的权值
		{
            temp->next->element.weight=weight;
			return;
		}
		if(temp->next->element.vertex>to) //边(from,to)或<from,to>在边表中不存在,但在边表中其后存在其它边,则在边表中插入这条边
		{
			Link<listUnit> *other=temp->next;
			temp->next=new Link<listUnit>;
			temp->next->element.vertex=to;
			temp->next->element.weight=weight;
			temp->next->next=other;
			numEdge++;
			Indegree[to]++;			
		}
	}

	void delEdge(int from,int to)      //删掉图的一条边
	{
		Link<listUnit> *temp=graList[from].head;      //graList[from].head保存的是顶点from的边表，temp->next指向顶点from的第一条边(如果temp->next不为null)
		while(temp->next!=NULL&&temp->next->element.vertex<to)   //确定边(from,to)或<from,to>在边表中的位置(如果该边存在)
			temp=temp->next;
		if(temp->next==NULL) return;   //边(from,to)或<from,to>在边表中不存在,则不需要做任何操作	
		if(temp->next->element.vertex==to)  //边(from,to)或<from,to>在边表中存在且确定了该边在边表中的位置,则从边表中将其删掉
		{
			Link<listUnit> *other=temp->next->next;
			delete temp->next;
			temp->next=other;
			numEdge--;
			Indegree[to]--;			
		}
	}
};


//算法部分:


//深度优先周游（从一个点开始周游）：
void DFS(Graph& G, int V)
{
	G.Mark[V]= VISITED;                           //标记该点
	cout<<V<<"\t";								  //打印
	for(Edge e=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))  //由该点所连的边进行深度优先周游
	{
	
		if(G.Mark[G.ToVertex(e)]==UNVISITED)               //访问V邻接到的未被访问过的顶点，并递归地按照深度优先的方式进行周游
			DFS(G, G.ToVertex(e));	
	}
}

//广度优先周游（从一个点开始周游）：
void BFS(Graph& G, int V)
{
	using std::queue;
	queue<int> Q;                   //初始化广度优先周游要用到的队列
	
	G.Mark[V]= VISITED;             //访问顶点V，并标记其标志位
	cout<<V<<"\t";                  //打印
	Q.push(V);                      //V入队
	
	while(!Q.empty())               //如果队列仍然有元素
	{
		int V=Q.front();		    //顶部元素
		Q.pop();                    //出队
	
		for(Edge e=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))    //将与该点相邻的每一个未访问点都入队
		{			
			if(G.Mark[G.ToVertex(e)]== UNVISITED)   //访问V邻接到的所有未被访问过的顶点
			{				
				G.Mark[G.ToVertex(e)]= VISITED;     //访问顶点V，并标记其标志位
	        	cout<<G.ToVertex(e)<<"\t";          //打印
				Q.push(G.ToVertex(e));              //入队				
			}			
		}
	}
}

//图周游：
void graph_traverse(Graph& G,bool useDFS)
{
	for(int i=0;i<G.VerticesNum();i++)  //对图所有顶点的标志位进行初始化
		G.Mark[i]=UNVISITED;
	for(i=0;i<G.VerticesNum();i++)      //检查图的所有顶点是否被标记过，如果未被标记，则从该未被标记的顶点开始继续周游
    {
		if(G.Mark[i]== UNVISITED)
		{
			if(useDFS)
				DFS(G,i);       //深度优先搜索
			else
				BFS(G,i);       //广度优先搜索
		}
	}
	cout<<endl;
}

//队列方式实现的拓扑排序
void TopsortbyQueue(Graph& G)                     
{
	for(int i=0;i<G.VerticesNum();i++)     //初始化Mark数组
		G.Mark[i]=UNVISITED;

    using std::queue;
	queue<int> Q;                          //初始化队列
	
	for(i=0; i<G.VerticesNum(); i++)       //图中入度为0的顶点入队
	{
		if(G.Indegree[i]==0)    
		{
			Q.push(i);                            
		}
	}

	while(!Q.empty())                 //如果队列中还有图的顶点
	{
		int V=Q.front();		
		cout<<V<<"\t";               //打印输出该顶点
		G.Mark[V]=VISITED;
		Q.pop();                     //一个顶点出队
			
		for(Edge e= G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))  //所有与之相邻的点入度-1
		{				
			G.Indegree[G.ToVertex(e)]--;   //边e的终点的入度值减1
			if(G.Indegree[G.ToVertex(e)]==0)
			{
				Q.push(G.ToVertex(e));    //入度为0的顶点入队				
			}
		}
	}
	
	cout<<endl;

	for(i=0; i<G.VerticesNum(); i++)
	{ 
      if(G.Mark[i]==UNVISITED)
	  {            
	    cout<<"此图有环！"<<endl;        //图有环
        break;
      }
	}            
}


void Do_topsort(Graph& G, int V,int *result,int& tag)    //深度优先搜索方式实现拓扑排序
{
	G.Mark[V]= VISITED;
	for(Edge e= G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))
    {		
		if(G.Mark[G.ToVertex(e)]== UNVISITED)            //访问V邻接到的所有未被访问过的顶点
			Do_topsort(G, G.ToVertex(e),result,tag);     //递归调用        
	}
	result[tag++]=V;
}

void TopsortbyDFS(Graph& G)               //深度优先搜索方式实现的拓扑排序,结果是颠倒的
{
	for(int i=0; i<G.VerticesNum(); i++)  //对图所有顶点的标志位进行初始化
		G.Mark[i]=UNVISITED;

	int *result=new int[G.VerticesNum()];
	int tag=0;
	for(i=0; i<G.VerticesNum(); i++)      //对图的所有顶点进行处理
		if(G.Mark[i]== UNVISITED)
			Do_topsort(G,i,result,tag);   //调用递归函数

	for(i=G.VerticesNum()-1;i>=0;i--)     //逆序输出
	{		
		cout<<result[i]<<"\t";
	}
	cout<<endl;
}

//Dijkstra算法