topological_sorting.cpp

图的基类以及最短路径算法

// 图的相邻矩阵表示存储图，实现图的拓扑排序
#include <iostream.h>
#include <queue>
#include "Graphm.h"

int topolist[N];
int le[N],ee[N];
// 函数功能：显示排序后的序列
void Visit(Graph &G, int v) {
	cout << "C" << v << " ";
}

//***************************************************************
//[算法7.7] 队列实现的图拓扑排序
void TopsortbyQueue(Graph& G)  {      //队列方式实现的拓扑排序
	int count=0;
	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++)
		if(G.Indegree[i]==0)
			Q.push(i);                //图中入度为0的顶点入队
		while(!Q.empty())  {              //如果队列中还有图的顶点
			int V=Q.front();
			Q.pop();                     //一个顶点出队
			topolist[count]=V;           //写入数组
			count++;
			G.Mark[V]=VISITED;
			for(Edge e= G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))  {
				G.Indegree[G.ToVertex(e)]--;  //所有与之相邻的顶点入度-1
				if(G.Indegree[G.ToVertex(e)]==0)
					Q.push(G.ToVertex(e));   //入度为0的顶点入队
			}
		}
}


int A[N][N] =  {
	//C0  C1  C2  C3  C4  C5  C6  C7  C8	
		0,  0,  1,  0,  0,  0,  0,  1,  0, 
		0,  0,  1,  1,  1,  0,  0,  0,  0, 
		0,  0,  0,  1,  0,  0,  0,  0,  0,  
		0,  0,  0,  0,  0,  1,  1,  0,  0,  
		0,  0,  0,  0,  0,  1,  0,  0,  0,  
		0,  0,  0,  0,  0,  0,  0,  0,  0,  
		0,  0,  0,  0,  0,  0,  0,  0,  0,  
		0,  0,  0,  0,  0,  0,  0,  0,  1,  
		0,  0,  0,  0,  0,  0,  1,  0,  0};  //该图为图7.18表示课程优先关系的有向无环图
	
	void main()
	{
		int i;
		memset(ee,0,sizeof(ee));
		for(i=0;i<N;i++)
		{
			le[i]=99999;
		}
		Graphm aGraphm(N);              // 建立图
		aGraphm.IniGraphm(&aGraphm, A); // 初始化图
		cout << "Top sort by Queue is : ";
		TopsortbyQueue(aGraphm);
		for(i=0;i<N;i++)
		{
			cout<<"C"<<topolist[i]<<" ";
		}
		cout<<endl;
		//求le和ee
		int j;
		for(j=0;j<N;j++)
		{
			int temp=0;
			ee[0]=0;
			for(i=0;i<N;i++)
			{
				if(ee[i]+A[i][j]>=temp)
					temp=ee[i]+A[i][j];
			}
			ee[j]=temp;
		}
		le[N-1]=ee[N-1];
		for(j=N-2;j>=0;j--)
		{
			int temp1=999999;
			for(i=0;i<N;i++)
			{
				if(le[i]-A[i][j]<=temp1)
					temp1=le[i]-A[i][j];
			}
			le[j]=temp1;
		}
		cout<<"最短时间：";
		for(i=0;i<N;i++)
		{
			cout<<ee[i]<<" ";
		}
		cout<<endl;
		cout<<"最长时间：";
		for(i=0;i<N;i++)
		{
			cout<<le[i]<<" ";
		}
	}