最小生成树.cpp

KRUSAL算法实现最小生成数的 最小生成数的 最小生成数的

	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算法

//用最小堆的方法实现实现寻找离访问组距离最小的点的功能
//为利用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;
			Kruskal(*myGra);
	
}