这个例子很好地解释了拓扑排序的意思。拓扑排序,就像只有穿了袜子才能穿鞋子,每一个点,都只有固定的能通往的点。
方法一:从图形上看,我们会发现,可以直接穿的衣服没有箭头指向,例如衬衣,当把衬衣归入队列以后,此时领带也没有箭头指向了,也可以穿。
因此可以得出没有节点可以通往(可通往节点数为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;
}