graph.cpp

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

//用最小堆的方法实现实现寻找离访问组距离最小的点的功能
//为利用minheap，定义特别的DijElem类
class DijElem
{
public:
	int vertex;
	int distance;
	
	DijElem(int v=-1,int d=INFINITY)
	{
		vertex=v;
		distance=d;
	}	

	bool operator<(const DijElem &ele) const
	{
		return distance<ele.distance;
	}

	bool operator>(const DijElem &ele) const
	{
		return distance>ele.distance;
	}

	bool operator==(const DijElem &ele) const
	{
		return distance==ele.distance;
	}
};

//D的初始值为D[s]=0, D[else]=INFINITY
void Dijkstra(Graph& G,int *D,int s)
{
	int v;
	for(int i=0;i<G.VerticesNum();i++)           //初始化Mark数组
		G.Mark[i]=UNVISITED;
	
	//用最小堆方式实现找距离最小的顶点
	DijElem *E=new DijElem[G.VerticesNum()];
	DijElem temp;
	temp.vertex=s;
	temp.distance=0;	
	E[0]=temp;
	minheap<DijElem> H(E,1,G.VerticesNum());

	for(i=0;i<G.VerticesNum();i++)
	{	    
		do
		{
			if(H.isempty())
				return;
			temp=H.removemin();
			v=temp.vertex;
		}while(G.Mark[v]==VISITED);
		

		if(D[v]==INFINITY)                       			
			break;
		G.Mark[v]=VISITED;                       //把该点加入已访问组
		cout<<v<<"\t";                           //输出
		for(Edge e=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e)) //刷新D中的值，因为v的加入，D的值需要改变，只要刷新与v相邻的点的值
		{			
			if(D[G.ToVertex(e)]>(D[v]+G.Weight(e)))
			{
				D[G.ToVertex(e)]=D[v]+G.Weight(e);	                
				temp.vertex=G.ToVertex(e);
				temp.distance=D[G.ToVertex(e)];
				H.insert(temp);
			}
		}
	}	
}

//每对顶点之间的最短距离，用Floyd算法实现
void Floyd(Graph& G,int **D)
{
	
	int i,j,v;                 //i,j是计数器，v记录相应顶点

	//初始化D数组
	for(i=0;i<G.VerticesNum();i++)
	{
		for(j=0;j<G.VerticesNum();j++)
		{
			if(i==j) 
				D[i][j]=0;
			else				
				D[i][j]=INFINITY;			
		}
	}
	
	//D=adj[0]，将边的值填入D数组
	for(v=0;v<G.VerticesNum();v++)
	{
		for(Edge e=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e))
		{			
			D[v][e.to]=G.Weight(e);			
		}
	}

	//如果两个顶点间的最短路径经过顶点v，则有D[i][j]>(D[i][v]+D[v][j])
	//通过对v的循环，相当于将图一个顶点一个顶点的扩大
	for(v=0;v<G.VerticesNum();v++)
		for(i=0;i<G.VerticesNum();i++)
			for(j=0;j<G.VerticesNum();j++)
				if(D[i][j]>(D[i][v]+D[v][j]))
					D[i][j]=D[i][v]+D[v][j];
	
	for(i=0;i<G.VerticesNum();i++)
	{
		for(j=0;j<G.VerticesNum();j++)
			cout<<D[i][j]<<"\t";
		cout<<endl;
	}
}


//最小支撑树的算法

//添加边
void AddEdgetoMST(int i,int j,Edge *MST,int tag)
{
	MST[tag].from=i;
	MST[tag].to=j;
}

//最小支撑树的Prim算法,寻找下一条权最小的边采用最小堆的方式
void Prim(Graph& G, int s)        
{	
	int MSTtag=0;                            //最小支撑树边的标号
	Edge *MST=new Edge[G.VerticesNum()-1];   //存储最小支撑树的边
	int Etag=0;
	Edge *E=new Edge[G.EdgesNum()];

	for(int i=0;i<G.VerticesNum();i++)       //初始化Mark数组
	{
		G.Mark[i]=UNVISITED;			                    
	}	
	G.Mark[s]=VISITED;

	for(Edge e=G.FirstEdge(s);G.IsEdge(e);e=G.NextEdge(e))
	{
		E[Etag++]=e;		
	}
	
	minheap<Edge> H(E,Etag,G.EdgesNum());

	for(i=1; i<G.VerticesNum(); i++)
	{
        //寻找权最小的边
		if(H.isempty())
		{
			cout<<"不存在最小支撑树！";
			return;
		}
		Edge temp=H.removemin();
		
		if(G.Mark[temp.to]==UNVISITED)
		{
			AddEdgetoMST(temp.from,temp.to,MST,MSTtag++);
			G.Mark[temp.to]=VISITED;
			for(e=G.FirstEdge(temp.to);G.IsEdge(e);e=G.NextEdge(e))
			{
				if(G.Mark[e.to]==VISITED)
					continue;				
				H.insert(e);
			}
		}
		else
			i--;
	}      	

	//输出
	for(i=0;i<G.VerticesNum()-1;i++)
		cout<<MST[i].from<<"-"<<MST[i].to<<"\t";
	cout<<endl;
}

//Kruskal算法
//用“父指针”法表示等价类的类
class Gentree
{
private:
	int* array;             //叶结点数组
	int size;               //叶结点的大小
public:
	Gentree(int sz)         //构造函数
	{
		size=sz;
		array=new int[sz];
		for(int i=0;i<sz;i++) 
			array[i]=ROOT;  //ROOT表示整个树的根结点
	}
	~Gentree()           //析构函数，释放空间
	{
		delete [] array;
	}
	int FIND(int curr)   //寻找根的函数
	{
		while(array[curr]!=ROOT)
			curr=array[curr];
		return curr;
	}

	void UNION(int a,int b)     //将a和b合并到一个等价类中，a和b在一个等价类中就是他们有相同的根
	{
		int root1=FIND(a);
		int root2=FIND(b);
		if(root1!=root2) 
			array[root2]=root1;
	}

	bool differ(int a,int b)    //判断a和b是否不等价
	{
		int root1=FIND(a);
		int root2=FIND(b);
		return root1!=root2;
	}
};

//最小支撑树的Kruskal算法
void Kruskal(Graph& G)       
{	
	Gentree A(G.VerticesNum());            //等价类
    Edge *E=new Edge[G.EdgesNum()];        //记录图的所有边
	Edge *MST=new Edge[G.VerticesNum()-1]; //最小支撑树
	int MSTtag=0;
	int edgecount=0;

    for(int i=0; i<G.VerticesNum(); i++)    //将图的所有边记录在数组E中
	{
		for(Edge e= G.FirstEdge(i);G.IsEdge(e);e=G.NextEdge(e))
		{			
			if(G.FromVertex(e)< G.ToVertex(e)) 
				E[edgecount++]=e;		
		}
	}
    
	edgecount--;                                    //得到图的边数
	minheap<Edge> H(E,edgecount,edgecount);        //最小堆（min-heap）
    
	int EquNum=G.VerticesNum();  //开始时有|V|个等价类
    for(i=0; EquNum>1;i++)      //合并等价类
	{
		Edge e=H.removemin();       //获得下一条权最小的边
		if(e.weight>=INFINITY)
		{
			cout<<"不存在最小支撑树."<<endl;
			return;
		}
        int from=G.FromVertex(e);   //记录该条边的信息
        int to= G.ToVertex(e);
        if(A.differ(from,to))       //如果边e的两个顶点不在一个等价类
		{
			A.UNION(from,to);       //将边e的两个顶点所在的两个等价类合并为一个
			AddEdgetoMST(from,to,MST,MSTtag++); //将边e加到MST
			EquNum--;             //将等价类的个数减1
		}
	}
	
	for(i=0;i<G.VerticesNum()-1;i++)
		cout<<MST[i].from<<"-"<<MST[i].to<<"\t";
	cout<<endl;
}


void main()
{
	//依用户的选择实现功能
	cout<<"——————第一步：构造图——————"<<endl;
	//获取构图方式
	cout<<"请选择构图方式："<<endl;
	cout<<"(1)相邻矩阵"<<endl;
	cout<<"(2)邻接表"<<endl;
	
	int choice;
	cout<<"你的选择是(例如，输入1，然后回车，即表示用相邻矩阵的构图方式)：";
	cin>>choice;
	if(choice>2||choice<1)
	{
		cout<<"错误的输入！"<<endl;
		return;
	}
	cout<<endl;

	int isDirected;                        //标记是否有向图
	int numVertex;                         //图的顶点个数（边数将在setEdge中被自动修改）
	int from,to,weight;                    //读入每条边的起点，终点和权
	ifstream GraphSou;                     //输入文件流
	//文件格式必须正确无误，否则无法工作
	cout<<"请输入构图文件（例如，输入a.txt，然后回车。请确保构图文件是正确的格式，可参见同目录下文件a.txt的格式及说明文件readme.txt）:";
	char filename[20];
	cin>>filename;                         //获取文件名
	
	GraphSou.open(filename);
	GraphSou>>isDirected;                  //是否有向
	if(isDirected!=1&&isDirected!=0)
	{
		cout<<"文件格式不正确，请重新输入。"<<endl;
		return;
	}

	GraphSou>>numVertex;                   //顶点个数
	Graph *myGra;                          //图本身
	if(choice==1)                          //相邻矩阵
		myGra=new Graphm(numVertex);
	else                                   //因为邻接多重表是通过邻接表来初始化的
		myGra=new Graphl(numVertex);
	
	while(!GraphSou.eof())                 //顺次读取边的信息
	{
		GraphSou>>from>>to>>weight;
		if(from>=0&&to>=0&&weight>0&&from<numVertex&&to<numVertex)
		{
			myGra->setEdge(from,to,weight);
			if(!isDirected)
				myGra->setEdge(to,from,weight);
		}
		else
		{
			cout<<"文件数据非法，请重新输入。"<<endl;
			return;
		}
	}	
	
	cout<<endl;
	//输出图的构造情况以便用户检查
	cout<<"**********你所构造的图具体情况如下：**********"<<endl;
	if(isDirected)
		cout<<"该图为有向图。"<<endl;
	else
		cout<<"该图为无向图。"<<endl;
	cout<<"顶点数——"<<myGra->VerticesNum()<<endl;
	cout<<"存在边如下——"<<endl;
	for(int i=0;i<myGra->VerticesNum();i++)
	{
		for(Edge e=myGra->FirstEdge(i);myGra->IsEdge(e);e=myGra->NextEdge(e))
		{			
			cout<<"始点："<<e.from<<" 终点："<<e.to<<" 权："<<e.weight<<endl;			
		}
		cout<<endl;
	}	
	
	//依据用户的选择来验证各种算法
	cout<<"——————第二步：验证图的算法——————"<<endl;
	cout<<"请选择要进行的操作（例如，输入1，然后回车，表示你选择进行“图的深度优先周游”，按除1-8之外的其它键则自动退出）:"<<endl;
	cout<<"(1)图的深度优先周游"<<endl;
	cout<<"(2)图的广度优先周游"<<endl;
	cout<<"(3)由队列方式实现的拓扑排序"<<endl;
	cout<<"(4)由深度优先搜索方式实现的拓扑排序"<<endl;
	cout<<"(5)单源最短路径(Dijkstra算法)"<<endl;
	cout<<"(6)每对顶点之间的最短路径(Floyd算法)"<<endl;
	cout<<"(7)最小支撑树(Prim算法)"<<endl;
	cout<<"(8)最小支撑树(Kruskal算法)"<<endl;	
	while(1)
	{		
		cout<<"你的选择是：";
		cin>>choice;
		if(choice==1)
			graph_traverse(*myGra,true);
		else if(choice==2)
			graph_traverse(*myGra,false);
		else if(choice==3)
		{
			if(!isDirected)
			{
				cout<<"此图是无向图，而拓扑排序算法适用于有向无环图！"<<endl;
				continue;
			}
			TopsortbyQueue(*myGra);
		}
		else if(choice==4)
		{
			if(!isDirected)
			{
				cout<<"此图是无向图，而拓扑排序算法适用于有向无环图！"<<endl;
				continue;
			}
			TopsortbyDFS(*myGra);
		}
		else if(choice==5)
		{
			int start;
			while(1)
			{
				cout<<"请选择源点(例如，输入0，然后回车，表示你选择以顶点0为源点)：";
				cin>>start;
				if(start<0||start>=myGra->VerticesNum())
					cout<<"输入非法。"<<endl;
				else break;
			}
			int *DforDijkstra=new int[myGra->VerticesNum()];
			for(i=0;i<myGra->VerticesNum();i++)
				DforDijkstra[i]=INFINITY;
			DforDijkstra[start]=0;
			Dijkstra(*myGra,DforDijkstra,start);
			cout<<endl;
			for(i=0;i<myGra->VerticesNum();i++)
				cout<<start<<"，"<<i<<"="<<DforDijkstra[i]<<endl;
		}
		else if(choice==6)
		{
			int **DforFloyd=(int **)new int*[myGra->VerticesNum()];
			for(i=0;i<myGra->VerticesNum();i++)
				DforFloyd[i]=new int[myGra->VerticesNum()];
			Floyd(*myGra,DforFloyd);
		}
		else if(choice==7)
		{
			if(isDirected)
			{
				cout<<"此图是有向图，而最小支撑树的Prim算法适用于连通无向图！"<<endl;
				continue;
			}
			int start;
			while(1)
			{
				cout<<"请选择起始点(例如，输入0，然后回车，表示你选择以顶点0为始点)：";
				cin>>start;
				if(start<0||start>=myGra->VerticesNum())
					cout<<"输入非法。"<<endl;
				else break;
			}
			Prim(*myGra,start);
		}
		else if(choice==8)
		{		
			if(isDirected)
			{
				cout<<"此图是有向图，而最小支撑树的Kruskal算法适用于连通无向图！"<<endl;
				continue;
			}
			Kruskal(*myGra);
		}
		else 
			return;
		cout<<endl;
	}
}