/*借助队列实现图的拓扑排序C程序*/
#include<stdlib.h>
#define maxvertexnum 20/*定义最多的顶点数*/
#define null 0
#define maxqueue 20
#define m 10 /*定义最多入度数*/
/*图的邻接表的边表结点*/
typedef struct node
{
int adjvex;/*存放邻接点序号*/
/*若要表示边上的权，可添加一个数据域*/
struct node *next;
}edgenode;
/*图的邻接表表示的顶点表结点*/
typedef struct vnode
{
int vertex;/*顶点数据域*/
edgenode *firstedge;/*边表头指针*/
}vertexnode;
/*用向量定义图的邻接表表示的顶点表*/
typedef vertexnode adjlist[maxvertexnum];
/*定义图的邻接表*/
typedef struct
{
adjlist adjlist;/*邻接表*/
int n;/*顶点数*/
int e;/*边数*/
}algraph;
int queue[maxqueue];/*队列的数组声明*/
int front=-1;/*队头*/
int rear=-1;/*队尾*/
/*建立有向图g的邻接表*/
void createalgraph(algraph *g)
{
int i,j,k,r;
edgenode *s;
printf("\ncreat_digraph:\n");
printf("input n,e.\n");
scanf("%d,%d",&g->n,&g->e);/*输入图g的顶点数和边数*/
printf("input nodes(after input a node then enter 'Enter'):\n");
for(i=1;i<=g->n;i++) /*构造一个只含n个顶点，边数为0的图*/
{
scanf("%d",&(g->adjlist.vertex)); /*读入顶点信息*/
g->adjlist.firstedge=null; /*将顶点结点的firstedge域置为空*/
}
for(k=1;k<=g->e;k++) /*建立边表*/
{
printf("input i,j(1~n):\n");
scanf("%d,%d",&i,&j); /*读入边（vi，vj）的顶点对序号*/
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=j;/*将序号j放入边结点*s的邻接点序号adjvex域*/
s->next=g->adjlist.firstedge;
/*将边结点*s作为第一个邻接点插入到序号为i的顶点的边表中*/
g->adjlist.firstedge=s;
}
}
/*打印邻接表*/
void print(adjlist g,int n)
{
edgenode *q;
int i;
printf("\nPrint out the linjiebiao of graph:\n");
for(i=1;i<=n;i++)
{
printf("%d->",g.vertex);/*输出头结点数组的数据*/
while(q!=null)
{
printf("%d-",q->adjvex);/*输出边表的数据*/
q=q->next;
}
printf("\n");
}
}
/*图的拓扑排序(队列)*/
int toposort(adjlist g,int n)
{
edgenode *r;
int i;
for(i=1;i<=n;i++)
if(r->indegree==0)
enqueue(i);
while((i=dequeue())!=-1)
{
printf(" %d ",i); *输出入度为零的顶点*
g=r->next;
while(g!=null)
{
i=r->indegree;
r->indegree--;
if(r->indegree==0)
enqueue(i);
g=g->next;