博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
拓扑排序
阅读量:5887 次
发布时间:2019-06-19

本文共 501 字,大约阅读时间需要 1 分钟。

 

    

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

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

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

 

转载于:https://www.cnblogs.com/yiyiyizqy/p/7397591.html

你可能感兴趣的文章
Oracle学习笔记之五,Oracle 11g的PL/SQL入门
查看>>
css绘制几何图形
查看>>
结合kmp算法的匹配动画浅析其基本思想
查看>>
Android网络编程11之源码解析Retrofit
查看>>
安全预警:全球13.5亿的ARRIS有线调制解调器可被远程攻击
查看>>
麦子学院与阿里云战略合作 在线教育领军者技术实力被认可
查看>>
正确看待大数据
查看>>
Facebook通过10亿单词构建有效的神经网络语言模型
查看>>
发展大数据不能抛弃“小数据”
查看>>
中了WannaCry病毒的电脑几乎都是Win 7
查看>>
学生机房虚拟化(九)系统操作设计思路
查看>>
nginx报错pread() returned only 0 bytes instead of 4091的分析
查看>>
质数因子
查看>>
Spring源码浅析之事务(四)
查看>>
[转载] Live Writer 配置写 CSDN、BlogBus、cnBlogs、163、sina 博客
查看>>
SQL:连表查询
查看>>
MySQL日期函数、时间函数总结(MySQL 5.X)
查看>>
c语言用尾插法新建链表和输出建好的链表
查看>>
高性能 Oracle JDBC 编程
查看>>
java 中ResultSet可以获取的数据类型及返回值类型列表
查看>>