toplogical sort.cpp

这是一个图的拓扑排序的程序

#include<iostream>
#include<iomanip>
using namespace std;

//函数结果状态代码 
# define TRUE 1 
# define FALSE 0 
# define OK 1 
# define ERROR 0 
# define INFEASIBLE -1 
# define OVERFLOW -2
#define MAX_VERTEX_NUM 20 //最大顶点数
//用于拓扑排序的图的邻接表的定义
typedef int Status;
typedef char VertexType;
typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
	int info;
}ArcNode;
typedef struct VNode{
	VertexType data;
	int indegree;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
	AdjList vertices;
	int vexnum,arcnum;}ALGraph;

//建立邻接表
//定位顶点的函数
int LocateVex(ALGraph G,char u)
    {
	int i;
	for (i=0;i<MAX_VERTEX_NUM;++i)
           { if(G.vertices[i].data==u) return i; }
	if (i==G.vexnum) {cin>>"Error u!";exit(1);}
	return -1;
    }
//建立有向图的邻接表的函数
void CreateALGraph_adjlist(ALGraph &G)
    {	int i,j,k,w;  char v1,v2;
	ArcNode *p;
	cout<<"Input vexnum & arcnum:";
	cin>>G.vexnum>>G.arcnum;
	cout<<"Input Vertices:"<<endl; 
	cout<<"Input value of note,a string of char:";
	for (i=0;i<G.vexnum;i++)
            {	cin>>G.vertices[i].data;
		         G.vertices[i].firstarc=NULL;
				 G.vertices[i].indegree=0;
             }
  cout<<"Input Arcs(v1,v2 & w):"<<endl;
  for (k=0;k<G.arcnum;++k)
  { cin>>v1>>v2>>w;
	i=LocateVex(G,v1);
	j=LocateVex(G,v2);
	p=(ArcNode*)malloc(sizeof(ArcNode));
	p->adjvex=j;	
	p->info = w;
	p->nextarc=G.vertices[i].firstarc;
	G.vertices[i].firstarc=p;
	G.vertices[j].indegree++;
  }	return;
}

//拓扑排序算法
Status ToplogicalSort(ALGraph G){
	ArcNode *p;
	int k;
//	FindIndegree(G,indegree);
	int top=-1; //入度为零的顶点栈初始化
	for (int i=0;i<G.vexnum;++i)
		if (G.vertices[i].indegree==0){
			G.vertices[i].indegree=top;
			top=i; //入度为零顶点进栈
		}
	int count=0;
while (top+1)
 { i=top;	top=G.vertices[top].indegree;
    cout<<setw(2)<<G.vertices[i].data;
   ++count;
  for (p=G.vertices[i].firstarc;p;p=p->nextarc)
   {//扫描该顶点的出边表
      k=p->adjvex; //边的另一顶点
      G.vertices[k].indegree--; //顶点入度减1
     if (G.vertices[k].indegree==0)
         {G.vertices[k].indegree=top;
	  top=k;}//入度为0入栈
	}
    }
if (count<G.vexnum) return ERROR;//有向环
	else return OK;
}


void main(){
ALGraph G;
cout<<"下面开始建立图的邻接表!"<<endl;
CreateALGraph_adjlist(G);
cout<<"下面是该图的拓扑排序!"<<endl;
ToplogicalSort(G);
cout<<endl;
}