本文共 5616 字，大约阅读时间需要 18 分钟。

• 图的经典应用主要有最小生成树（求最小代价）、最短路径、拓扑排序和关键路径。

一、最小生成树

1、基本概念

• 一个带权连通图的生成树往往不唯一，每个生成树的权（树中每条边的权值之和）也不同，但始终存在是所有生成树中权最小的树，这样的树就成为图的最小生成树（Minimum-Spanning-Tree，MST）。

2、性质

• 图的最小生成树有如下性质：
  1）最小生成树并不一定是唯一的，即最小生成树的树形不唯一。当图中各边的权都不唯一时，最小生成树方是唯一的。
  2）若图是边数比顶点数少一个的无向连通图，则其最小生成树就是其本身。
  3）最小生成树的权是唯一的，是所有生成树中权最小的。
  4）最小生成树的边数为顶点数减一。
  5）若G(V, E) 是一个带权连通图，U 是 V 的非空子集，若(u, v) 是一条具有最小权值的边，u 属于 U，v 属于 V-U，则比存在一棵包含边(u,v)的最小生成树。

3、算法

• 基于性质 5）的最小生成树的算法有 Prim算法和Kruskal算法，都是一种贪心算法。
• 一种通用的最小生成树算法如下伪代码：

  GetMST(G){
       	T=NULL;	while T is not the MST:		do find a edge(u,v) with minium value:			T=T+(u,v)}

3.1、Prim 算法

• 该算法基本过程如下图：
  
• 该过程类似寻找最短路径。Prim 算法的步骤如下：
  假设：G=｛V，E｝是连通图，其最小生成树T=（U，E_T），E_T是最小生成树的边集。
  初始化：向空树T=（U，E_T）中添加G的任一顶点 u₀，使U=｛u₀｝，E_T不空。
  循环：从 G 中选择满足｛(u,v)|u∈U，v∈V-U｝且具有最小权值的边(u,v)，加到 T 中，置 U=U∪{v}，E_T=E_T∪{(u,v)}。
  结束循环条件：T 是最小生成树。
• 简单描述如下：

  void Prim(G,&T){
       	T=NULL;	U={
       w};	while((V-U)!=NULL)		if (u,v)|u∈U，v∈V-U and ismin(u,v)		{
       			T=T+(u,v);			U=U+{
       v};		}}

• prim算法的时间复杂度为O(|V|²)，适用于求边稠密的图的最小生成树。

3.2、Kruskal 算法

• 不同于 Prim 是从顶点开始扩展最小生成树，该算法是按权值的递增次序选择合适的边来构造最小生成树。其过程如下图：
  
• 该算法的基本步骤如下：
  假设：G=｛V，E｝是连通图，其最小生成树T=（U，E_T）。
  初始化：U=V，E_T=∮
  循环：按 G 的边权递增次序依次从 E-E_T 中选择合适的边，若这条边加入 T 后不会形成回路，则将其加入 E_T，否则放弃另寻它边，直到 E_T中含有 n-1 条边。
• 此算法的实现简单描述如下：

  void Kruskal(V,&T){
       	T=V;	numS=n;	while(numS>1)	{
       		select min(u,v);		if(v and u belong to defferend connected component)		{
       			T=T+{
       (u,v)};			numS--;		}	}}

• 该算法具体实现时，采用堆存放边集，因此每次选择最小权值的边只需O(log|E|) 的时间，并且由于生成树中所有边可视为一个等价类，因此每次添加新边的过程类似于求解等价类，可采用并查集的数据结构描述 T，从而构造 T 的时间复杂度为 O(|E|log|E|).
• 该算法适用于边稀疏而顶点较多的图。

二、最短路径

1、基本概念

• 当一个图是带权图，且每条边的权值不一样，则无法通过广度优先搜索遍历来求最短路径，此时便要用此处专门针对带权图求最短路径的算法了。
• 所谓最短路径，便是带权路径长度最短的一条边，而所谓带权路径长度是指从v出发到u所经过的路径的权值之和。
• 求最短路径的算法通常都依赖于：两点之间的最短路径也包含了路径上其他顶点的间的最短路径。

2、分类

• 所有求最短路径的问题可分为两大类：单源最短路径和每对顶点间的最短路径。所谓单源最短路径，指的是求图中某一点到其他各点的最短路径，典型算法是Dijkstra（迪杰斯特拉）；求每对顶点之间的典型算法是Floyd（弗洛伊德）。

3、Dijkstra 算法

3.1、基本思想

• 算法设置一个集合 S 记录已经求得的最短路径的顶点，初始时将 v₀ 放入 S，每增加一个新点到 S 中，更新源点到 S 中其他点的最短路径长度。

3.2、辅组数组

• 该算法求最短路径的过程，需要用到三个辅助数组，作用分别如下：
  1）dist[]：记录源点到其他各点当前的最短路径长度；初始情况，若源点到一点有路径，则dist[i]为该路径的权值，否则就是∞。
  2）path[]：path[i] 表示从源点出发到点i之间的最短路径的前驱节点。算法结束时，可根据其值追溯得到源点和点i之间的最短路径。
  3）arcs[][]:表示带权有向图，arcs[i][j]表示有向边<i,j>的权值，若不存在有向边<i,j>，则arcs[i][j]=∞。

3.3、基本步骤

• Dijkstra 算法的基本步骤如下：
  1）初始化, 集合S初始为{0},dist[]的初始值 dist [i]= arcs[0][i],i=1,2,3…,n-1
  2）从顶点集V-S中选出v_j，满足dist[j]= Min(dist[i]lv_i∈V-S}, v_j就是当前求得的条从v₀出发的最短路径的终点，令S=S∪{j}.
  3）修改从v₀出发到集合VーS上任一顶点v_k可达的最短路径长度：若 dist[i]+arcs[j][k]<dist [k],则更新dist[k]= dist[j]+arcs[j][k]
  4）重复2)~3)操作共m-1次，直到所有的顶点都包含在S中。
• 可见 Dijkstra 算法也是基于贪心策略的，其时间复杂度无论是邻接矩阵还是邻接表都是O(|V|²)。值得注意的是，该算法不适用于带负权的图，如下图：
  

2.4、示例

• 示例如下：
  

3、Floyd 算法

3.1、基本思想

• Floyd 的基本思想如下：
  递推产生一个 n 阶方阵序列 A^(-1), A⁰,…,A^k,…,A^(n-1)，A^k[i][j] 表示从顶点 v_i 到 v_j 的路径长度，k 表示绕行第 k 个顶点的运算步骤。A^k[i][j] 初始时为边权值或∞，若增加中间顶点后，得到的路径比原来的路径长度小，则更新为新的路径。
• 算法描述如下：
  1）定义n 阶方阵序列 A^(-1), A⁰,…,A^k,…,A^(n-1)，其中 A^(-1)[i][j]=arcs[i][j]
  2）A^k[i][j] = Min{ A^k-1[i][j], A^k-1[i][k], A^k-1[k][j] }, k = 0,1,2 …… n-1，表示从顶点 V_i 到 V_j 中间顶点的序号不大于 k 的最短路径的长度。

3.2、示例如下：

• 带权有向图如下：
  
• Floyd 算法运行如下：
  
• Floyd 算法的时间复杂度为 O(|V|³)，与轮流将图中的点作为源点进行 Dijkstra 算法的时间复杂度 O(|V|²)|V| 等价。
• Floyd 算法允许图中的边带负权，但是不允许包含带负权值得边组成回路，也可用于带权无向图的多源最短路径的求解。

三、拓扑排序

1、DAG 图和 AOV 网

• DAG 图就是有向无环图，指不存在环的有向图。
• AOV 网：若 DAG 图表示一个工程，顶点表示活动，用有向边<V_i, V_j> 表示 V_i 必须先于 V_j 进行，则将这种有向图称之为顶点表示活动的网络，记为 AOV 网。

2、拓扑排序

• 由 DAG 的顶点组成的序列，当且仅当满足下列条件：
  ① 每个顶点出现且只出现一次；
  ② 若顶点 A 在序列中中排在 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径。
• 则该序列称之为图的拓扑排序。
• 或者定义为：拓扑排序是 DAG 的一种排序，它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 之后。
• AOV 网的拓扑排序不唯一。

2.1、步骤

• 拓扑排序的步骤如下：
  ① 从 AOV 网中选择一个没有前驱（没有入度）的点输出；
  ② 从网中删除该点和与其连接的所有边；
  ③ 重复上述操作，直到网为空或当前网中不存在没有前驱的点为止。

2.2、实现代码

• 算法的实现的伪代码如下：

  bool TPSort(Graph g){
       	InitStack(S);	for(int i=0;i
       
        nextarc)		{
       			v=p->adjvex;			if(!(--indegree[v]))				push(S,v)		}	}	if(count
       

3、逆拓扑排序

• 一个 AOV 网，若使用如下步骤进行排序，则称为逆拓扑排序
  ① 从 AOV 网中选择无后继的点，即出度为零的点进行输出；
  ② 从网中删除该点及其邻接边；
  ③ 重复上述直到 AOV 网为空。

4、注意事项

1）入度为 0 的点，工程可以从该点出发或继续。

2）拓扑排序是否唯一，关键看所有顶点是不是都是具有唯一前驱后继的点，一旦有某个点并非如此，则得出的拓扑排序便不唯一。 3）可以根据拓扑排序的序列对图的点进行重新编号，生成 AOV 网的新的邻接矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑排序；反之不一定成立。

四、关键路径

1、AOE 网

• 若带权有向图中，顶点表示事件，有向边表示活动，有向边的权值表示完成该活动的开销，这种图称之为用边表示活动的网络，简称 AOE 网。
• AOE 网中仅有一个入度为 0 的点，称之为开始顶点或源点；同样 AOE 网中仅有一个出度为 0 的点，称之为结束顶点或汇点。
• AOE 网也是一种 DAG 图。

1.1、性质

• AOE 网性质如下：
  ① 只有某点所代表的的事件发生了，其出边所代表的活动才能开始。
  ② 只有进入某点的各个有向边代表的活动都结束了，该点所代表的的事件才能发生。

1.2、关键路径与关键活动

• AOE 网的关键路径，是指从源点出发到汇点结束，具有最大路径长度的路径称为关键路径，而关键路径上的活动称为关键活动。
• 关键路径的长度表示着完成整个工程的最短时间

2、与关键活动相关的参量

2.1、事件v_k的最早发生时间ve(k)

• 是指从源点到顶点v~k~的最长路径长度。ve(k) 决定了所有从 v_k 开始的活动能够开工的最早时间，可用如下递推公式：
  ve(源点) = 0
  ve(k) = Max{ ve(j) + Weight(v_j, v_k)}，v_k 为 v_j 的任意后继。
• 计算 ve() 可以按从前往后的顺序进行，也可在拓扑排序的基础上进行：
  ① ve[1,…,n] 初始全为 0.
  ② 输入一个入度为 0 的点，计算其直接后继点的最早发生时间，若 ve[j]+Weight(v_j, v_k) > ve[k]，则 ve[k] = Weight(v_j, v_k) + ve[j]。
  ③ 重复上述两步直到输出所有顶点。

2.2、事件v_k的最迟发生时间vl(k)

• 指在不推迟整个工程完成的前提下，即保证它的后继事件v~j~在其最迟发生时间vl(j)能够发生时，该事件最迟必须发生的时间。可用下面的递推公式来计算:
  vl（汇点）=ve（汇点）
  vl(k) =Min(vl(j) - Weight(v_k, v_j)},v_k为v_j的任意前驱.
• 计算vl()值时，按从后往前的顺序进行，在上述拓扑排序中，増设一个栈以记录拓扑序列，拓扑排序结朿后从栈顶至栈底便为逆拓扑有序序列。过程如下:
  ① vl[1,…,n] 初始全为ve[n] .
  ② 栈顶点出栈，计算其所有直接前驱顶点最迟发生时间，若栈顶点的最迟发生时间与入边所代表的活动时间的差小于其前驱点的最迟发生时间t，则更新其前驱最迟发生时间为 t
  ③ 重复上述两步直到输出所有顶点。

2.3、其他时间参量

• 活动最早开始时间 e：它是指该活动弧的起点所表示的事件的最早发生时间。若边<v~k~,v~j~> 表示活动，则有e(i)=ve(k).
• 活动最迟开始时间：它是指该活动弧的终点所表示事件的最退发生时间与该活动所需时间之差。若边<v_k,v_j>表示活动a_i，则有 l(i) = vl(j) - Weight(v_k, v_j)
• 上述两个时间参量的差额称为完成活动的时间余量，即在不增加完成整个工程所需的总时间的情况下，活动可以拖延的时间。时间余量为 0 的活动必须如期完成，因此也是关键活动。

3、求关键路径的算法步骤

• 算法的步骤描述如下：
  1)从源点出发，令ve（源点）=0,按拓扑有序求其余顶点的最早发生时间ve()；
  2)从汇点出发，令vl（汇点）=ve（汇点），按逆拓扑有序求其余顶点的最迟发生时间vl();
  3)根据各顶点的ve() 値求所有弧的最早开始时间e();
  4)根据各顶点的vl() 值求所有孤的最迟开始时间 l();
  5)求AOE网中所有活动的差额 d(),找出所有d()=0的活动构成关键路径.
  

4、注意事项

1）可以通过适度缩减关键活动的时间达到缩减整个工程的工期，一定要适度，因为当缩减时间太多，该活动就不再是关键活动了。

2）具有多条关键路径的工程，要达到缩减整个工程的工期，就必须对这些关键路径的关键活动的时间进行缩减；反过来说，只是缩减某条关键路径上的关键活动的时间是不足以影响到整个工程的工期。

转载地址：http://zhqgn.baihongyu.com/