作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站

拓扑排序的C语言的源代码：

# include
# include
# define  M    30
# define  PR  printf
# define  SC  scanf

typedef struct ArcNode
{int adjvex;
 struct ArcNode *nextarc;
}ArcNode,*Anode;

typedef struct VexNode
{int  data;
 int  indegree;
 struct ArcNode *firstarc;
}VexNode,*Vnode,G[M];

typedef struct Lnode
{int data;
 struct Lnode * next;
} Lnode,*Link;
Link L=NULL;

void Push(int r)
{ Link q;
  q=(Link)malloc(sizeof(Lnode));
  q->data=r; q->next=L; L=q;
}

char Pop(int r)
{ Link p;
  if (L!=NULL)
     {p=L;L=L->next;r=p->data;
      free(p); return r;}
  else return -1;
}

void CreatGraph(G g,int n)
{ int i,j; Vnode q; Anode p;
   for(i=1;i<=n;i++)
    {g[i].data=i;
     g[i].indegree=0;
     g[i].firstarc=NULL;
    }
  printf("input the edge:i,j\n");
  scanf("%d,%d",&i,&j);
   while(i!=0)
    { p=(Anode)malloc(sizeof(ArcNode));
      p->adjvex=j;
      p->nextarc=g[i].firstarc;
      g[i].firstarc=p;
      g[j].indegree++;
      scanf("%d,%d",&i,&j);
    }
 }

void PrintGraph(G g,int n)
{int i; Anode p;
 PR("\nAdjacency List Graph:\n");
 printf("vexnode indgree adjvex\n");
 for(i=1;i<=n;i++)
  {PR("vex[%d]:[%d]",g[i].data,g[i].indegree);
   p=g[i].firstarc;
   while(p)
     {PR("-->[%d]",p->adjvex);
      p=p->nextarc;}
   PR("\n");
  }
}

int TopSort(G g,int n)
 {Anode p; int i,k,count=0;
  for(i=1;i<=n;i++)
    if(g[i].indegree==0) Push(i);
  PR("\nAfter the TopSort\n:");
  while(L)
   {i=Pop(i);
    PR("%d\n",g[i].data);count++;
    for(p=g[i].firstarc; p; p=p->nextarc)
      {k=p->adjvex;
       if((--g[k].indegree)==0) Push(k);}
    }
  if(count}

void main()
{G g;  int n;  clrscr();
PR("Input the numbers of node:");
SC("%d",&n);
CreatGraph(g,n);
PrintGraph(g,n);
TopSort(g,n);
}

大企鹅，以后我们就可以联系了！

相关软件：