7.7拓扑排序

在一个表示工程的有向图中，有顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。

AOV网中的弧表示活动之间存在的某种制约关系。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1, V2,Vn,满足若从顶点vi到v)有一条路径，则在顶点序列中顶点Vi 必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列

7.7.2拓扑排序算法

对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

代码不妨了，以后更新Java的

一个AOV网的拓扑序列不是唯一的

检测AOV网中是否存在环方法

对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

7.8关键路径

把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。

AOE网中没用入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点

v0，v1,....,v9分别表示事件，<v0,v1>,<v0,v2>,....<v8,v9>表示一个活动，用a0，a1....a12表示，它们的值代表活动持续时间

比如弧<V,V1>就是从源点开始的第一个活动a0，它的时间是3个单位。

我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。 显然就图7-9-3的AOE网而言，开始→发动机完成→部件集中到位→组装完成就是关键路径，路径长度为5.5

7.8.1 关键路径算法

我们将AOE网转化为邻接表结构，注意与拓扑排序时 邻接表结构不同的地方在于，这里弧链表增加weight域，用来存储弧的权值。

关键路径算法和拓扑排序算法大概一致

小总结

图是计算机科学中非常常用的一类数据结构，有许许多多的计算问题都是用图来定义的。由于图也是最复杂的数据结构，对它讲解时，涉及到数组、链表、栈、队 列、树等之前学的几乎所有数据结构。因此从某种角度来说，学好了图，基本就等于理解了数据结构这门课的精神。

图的存储结构

邻接矩阵 邻接表 边集数组 十字链表 邻接多重表

图的遍历分为深度和广度两种，各有优缺点，就像人在追求卓越时，是着重深度还是看重广度，总是很难说得清楚。

图的应用是我们这一-章浓墨重彩的一 部分， 一共谈了三种应用:最小生成树、最短路径和有向无环图的应用。

最小生成树，我们讲了两种算法:普里姆(Prim) 算法和克鲁斯卡尔(Kruskal)算法。普里姆算法像是走一步看一步的思维方式，逐步生成最小生成树。而克鲁斯卡 尔算法则更有全局意识，直接从图中最短权值的边入手，找寻最后的答案。

最短路径的现实应用非常多，我们也介绍了两种算法。迪杰斯特拉(Dijkstra) 算法更强调单源顶点查找路径的方式，比较符合我们正常的思路，容易理解原理，但算 法代码相对复杂。而弗洛伊德(Flbyd) 算法则完全抛开了单点的局限思维方式，巧妙地应用矩阵的变换，用最清爽的代码实现了多顶点间最短路径求解的方案，原理理解有难度，但算法编写很简洁。

有向无环图时常应用于工程规划中，对于整个工程或系统来说，我们一方面关心 的是工程能否顺利进行的问题，通过拓扑排序的方式，我们可以有效地分析出一一个有向图是否存在环，如果不存在，那它的拓扑序列是什么?另方面关心的是整个工程完成所必须的最短时间问题，利用求关键路径的算法，可以得到最短完成工程的工期以及关键的活动有哪些。

算法--打油诗

算法很美妙，但它很枯燥

我想把它秒，但我办不到

奥利给！！！

学！！！