这个例子很好地解释了拓扑排序的意思。拓扑排序,就像只有穿了袜子才能穿鞋子,每一个点,都只有固定的能通往的点。
方法一:从图形上看,我们会发现,可以直接穿的衣服没有箭头指向,例如衬衣,当把衬衣归入队列以后,此时领带也没有箭头指向了,也可以穿。
因此可以得出没有节点可以通往(可通往节点数为0)就删除。
这种方法容易想到,但是比较麻烦实现。
方法二:用深度优先搜索,看它是否有可以连接的点,如果有,就继续往下深搜。
但是,如果已经搜索过的点
void dfs ( int s ){ state[s]=1;//改变状态 int h=head[s]; while(h!=1)//如果还有可以连接的点 { int t=edge[s].ta; if(state[t]==0) { dfs(t) } h=edge[s].next; } now++; g[now]=s;}