第八讲:图(下)

8.1 最小生成树问题

8.1.1 最小生成树(Minimum Spanning Tree)

如图1所示。

1.jpg 

图1

它是一棵树:无回路;|V|个顶点一定有|V|-1条边;

它是生成树:包含全部顶点;|V|-1条边都在图里。在图1中,第2/3/4个图都是图1的生成树,可以看出,生成树中任加一条边都一定构成回路

最小:边的权重和最小

显然可以得出,最小生成树存在<->图连通

8.1.2 贪心算法

贪:每一步都要最好的。好:权重最小的边。

需要约束:只能用图里有的边;只能正好用掉|V|-1条边;不能有回路。

8.1.3 Prim算法(密集图)—让一棵小树长大

如图2所示,我们选择v1作为源节点,选择权重最小的(为1),到v4;然后我们看这个图,权重最小的为2有两个边,分别到v2和v3,我们先选择连到v2,再用v4连接到v3;为了不构成回路,我们需要选择权重为4的由v4到v7的边;再选择权重为1的v6,再选择权重为6的v5。

2.jpg 

图2

其伪码描述如下,其中dist[V]=E(s,v)或正无穷,parent[s]=-1:

完整代码:

 

8.1.4 Kruskal算法(稀疏图)—将森林合并成树

寻找权重最短的边,初始的情况下认为每一个顶点都是一棵树,通过不断把边收进来,就把两棵树并成了一棵树,最后把所有节点并成一棵树。

伪码如下:

复杂度为T=O(|E|log|E|)

完整代码:

8.2 拓扑排序

8.2.1 拓扑排序

AOV(Activity On Vertex)网络

如图3所示,是指所有的真实活动是表现在顶点上的,顶点与顶点之间的有向边表现了顶点间的先后顺序。

3.jpg 

图3

所谓拓扑序是指:如果图中从V到W有一条有向路径,则V一定排在W之前,满足此条件的顶点序列称为一个拓扑序。获得一个拓扑序的过程就是拓扑排序。

AOV网络如果有合理(所谓不合理是指,网络形成了一个环,那就代表着V必须在V开始之前结束,自然不合理)的拓扑序,则必定是有向无环图(Directed Acyclic Graph, DAG)。

所谓拓扑排序,就是每一次输出没有前序顶点的顶点。

伪码描述如下:

聪明的算法:随时将入度变为0的顶点放到一个容器(数组、堆栈、队列等都行)中,下一次直接从这里面直接拿数据就可以了。利用队列的新的伪码描述:

时间复杂度T=O(|V|+|E|)

完整代码:

8.2.2 关键路径

AOE(Activity On Edge)网络一般用于安排项目的工序。与AOV不同,AOE的活动表示在边上,而节点代表活动到此结束。一般情况下,AOE网络的图示为以下结构:

4.jpg 

图4

如图5所示,图中虚线,且权重为0表示的是,要继续执行9/7权重那里,4/5这里必须都得走到了。

5.jpg 

图5

问题1:整个工期有多长?

Earliest[0]=0;

Earliest[j]=max(<i,j>∈E){Earliest[i]+C<i,j>}

故Earliest[8]=18

问题2:哪几个组有机动时间(保证工期最长18天)?

方法是设置最后一个最晚完成时间为18天,然后往前推。

注意:虽然7倒推回去5只需要在第10天完工就可以,但是考虑到4必须在第7天完工,而6必须在第16天完工,又由于4、5同时完工才能往下走,所以5的最晚完成时间也必须和4同样,为第7天。

Latest[8]=18;

Latest[i]=(min<i,j>∈E){Latest[j]-C<i,j>}

所谓机动时间就是哪些组可以不用急着赶工

机动时间D<i,j>=Latest[j]-Earliest[i]-C<i,j>

所谓关键路径就是整个流程中最需要关注的地方,哪些步骤是一点也不能耽误的,只要它耽误了,整个流程都要耽误,所以它是绝对不允许延误的活动组成的路径。