topsort.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/*************************************************/
/*                拓扑排序算法                   */
/*        文件名:topsort.c 函数名:topsort()      */
/*************************************************/
#include<stdio.h>
#define m 20
typedef char vertextype;
typedef struct node{      /*边结点类型定义*/
      int adjvex;
      struct node *next;
  }edgenode;
typedef struct de         /*带顶点入度的头结点定义*/
  {
   edgenode* firstedge;
   vertextype vertex;
   int id;                /*顶点的入度域*/
  }vertexnode;
typedef struct{           /*AOV网络的邻接表结构*/
      vertexnode adjlist[m];
      int n,e;
      }aovgraph;

void  creat(aovgraph *g)       /*建立AOV网络的存储结构*/
 { int j,i,k,flag[m];
   edgenode  *s;
   printf("please input N and E\n");
   scanf("%d%d",&g->n,&g->e);  /*输入图中的顶点数与边数*/
   getchar();
   printf("please  input %d vertex data\n",g->n);
  for(i=0;i<g->n;i++)                        /*输入顶点值*/
      {g->adjlist[i].vertex=getchar();
       g->adjlist[i].firstedge=NULL;
       g->adjlist[i].id=0;       /*入度初始化为0*/
      }
   printf("\n please input %d edges\n ",g->e); /*输入边信息*/
   for(k=0;k<g->e;k++)
        { scanf("%d%d",&i,&j);
	  s=(edgenode*)malloc(sizeof(edgenode));
          s->adjvex=j;
          g->adjlist[j].id++;    /*顶点j的入度加1*/
          s->next=g->adjlist[i].firstedge;
          g->adjlist[i].firstedge=s;
        }
 }

void print(aovgraph g)
{  edgenode *p;
   int i;
  for (i=0;i<g.n;i++)
   { printf("%d %c  ",g.adjlist[i].id, g.adjlist[i].vertex);
     p=g.adjlist[i].firstedge;
     while (p)
      { printf("%d-->",p->adjvex);
        p=p->next;
      }
     printf("\n");
   }
}
/********************TOPSORT排序********************/
int topsort(aovgraph g)  /*函数返回输出的顶点的个数*/
  {int k=0,i,j,v, flag[m];
   int queue[m];  /*队列*/
   int h=0,t=0;
   edgenode* p;
   for (i=0;i<g.n;i++)  flag[i]=0;  /*访问标记初始化*/
    for(i=0;i<g.n;i++)     /*先将所有入度为0的结点进队*/
     if( g.adjlist[i].id==0 && flag[i]==0)
         {  queue[++t]=i;flag[i]=1; }
    while (h<t)   /*当队列不空时*/
      {
	 v=queue[++h];  /*队首元出队*/
         printf("%c----->",g.adjlist[v].vertex);
         k++;  /*计数器加1*/
         p=g.adjlist[v].firstedge;
         while(p)     /*将所有与v邻接的顶点的入度减1*/
          { j=p->adjvex;
            if (--g.adjlist[j].id==0 && flag[j]==0)   /*若入度为0则将进队*/
		    {queue[++t]=j; flag[j]=1;}
	  p=p->next;
	  }
      }

 return k;
 }
main()
{ int k=0;
  aovgraph g;
  creat(&g);
  print(g);
  k=topsort(g);
  if(k<g.n) printf(" the graph has a circle!!!");
}