一、拓扑排序--AOV网
1.找到做事的先后顺序(有向无环图)
拓扑排序实现:
- 从AOV网中选择一个没有前驱(入度为0)的顶点并输出
- 从网中删除该顶点和所有以它为起点的有向边
- 重复上述动作,直至当前的AOV网为空 或 当前网中不存在无前驱的顶点为止
拓扑排序定义:有向无环图
拓扑排序的代码实现:
(一)
indegree: 记录度数为0的顶点
print:记录拓扑排序最终的序列
count:遍历拓扑排序数列,插入数据的操作
S:栈,从indegree中为0的顶点进行保存
(二)
条件判断如果indegree[v]-1 == 0的话满足条件
等价于 !( --indegree[v])
拓扑排序的时间复杂度
O(|V|+|E|)
若采用邻接矩阵 O(|V|²)
二、逆拓扑排序
1.逆拓扑排序步骤
邻接矩阵来记录
>>>>也就是可以直观看出顶点和顶点之间的关系
区别邻接表:
而逆邻接表所指向的是图中本来应该指向它的
深度优先实现拓扑排序和逆拓扑排序
逆拓扑排序与深度优先的关系:逆拓扑排序最终要进行 print(v)
区分考题中的 V 和 W
V: 当前正在处理的顶点
W:表示与V邻接的顶点