图论算法 有图有代码 万字总结 向前辈致敬（6） critical, 工程, 网络

yuyang911220

AOE网络AOE网络就是边表示活动的网络（activity on edge network），它的有向边表示在一个工程中所需完成的任务或活动，而顶点表示事件，用来标识某些活动的完成。在AOV网络中，事件高数2完成意味着要先完成高数1；AOE网络中，事件高数2完成意味着已经完成了高数1。也就是说在AOE中，当一个事件发生时，就表明触发该事件的所有活动都已经完成。
在AOE网络中，有些活动可以并行地进行，所以完成整个工程所需的最短时间是从开始顶点到终止顶点的最长路径的长度。关键路径（critical path）就是一条具有最长路径长度的路径。
一个事件vi可以发生的最早发生时间（earliest time），是从开始顶点vo到顶点vi的最长路径的长度。活动vi的最迟开始时间（latest time），记作late(i)，是指在不增加工程工期的前提下，活动ai能够最迟的开始时间。
关键网络（critical activity）是指满足early(i)=late(i)的活动，一个活动的最迟开始时间late(i)与最早开始时间early(i)之间的差说明了该活动的关键程度。
下面列出两个比较常用的公式：
1）事件最早发生时间的计算
earliest[j]=maxi∈P(j){earliest+<i,j>的持续时间}
以上这个数学公式的markdown“源码”： $ earliest[j] = displaystyle max_{x in {P(j)}} { earliest + <i , j> 的持续时间 } $

• 1
• 2

2）事件最晚发生时间的计算
latest[j]=mini∈S(j){latest−<j,i>的持续时间}
最小生成树一个无向图G的最小生成树（minimum spanning tree）就是由该图的那些连接G的所有顶点的边构成的总值最低的树。最小生成树存在当且仅当G是连通的。
下面第二个图是第一个图的最小生成树（碰巧是唯一的，但并不能代表一般情况）。最小生成树是一棵树；因为它无环；因为最小生成树包含每一个顶点，所以它叫生成树；此外，它显然是包含所有顶点的最小的树。

Prim算法计算最小生成树的一种方法是使其连续地一步一步成长，在每一步中，都要把一个结点当作根并且往上累加边，于是就将关联的顶点加到了增长中的树上。
Prim算法和前面求最短路径的Dijkstra算法思想类似，因此和前面一样我们对每一个顶点保留值dv和pv以及一个标记顶点的known或unknown。

还是老办法，在Prim算法中也设定一个表的初始状态如下。

将v1设置为known的，根据Prim算法上一张图所示，v1连接了v2、v3、v4，其dv分别为2、4、1，因此更新如下。

将v4声明为known，更新如下。

将v2和v3先后声明为known，更新如下。

将v7声明为known后更新如下左图，最后将v6和v5也更新为known后更新如下右图。

下面是Prim算法的伪代码实现，其中T为生成树的边集，TV是当前生成树T的顶点集合
Kruskal算法第二种贪心策略是连续地按照最小的权选择边，并且当所选的边不产生回路时就把它作为取定的边。同样是前面的示例，用Kruskal算法执行如下。

形式上，Kruskal算法是在处理一个森林——树的集合。下图展示了边被添加到森林中的顺序。

当添加到森林中的边足够多时，算法终止，这里算法的作用在于决定边（u，v）是应该添加还是舍弃。
在该算法执行的过程中，两个顶点属于同一个集合当且仅当它们在当前的生成森林（spanning forest）中连通。如果u和v在同一个集合中，那么连接它们的边就要放弃，因为当它们已经连接的情况下，再添加边（u，v）就会形成一个回路。
如果这两个顶点不在同一个集合中，就应该将这条边加入，并对包含顶点u和v的两个集合执行一次union操作。这样将保持集合的不变性，因为一旦边（u，v）添加到生成森林中，若w连通到u而x连通到v，这x和w必然是连通的，因此属于相同的集合。虽然将边排序便于选取，但用线性时间建立一个堆则是更好的想法，此时deleteMin使得边依次得到测试。
Sollin算法Sollin算法在每一步都为生成树递归地选取若干条边，在每一步处理开始时，说选取的边与图中的所有n个顶点形成一个生成森林。在执行过程中，为森林中的每棵树都选取一条边，与选取的边都是恰有一个顶点在树上且代价最小。由于森林中的两棵树可能选取同一条边，所以需要去掉同一条边被多次选取的情况。在开始时，说选取的边集为空，当最后结果只有一棵树或者再没有边可供选取时，算法就此结束。

yuchengze

很不错的帖子，很好的算法介绍，路过帮顶