没有合适的资源?快使用搜索试试~ 我知道了~
拓扑排序例子.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 138 浏览量
2021-09-13
20:02:38
上传
评论
收藏 50KB DOCX 举报
温馨提示
试读
10页
项目投标合作协议书范本.pdf
资源推荐
资源详情
资源评论
拓扑排序例子
【篇一:拓扑排序例子】
取材自以下材料:
定义和前置条件:
定义:将有向图中的顶点以线性方式进行排序。即对于任何连接自
顶点 u 到顶点 v 的有向边 uv,在最后的排序结果中,顶点 u 总是在
顶点 v 的前面。
如果这个概念还略显抽象的话,那么不妨考虑一个非常非常经典的
例子——选课。我想任何看过相关书籍的同学都知道它吧。假设我
非常想学习一门的课程,但是在修这么课程之前,我们必须要学习
一些基础课程,比如计算机科学概论,c 语言程序设计,数据结构,
等等。那么这个制定选修课程顺序的过程,实际上就是一个拓扑排
序的过程,每门课程相当于有向图中的一个顶点,而连接顶点之间
的有向边就是课程学习的先后关系。只不过这个过程不是那么复杂,
从而很自然的在我们的大脑中完成了。将这个过程以算法的形式描
述出来的结果,就是拓扑排序。
那么是不是所有的有向图都能够被拓扑排序呢?显然不是。继续考
虑上面的例子,如果告诉你在选修计算机科学概论这门课之前需要
你先学习机器学习,你是不是会被弄糊涂?在这种情况下,就无法
进行拓扑排序,因为它中间存在互相依赖的关系,从而无法确定谁
先谁后。在有向图中,这种情况被描述为存在环路。因此,一个有
向图能被拓扑排序的充要条件就是它是一个有向无环图(dag:
directed acyclic graph)。
偏序/全序关系:
偏序和全序实际上是离散数学中的概念。
这里不打算说太多形式化的定义,形式化的定义教科书上或者上面
给的链接中就说的很详细。
还是以上面选课的例子来描述这两个概念。假设我们在学习完了算
法这门课后,可以选修机器学习或者计算机图形学。这个或者表示,
学习机器学习和计算机图形学这两门课之间没有特定的先后顺序。
因此,在我们所有可以选择的课程中,任意两门课程之间的关系要
么是确定的(即拥有先后关系),要么是不确定的(即没有先后关系),
绝对不存在互相矛盾的关系(即环路)。以上就是偏序的意义,抽象而
资源评论
苦茶子12138
- 粉丝: 1w+
- 资源: 6万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功