拓扑排序
对一个 有向无环图 (Directed Acyclic Graph简称 DAG )G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个 偏序 得到该集合上的一个 全序 ,这个操作称之为拓扑排序。
一个较大的工程往往被划分成许多子工程,工程之间相互存在依赖关系,比如工程A 、B、C,A工程开始依赖B完成, B开始又依赖C的完成,想要完成工程的话则需要按C->B-A顺序执行。
但是一旦增加 C依赖A 的条件后,则工程之间形成环形结构 C->B-A->C,导致无法完成。
拓扑排序可将有向图转换成线性有向图,以便直观的查看有向图是否存在环结构
入度 :一个顶点的入度是以这个顶点为 终点 的有向边的数量
出度 :一个顶点的入度是以这个顶点为 起点 的有向边的数量
例如:
A->B,B的入度+1,A的出度+1
若整个课程安排图是有向无环图(即可以安排),则所有节点一定都入队并出队过,即完成拓扑排序。换个角度说,若有向图中存在环,一定有节点的入度始终不为 0。
因此,拓扑排序出队次数等于节点个数,返回 num == 0 判断课程是否可以成功安排。
这里利用网上找到的一组图说明:
入度表遍历过程中,经常使用 邻接表 、 邻接矩阵 存储、任意两个顶点之间的连通关系,以便查找常数时间内找到当前节点对应的临界节点,以及当前节点和邻接节点之间的入度、出度数
借助一个标志列表 flags,用于判断每个节点 i (课程)的状态:
对 num个节点依次执行 DFS,判断每个节点起步 DFS 是否存在环,若存在环直接返回 False。DFS 流程;
具体案例可以参考这里: 课程表