tupo.cpp

拓扑排序的源程序。本程序可以对给定的一组数据进行拓扑排序。

#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#define MAX 100
int arcs[MAX][MAX];//邻接矩阵中有从i到j的有向边,用1表示;否则用0表示
int color[MAX];//记录第i个顶点的颜色,未被访问为白色(0),第一次被访问为灰色(1),第二次被访问为黑色(2)
int tuopu[MAX];//拓扑排序的逆序列
int m=0;//记录中元素的个数

void creat(int n)//生成一个有向图
{
	for(int i=0;i<n;i++)
	{
	    for(int j=0;j<n;j++)
		{
			arcs[i][j]=0;
			if(i!=j) 
			{
				if(arcs[i][j]!=1&&arcs[j][i]!=1)
				{
				   //srand((unsigned)time(NULL));//随时间的不同产生不同的随机数
			       arcs[i][j]=rand()%100;
		           if(arcs[i][j]>50)
				      arcs[i][j]=0;
		           else
				      arcs[i][j]=1;
				}
			}

		}
	}
}

void Dfst(int i,int n)//对i结点深度非递归遍历，产生拓扑序列
{
    int s[MAX];
	int top=0;
	color[i]=1; //记录第i结点第一次被访问,颜色由白色变为黑色(1)
	s[top++]=i;
	
	        for(int j=0;j<n;j++)
			{
			  if(arcs[i][j]==1)
			  {
			     if(color[j]==0)//当j结点满足，有从i到j的有向边且j没有被访问过，则深度访问j结点
				 {
				   color[j]=1;
                   s[top++]=j;
				 }
			     else if(color[j]==1)//判断有环路时退出程序
				  {
			       cout<<"there is a circle"<<endl;
				   cout<<j<<"->";
			       //tuopu[m++]=j;
		           return;
				  }
			  }  
			   while(top>0)
			   {
			     int t=s[top-1];
			     color[t]=2;//记录第i结点第二次被访问,颜色灰色变为黑色(2)
				 cout<<t<<"->";
			     //tuopu[m++]=t;
			     top--;  
			   }		
			}	
}

void Dfs(int i,int n,int flag)	//对i结点深度递归遍历，产生拓扑序列
{

    if(flag==1) return;//当有环路时退出
	color[i]=1;//记录第i结点第一次被访问,颜色由白色变为黑色(1)
	for(int j=0;j<n;j++)
	{
		if(arcs[i][j]==1)
		{
		 if(color[j]==0)//当j结点满足，有从i到j的有向边且j没有被访问过，则深度访问j结点
		 {
				Dfs(j,n,flag);
		 }
		 else if(color[j]==1)//判断有环路时退出程序
		 {
			cout<<"there is a circle"<<endl;
			tuopu[m++]=j;
		    flag=1;
		 }
		}
	} 
	color[i]=2;//记录第i结点第二次被访问,颜色灰色变为黑色(2)
	tuopu[m++]=i;
}

void Tuopu(int n)//拓扑排序
{
	for(int i=0;i<n;i++)
	{
		color[i]=0;
	}
    int flag=0;
	int count=0;
	for( i=0;i<n;i++)
	{
		if(color[i]==0)
		{   
		  Dfs(i,n,flag);
		  //Dfst(i, n);
		}
	}
}

void main()
{
	int n=4;
	creat(n);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			cout<<arcs[i][j]<<" ";
		cout<<endl;
	}

	Tuopu(n);//拓扑排序

   for(i=m-1;i>=0;i--)
	{
		cout<<tuopu[i];
		if(i!=0)
			cout<<"->";
	}
}