#include<stdio.h>
#include<stdlib.h>
#define MAX_VEXTEX_NUM 20   //最大頂點個數#define M 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define M 20
#define ERROR 0
typedef int ElemType;
typedef struct ArcNode       //定義表結點結構
{
int adjvex;               //與vi相鄰接的頂點編號
struct ArcNode *nextarc;    //指向下一條弧(邊)的指針
}ArcNode;
typedef struct VNode       //定義表頭結點結構
{
int data;
ArcNode *firstarc;       //指向第一條弧（邊）的指針
}VNode,AdjList[MAX_VEXTEX_NUM];
typedef struct            //定義鄰接表結構
{
AdjList vertices;        //表頭結點數組
int vexnum, arcnum;     //頂點和弧（邊）的個數
}ALGraph;
typedef struct //構件棧
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack *);               //函數聲明
int Pop(SqStack *, ElemType *);
void Push(SqStack *,ElemType );
int StackEmpty(SqStack *);
void CreatGraph(ALGraph *);
void FindInDegree(ALGraph , int * );
void TopologicalSort(ALGraph );
void InitStack(SqStack *S)//初始化棧
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
int Pop(SqStack *S,ElemType *e)//出棧操作
{
if(S->top==S->base)
{
return ERROR;
}
*e=*--S->top;
return 0;
}
void Push(SqStack *S,ElemType e)//進棧操作
{
if(S->top-S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top = S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
}
int StackEmpty(SqStack *S)//判斷棧是否為空
{
if(S->top==S->base)
return OK;
else
return ERROR;
}
void CreatGraph(ALGraph *G)//構件圖
{
int m, n, i;
ArcNode *p;
printf("請輸入頂點數和邊數:");
scanf("%d%d",&G->vexnum,&G->arcnum);
for (i = 1; i <= G->vexnum; i++)
{
G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
for (i = 1; i <= G->arcnum; i++)       //輸入存在邊的點集合
{
printf("\n請輸入存在邊的兩個頂點的序號:");
scanf("%d%d",&n,&m);
while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
{
printf("輸入的頂點序號不正確 請重新輸入:");
scanf("%d%d",&n,&m);
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (p == NULL)
{
printf("memory allocation failed,goodbey");
exit(1);
}
p->adjvex = m;
p->nextarc = G->vertices[n].firstarc;
G->vertices[n].firstarc = p;
}

}
void FindInDegree(ALGraph G, int indegree[])
{
int i;
for (i = 1; i <= G.vexnum; i++)
{
indegree[i] = 0;
}
for (i = 1; i <= G.vexnum; i++)
{
while (G.vertices[i].firstarc)
{
indegree[G.vertices[i].firstarc->adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
}
}
}
void TopologicalSort(ALGraph G)       //進行拓撲排序
{
int indegree[M];
int i, k, n;
int count = 0;
ArcNode *p;
SqStack S;
FindInDegree(G, indegree);
InitStack(&S);

for ( i = 1; i <= G.vexnum; i++)
{
if (!indegree[i])
Push(&S,i);
}
printf("進行拓撲排序輸出順序為:");         //輸出結果
while(!StackEmpty(&S))
{
Pop(&S,&n);
printf("%4d",G.vertices[n].data);
count++;
for (p = G.vertices[n].firstarc;  p != NULL;  p = p->nextarc)
{
k = p->adjvex;
if (!(--indegree[k]))
{
Push(&S,k);
}
}
}
printf("\n");
if (count < G.vexnum)
{
printf("該有向圖有回路");
}
else
{
printf("排序成功\n");
}
}
int main(void)            //主函數
{
ALGraph G;
CreatGraph(&G);
TopologicalSort(G);
system("pause");
return 0;}