拓扑排序C语言代码

#include
#include
#include
#include

//----------------公共的-----------------
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//---------------------------------------

//*************栈的初始大小和增量***************
#define STACK_INIT_SIZE 100
#define STATCKINCREMENT 10
//**********************************************

//*************栈的元素类型***************
typedef int SElemType;
typedef struct SqStack
{
SElemType *base;
SElemType *top;
SElemType stacksize;
}SqStack;
//****************************************

#define MAX_VERTEX_NUM 20
#define MAX 20

typedef int Boolean;

typedef int Status;

typedef char InfoType;
typedef struct ArcNode{ //邻接表的弧
int adjvex; //该弧所指向的顶点的位置
InfoType *info; //该弧相关信息的指针（如:权值等）
struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode;

typedef int VertexType;//每个顶点的值的类型
typedef struct VNode//邻接表的顶点
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{
AdjList vertices; //邻接表
int vexnum,arcnum;//图的当前顶点数和弧数
int kind; //图的种类标志 0为无向图 1为有向图
}ALGraph;

//****************栈的使用函数*********************
int InitStack(SqStack &s){//栈的初始化
s.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!s.base)
{
return 0; //存储分配失败
}
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return 1;
}

int Push(SqStack &s,SElemType e){ //元素的入栈
if(s.top-s.base>=s.stacksize)//栈满，追加存储控件
{
s.base=(SElemType *)realloc(s.base,(s.stacksize+STATCKINCREMENT)*sizeof(SElemType));
if(!s.base) return 0;//存储分配失败
s.top=s.base+s.stacksize;
s.stacksize+=STATCKINCREMENT;
}
*(s.top)++=e;
return 1;
}

int Pop(SqStack &s,SElemType &e){//元素的出栈
if(s.top==s.base) return 0;
e=*--s.top;
return 1;
}

int StackEmpty(SqStack s){//若S为为空战，则返回1，否则返回0
if(s.top==s.base) return 1;
else return 0;
}
//*************************************************

Status CreateDG(ALGraph &g){ /* 邻接表建立有向图 */
int i,j,k;
ArcNode *p;
printf("请输入顶点数和边数（格式为:顶点数,边数）：");
scanf("%d,%d",&i,&j);
getchar();
g.vexnum=i;g.arcnum=j;
for(i=1;i<=g.vexnum;i++)//输入顶点
{
printf("请输入第%d个顶点的值：",i);
scanf("%d",&g.vertices[i].data);
getchar();
g.vertices[i].firstarc=NULL;
}

printf("输入边的信息（输入格式为：i,j）\n");
for(i=1;i<=g.arcnum;i++) /* 输入弧的信息 */
{
printf("请输入第%d条边的信息：",i);
scanf("%d,%d",&j,&k);
getchar();
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=k;
p->nextarc=g.

vertices[j].firstarc;
g.vertices[j].firstarc=p;
}
return OK;
}

int FirstAdjVex(ALGraph g,int v){
//获取邻接表g的第v个顶点的第一个邻接点
//返回第v个顶点的第一个邻接点的位置
if(g.vertices[v].firstarc!=NULL)
return g.vertices[v].firstarc->adjvex;
return -1;
}

int NextAdjVex(ALGraph g,int v,int w){
//w是邻接表g的第v个顶点的众多邻接点其中的一个
//返回相对于w的下一个邻接点的位置
ArcNode *p;
for(p=g.vertices[v].firstarc;p!=NULL;p=p->nextarc)
if(p->adjvex==w && p->nextarc!=NULL)
return p->nextarc->adjvex;
return -1;
}

void FindInDegree(ALGraph g,int indegree[MAX]){//找出图g的入度数组
ArcNode *p;
int i;int j;
for(i=1;i<=g.vexnum;i++)
{
j=0;
p=g.vertices[i].firstarc;
while(p)
{
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}

Status TopologicalSort(ALGraph g){
//有向图G采用的临界表存储结构
//若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR
int i;int count;int k;
ArcNode *p;
int indegree[MAX]={0};SqStack s;
FindInDegree(g,indegree);//对各个顶点求入度indegree[1..vexnum]
InitStack(s);
for(i=1;i<=g.vexnum;i++) //建零入度顶点栈S
if(!indegree[i]) Push(s,i);//入度为零者进栈
count=0; //对输出顶点计数
while(!StackEmpty(s)){
Pop(s,i);
printf("%d ",g.vertices[i].data);++count;//输出i号顶点并计数
for(p=g.vertices[i].firstarc;p;p=p->nextarc){
k=p->adjvex; //对i号顶点的每个邻接点入度减1
if(!(--indegree[k])) Push(s,k);
}//for
}//while
printf("\n");
if(countelse return OK;
}
void main()
{
ALGraph g;int indegree[MAX]={0};
CreateDG(g);
printf("其中一条有效的拓扑排序为：");
TopologicalSort(g);
system("pause");
}