tuopu.cpp

拓扑排序：对给定的AOV网判断网中是否存在环

#include<iostream.h>
#include<iomanip.h>
#define exit 0 ;
#define MAX_VERTEX_NUM 20
typedef int InfoType  ;
typedef struct ArcNode {                         //表结点
  int       adjvex;                              // 该弧所指向的顶点的位置
  struct ArcNode *nextarc;                       // 指向下一条弧指针
  //InfoType  info;                                // 该弧相关信息的指针
} ArcNode;
typedef char VertexType ;
typedef struct VNode {                           //头结点
 VertexType  data;                               // 顶点信息
 int indegree;
  ArcNode  *firstarc;                            // 指向第一条依附该顶点的弧
  } VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { 
    AdjList  vertices;
    int  vexnum,arcnum;                          //图的当前顶点数和弧数
}ALGraph;
typedef  int SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack &S)                     //构造一个空栈
{ 
	S.base=new SElemType[MAX_VERTEX_NUM];
	if(!S.base) exit(1);
	S.top=S.base;
	S.stacksize=MAX_VERTEX_NUM;
}
void Push(SqStack &S,SElemType e)              //插入元素e为新的栈顶元素
{
	if(S.top-S.base>=S.stacksize)
	exit(1);                                   //栈满，跳出
	*S.top++=e;
}
SElemType Pop(SqStack &S,SElemType &e)
{                                              //若栈不空，则删除S的栈顶元素，用e返回其值，并返回元素e
if(S.top==S.base)exit(1);
    e=*--S.top;
return e;
} 
void CreateGraph (ALGraph &G) {
int head,tail;
//InfoType weight;
cout<<"输入顶点数和边数"<<endl;
    cin >> G.vexnum >> G.arcnum;                //输入顶点数和边数
	cout<<"输入各顶点的信息"<<endl;
    for ( int i = 0; i < G.vexnum; i++) { 
		//cout<<"输入顶点"<<i<<"的信息"<<endl;
        cin >> G. vertices[i].data;             //输入顶点信息
        G. vertices[i].firstarc = NULL;
    }
	cout<<"**************逐条边输入各边的信息**************"<<endl;
    for ( i = 0; i < G.arcnum; i++) {           //逐条边输入
	
	   cout<<"请输入第 "<<i+1<<"条边的尾结点"<<'\t'<<"头结点"/*<<'\t'<<"权值"*/<<endl;
        cin >> tail >> head /*>> weight*/;
        ArcNode * p = new ArcNode;

		p->adjvex = head; 
	//	p=G. vertices[tail].firstarc;
		
	//	p=p->nextarc;
	   // q=p->nextarc;
        // p=q;
	//	p->info = weight; 
       p->nextarc = G. vertices[tail].firstarc; //链入第 tail 号链表的前端
       G. vertices[tail].firstarc = p;
     }


}
void FindInDegree (ALGraph &G/*,int indegree*/)
{
ArcNode *p;
int i,k;
for(i=0;i<G.vexnum;i++)
G.vertices[i].indegree=0;
for( i=0;i<G.vexnum;i++)
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
     //if(p)
	 {
//	k=G.vertices[i].firstarc->adjvex;
	k=p->adjvex;
//	cout<<"*******"<<endl;
	G.vertices[k].indegree=G.vertices[k].indegree+1;
}
for(i=0;i<G.vexnum;i++)
cout<<G.vertices[i].indegree<<'\t';
cout<<endl;
//return G.vertices[k].indegree;
}
void TopologicalSort(ALGraph G)
{
int i,count,k;
ArcNode *p;
SqStack S;
FindInDegree (G/*,indegree*/);
for(i=0;i<G.vexnum;i++)
cout<<G.vertices[i].indegree<<'\t';
cout<<endl;
InitStack(S);
for(i=0;i<G.vexnum;++i)
     if(G.vertices[i].indegree==0)
          Push(S,i);
count=0;
while(S.top!=S.base)
{
Pop(S,i);
cout<<i<<'\t'<<G.vertices[i].data<<endl;
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if((--G.vertices[k].indegree)==0)Push(S,k);
}
}
if(count<G.vexnum)cout<<"该有向图有回路"<<endl;
else cout<<"该有向图无回路"<<endl;
}
void main()
{
ALGraph G;
CreateGraph (G);
 FindInDegree (G/*,int indegree*/);
TopologicalSort(G);
}