topologicalsort.cpp

数据结构的拓扑排序算法

// TopologicalSort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "TopologicalSort.h"
#include "Stack.h"
int main(int argc, char* argv[])
{	int i,t;
	char c;
	int indegree[128];
	ArcNode *p,*q;
	ALGraph G;
	cout<<"\t\t TopologicalSort Arithmetic"<<endl;
	cout<<"Please Input data to Create the Graph for Adjacency List"<<endl;
	cout<<"First, Input the vexnum(that is the total number of data. For exp:5 ):";
	cin>>G.vexnum;
	//cout<<"Input data:"<<endl;
	for(i=0;i<G.vexnum;i++)
	{indegree[i]=0;
	cout<<"Input data info for the VNode,AdjList["<<i<<"] :\t";
	cin>>G.vertices[i].data;
	G.vertices[i].firstarc=NULL;
	}
	for(i=0;i<G.vexnum;i++)
    {//
	 cout<<"Input ArcNode Info for row \"V"<<i<<"\",yes(Y) or no?"<<"Your Choose:  ";
	 cin>>c;
     if(c=='Y'||c=='y')
	 {cout<<"  Input which num for G.vertices["<<i<<"].firstarc :\t";
	  cin>>t;
	  while(t==(i+1)&&t>=G.vexnum)
	  {  cout<<"\t\tError Inputing! the arcnode doesn't exist  ";
		  cin>>t;
	  }
	  indegree[t]++;
	  p=(ArcNode *)malloc (sizeof(ArcNode));
	  p->adjvex=t;
	  p->nextarc=NULL;
      G.vertices[i].firstarc=p;
	  
	 cout<<"Next ArcNode Info for row \"V"<<i<<"\",yes(Y) or no?"<<" Your Choose:  ";
	 cin>>c;
     while(c=='Y'||c=='y')
	 {
	  cout<<"  Input which num for nextarc :"<<"\t";
	  cin>>t;
	  indegree[t]++;
	  q=(ArcNode *)malloc (sizeof(ArcNode));
	  q->adjvex=t;
	  q->nextarc=NULL;
      p->nextarc=q;
	  p=q;
	  cout<<"Next ArcNode Info for row (V"<<i<<"),yes(Y) or no?"<<"Your Choose:  ";
	  cin>>c;
	 }
	  cout<<endl;
	 }
	}	 //Initialize G

cout<<"===============The Graph in Adjacency List initialized============="<<endl;
for(i=0;i<G.vexnum;i++)
{cout<<"\t\"V"<<i<<"\"  Firstarc: Data(";
 cout<<G.vertices[i].data<<")===>";
 p=G.vertices[i].firstarc;
 cout<<"\t"<<"ArcNode: ";
 while(p!=NULL){
	cout<<p->adjvex<<"===>"; 
	p=p->nextarc;
 }
 cout<<"NULL"<<endl;
}//check G initialization
cout<<"==================================================================="<<endl;


for(i=0;i<G.vexnum;i++)
{cout<<"indegree["<<i<<"]: "<<indegree[i]<<"\t";
if (i%4==0&&i!=0) cout<<endl;} // check indegree
cout<<endl;

cout<<"==================The Output Topological Serial (num,data)========="<<endl;
cout<<"\t\t  ";
SqStack S; 
int k;
InitStack(S);
for(i=0;i<G.vexnum;i++)
{ if(!indegree[i])	Push(S,i);}
 int count=0;
while(!StackEmpty(S))
{Pop(S,i);

cout<<"("<<i<<","<<G.vertices[i].data<<")    ";
if(count%3==0&&count!=0) cout<<endl;
++count;
  for(p=G.vertices[i].firstarc;p;p=p->nextarc)
  {k=p->adjvex;
    if(!(--indegree[k])) Push(S,k);
  }//for
}//while
cout<<endl;
cout<<"==================================================================="<<endl;



	return 0;
}//Topological main