topologicalsort.cpp

关于拓扑排序的算法

 /*拓扑排序*/
#include <stdio.h>
#include <malloc.h>
    #define M 10
    #define MAXVEX 10
    typedef char VertexType;
    
 struct edgenode
{   int vex;    /*邻接点序号*/
    struct edgenode *next;   /*指向下一条弧的指针*/
};
 struct tnode
{   int vexdata;    /*顶点信息*/
    int in;
    struct edgenode *link;     /*指向第一条依附该顶点的弧的指针*/
}; 
typedef struct tnode adjlist[MAXVEX];
    void creagraph(adjlist g,int *n)   /*建立有向图的邻接表*/
    {
      int e,i,s,d;
      struct edgenode *p;
      printf("顶点数(n),弧数(e):");
      scanf("%d,%d",n,&e);
      for (i=1;i<=*n;i++)
      {
	getchar();
	printf("  第%d个顶点信息:",i);
	scanf("%d",&g[i].vexdata);
	g[i].link=NULL;
      }
      for (i=1;i<=*n;i++)       /*初始化，使各顶点入度为"0"*/
      {
		  g[i].in=0;
	  }
      for (i=1;i<=e;i++)
      {
	printf("第%d条弧=>起点序号,终点序号:",i);
	scanf("%d,%d",&s,&d);
	p=(struct edgenode *)malloc(sizeof(struct edgenode));	
	p->vex=d;
	g[d].in++;
	p->next=g[s].link;  /*p插入顶点s的邻接表中*/
	g[s].link=p;
      }
    }
void toposort(adjlist g,int n)        /*拓扑排序*/
{  int top,m,k,j,s[M];     /*建立“0”入度顶点栈s*/
   edgenode *p;
   top=0; m=0;
   for(j=1;j<=n;j++)
     if(g[j].in==0)
       s[top++]=j;       /*入度为“0”者进栈*/
   while(top>0)
   {  j=s[--top];
      printf("%d  ",g[j].vexdata);
      m++;          /*对输出顶点计数*/
      p=g[j].link;
      while(p!=NULL)   /*对j号顶点的每个邻接点的入度减1*/
      {  k=p->vex;   
	 g[k].in--;
	 if(g[k].in==0)
	    s[top++]=k;      /*若入度减为0，则入栈*/
	 p=p->next;
      }
   }
   printf("\nm=%d\n",m);
   if(m<n)  printf("The network has a cycle\n");
}
main()
   {
      adjlist g;
      int n;  
      creagraph(g,&n);
      toposort(g,n);
}