最小生成树、最短路径、拓扑排序、关键路径

一、最小生成树

普利姆算法和克鲁斯卡尔算法是两个利用MST性质构造最小生成树的算法。

1、普利姆算法（“加点法”）

2、克鲁斯卡尔算法

二、最短路径 1、迪杰斯特拉算法

（从某个源点到其余各顶点的距离）

时间复杂度为O(n^2)

2、弗洛伊德算法

（每一对顶点之间的最短路径）

时间复杂度为O(n^3)

三、拓扑排序

1、AOV-网

用顶点表示活动，用弧表示活动间的优先关系的图称为顶点表示活动的网，简称AOV-网。

注意：

（1）在AOV-网中，不应该出现有向环；

（2）检测是否存在有向环的办法是对有向图的顶点进行拓扑排序；

2、拓扑排序

概念：

所谓的拓扑排序就是将AOV-网中所有顶点排成一个线性序列，该序列满足：若在AOV-网中由顶点Vi到顶点Vj只有一条路径，则在该线性序列中顶点Vi必定在顶点Vj之前。

过程：

（1）在有向图中选一个无前驱的顶点且输出它；

（2）从图中删除该顶点和所有以他为尾的弧；

（3）重复（1）和（2），直至不存在无前驱的顶点；

（4）若此时输出的顶点个数小于有向图中的顶点个数，则说明有向图中存在环，否则输出的顶点序列即为一个拓扑序列；

四、关键路径

1、AOE-网

AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程完成的时间。

2、几个定义：

（1）源点：网中只有一个入度为零的点；

（2）汇点：网中只有一个出度为零的点；

（3）带权路径长度：一条路径各弧上的权值之和；

（4）关键路径：找一条从源点到汇点的带权路径长度最长的路径；

3、关键路径求解的过程

（1）对图中顶点进行排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i);

（2）按逆拓扑序列求出每个事件的最迟发生时间vl(i)；

（3）求出每个活动ai的最早开始时间e(i)；

（4）求出每个活动ai的最晚开始时间l(i)；

（5）找出e(i)=l(i)的活动ai，即为关键活动。由关键活动形成的由源点到汇点的每一条路径就是关键路径（关键路径有可能不止一条）；

4、几个时间的求法