중국어판 토폴로스 솔트 리포트 (Topological Sort - 拓扑排序)

목차

없음

본문내용

计算机专业排课: 用一个图来解决:
1. 每一门课为图的顶点
2. 前是后的预修课程 ( v是w的预修课程)

先写出要预修的课程在画图
定义: ADT 为topo_sort:: 在图中v到w 有一条有向路径, 那么 v 一定在w 之前, 成为拓扑序;
AOV 有合理的拓扑序, 则一定是有向无环图(DAG, Directed Acyyclic Graph)
如何去排这些课呢?
1. 首先, 排那些没有预修课程的课, 先把那些没有预修课程的课输出, c1 ,c2,c3,c4随便一个,无所谓; 比如说先来输出c1, 第一学期排课 第二学期排课第三学期排课第四学期排课第五…
2. 这就是一个拓扑排序的过程, 每一次先输出没有前边顶点的顶点,(入度为0的顶点先选择), 输出同时, 把原图中的顶点抹掉,抹光的时候,就结束啦!

算法:
1. 要把所有的的顶点都输出,
所以需要一个循环;
2. 要找到一个还没输出,
并且入度=0的顶点
输出或者记录V 的输出序号
3. 要把v从原图中抹掉,
这是入度就减一
4. 如果这样的v不存在话, 说明有回路
跳出循环
聪明的算法: 其实就是让V= 未输出的入度为0的顶点 这一步加快
随时让入度=0的顶点放在一个特殊容器里,下次找度=0的顶点时, 直接去容器里取一个出来就行了

참고자료

· 없음