目录

AOV网（Activity On Vertex Network）

拓扑排序（Topological Sort）

拓扑排序 – 思路

拓扑排序 – 实现

AOE网 (Activity On Edge Network)

AOV网与AOE网的关系

拓扑排序应用

LeetCode_210:课程表

---

AOV网（Activity On Vertex Network）

一项大的工程常被分为多个小的子工程, 子工程之间可能存在一定的先后顺序，即某些子工程必须在其他的一些子工程完成后才能开始; 在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，子工程被称为活动(Activity)

以顶点表示活动、有向边表示活动之间的先后关系，这样的图简称为 AOV 网, 标准的AOV网必须是一个有向无环图(Directed Acyclic Graph，简称 DAG)

拓扑排序（Topological Sort）

前驱活动：有向边起点的活动称为终点的前驱活动  (注意: 只有当一个活动的前驱全部都完成后，这个活动才能进行)后继活动：有向边终点的活动称为起点的后继活动

什么是拓扑排序？将 AOV 网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面比如上图的拓扑排序结果是：A、B、C、D、E、F 或者 A、B、D、C、E、F (结果并不一定是唯一的)

拓扑排序 – 思路

可以使用卡恩算法(Kahn)完成拓扑排序 假设 L 是存放拓扑排序结果的列表 (1) 把所有入度为 0 的顶点放入 L 中，然后把这些顶点从图中去掉 (2) 重复操作(1)，直到找不到入度为 0 的顶点      如果此时 L 中的元素个数和顶点总数相同，说明拓扑排序完成      如果此时 L 中的元素个数少于顶点总数，说明原图中存在环，无法进行拓扑排序

拓扑排序 – 实现

在代码实现中, 使用一个map来维护顶点与该顶点入度的关系, 当某个顶点的入度为 0 , 那么该顶点需要放入list列表中, 进行排序, 并将该顶点所属边的终点顶点的入度 -1, 模拟移除该顶点; 

/**  * 拓扑排序(卡恩算法)  */ @Override public List<V> topologicalSort() {     List<V> list = new ArrayList<>(); //存储排好序的顶点值     Queue<Vertex<V, E>> queue = new LinkedList<>(); //存储度为0的顶点     Map<Vertex<V, E>, Integer> ins = new HashMap<>(); //存储顶点与实时入度的映射     /**      * 将入度为 0的顶点入栈,作为起始顶点;      * 将入度不为 0的顶点加入ins映射中, 后面进行实时更新      */     vertices.forEach((V v,Vertex<V,E> vertiex)->{         int inSize = vertiex.inEdges.size();         if(inSize == 0){             queue.offer(vertiex);         }else{             ins.put(vertiex,inSize);         }     });     while(!queue.isEmpty()){         Vertex<V, E> vertex = queue.poll(); //队头元素出队         list.add(vertex.value);  //加入集合         /**          * 模拟vertex顶点删除, 该顶点所有的边的to顶点的入度需要-1          */         vertex.outEdges.forEach((Edge<V,E> edge)->{             int inSize = ins.get(edge.to) - 1;             if(inSize == 0){                 queue.offer(edge.to);             }else{                 ins.put(edge.to,inSize);             }         });     }     return list; }

AOE网 (Activity On Edge Network)

AOE网的定义：在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网

如上所示，共有11项活动(11条边), 9个事件(9个顶点)。整个工程只有一个开始点和一个完成点。即只有一个入度为零的点 (源点) 和只有一个出度为零的点(汇点)关键路径：是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间 如上图所示，1 -> 2 -> 5 -> 7 -> 9是关键路径(关键路径不止一条，请输出字典序最小的), 权值的和为18

AOV网与AOE网的关系

从定义上来看，很容易看出两种网的不同，AOV网的活动以顶点表示，而AOE网的活动以有向边来表示，AOV网的有向边仅仅表示活动的先后次序。纵观这两种网图，其实它们总体网络结构是一样的，仅仅是活动所表示的方式不同，因此可以猜想从AOV网转换成AOE网应该是可行的。

  通常AOE网都是和关键路径联系在一起的，在AOE网中我们可以通过关键路径法来计算影响整个工期的关键路径，达到缩短工期的目的。在传统的AOV网中是没有表示活动时间的权值的，因此传统的AOV网无法估算工期，但是如果我们在AOV网中的活动结点上都标上时间属性，那么AOV网就可以完全转换为AOE网。

拓扑排序应用

LeetCode_210:课程表