拓扑排序

 #include<stdio.h>  

#include
<stdlib.h>

#include
<string.h>

typedef
struct AOE

{

int n; //所指为该节点的值

struct AOE *next;

}AOE;
// 一个动态链表用来记录后面的连接表

struct T

{

int n,flag; //该节点前面有多少个元素

AOE
*next;

}VEX[
524]; //静态链表用来储存头结点

void build( int x, int y) //建立表

{

AOE
*p;

if(VEX[x].next==NULL)

{

VEX[x].next
= ( AOE *) malloc( sizeof ( AOE));

VEX[x].next
->next = NULL;

VEX[x].next
->n=y;

VEX[y].n
++;

return ;

}

p
=VEX[x].next;

while(p->next)

p
= p->next;

p
->next= ( AOE * ) malloc( sizeof ( AOE));

p
->next->next = NULL;

p
->next->n=y;

VEX[y].n
++;



}

void rank(int n)

{

int i =1,sum=1;

while(i<=n)

{

if(VEX[ i ].n==0&&!VEX[i].flag) //寻找入度为0的节点

{

AOE
*p,*q;

VEX[i].flag
=1;

p
=VEX[i].next;

while(p)

{

q
=p;

VEX[p
->n].n--;

p
=p->next;

free(q);

}

printf(sum
==n?"%d\n":"%d ",i);

sum
++;

i
=0; //会到节点0重新开始遍历,这个地方可以优化,可以用栈

}

i
++;

}

}

int main( )

{

int n,m,x,y;

while ( scanf("%d%d" , &n,&m)!=EOF)

{

for(int i=0;i<=n;i++)

{

VEX[i].flag
=0;

VEX[i].n
=0;

VEX[i].next
=NULL;

}

for( int i=0; i< m; i++)

{

scanf(
"%d%d",&x,&y);

build(x,y);

}

rank(n);

}

return 0;

}

  

原文地址:https://www.cnblogs.com/yuelingzhi/p/2171762.html