欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

拓扑排序

程序员文章站 2023-12-23 16:52:58
...

拓扑排序

 

    

  这个例子很好地解释了拓扑排序的意思。拓扑排序,就像只有穿了袜子才能穿鞋子,每一个点,都只有固定的能通往的点。

  方法一:从图形上看,我们会发现,可以直接穿的衣服没有箭头指向,例如衬衣,当把衬衣归入队列以后,此时领带也没有箭头指向了,也可以穿。

  因此可以得出没有节点可以通往(可通往节点数为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;
}

 

上一篇:

下一篇: