data structure

本节是历年考查的重点 。图的应用主要包括 :最小生成(代价)树 、最短路径 、拓扑排序和关键路径 。一般而言 ,这部分内容直接以算法设计题考察的可能性很小,而更多的是结合图的实例来考查算法的具体执行过程,读者必须学会手工模拟给定图的各个算法的执行过程,此外,还需要掌握对给定模型建立相应的图去解决问题的方法 。

1. 最小生成树

一个连通图的生成树是图的极小连通图,它包含图中的所有顶点,并且只含尽可能少的边。这意味着对于生成树来说,若砍去它的一条边,则会使生成树变成非连通图;若给它增加一条边,则会形成图中的一条回路。

对于一个带权连通无向图 G=(V,E) ,生成树不同,每棵树的权(即树中所有边上的权值之和)也可能不同。设 R 是 G 的所有生成树的集合,若 T 为 R 中边的权值之和最小的那棵生成树,则 T 称为 G 的最小生成树(Minimum Spanning Tree,MST)。

不难看出,最小生成树具有如下性质:

  1. 最小生成树不是唯一的,即最小生成树的树形不唯一,R 中可能有多个最小生成树 。当图 G 中的各边权值互不相等时,G 的最小生成树是唯一的;若无向连通图 G 的边数比顶点数少 1,即 G 本身就是一棵树时,则 G 的最小生成树就是它本身 。
  2. 最小生成树的边的权值之和总是唯一的,虽然最小生成树不唯一,但其对应的边的权值之和总是唯一的,而且是最小的。
  3. 最小生成树的边数为顶点数减-1 。

构造最小生成树有很多算法,但大多数算法都利用了最小生成树的下列性质 :假设 G=(V,E) 是一个带权连通无向图, U 是顶点集 V 的一个非空子集 。若 (u,v) 是一条具有最小权值的边,其中 u ∈U,v ∈V-U ,则必存在一棵包含边 (u,v) 的最小生成树 。

基于该性质的最小生成树算法主要有 Prim 算法和 Kruskal 算法,它们都基于贪心算法的策略。对这两种算法的掌握不应拘泥于其代码实现,而应掌握算法的本质含义和基本思想,并能够手工模拟算法的具体步骤 。

下面介绍一个通用的最小生成树算法

GENERIC_MST(G) {
    T=NULL;;
    while T 未形成一棵生成树
        do 找到一条最小代价边 (u,v) 并且加入 T 后不会产生回路
            T=T(u,v)
}

通用的算法采用每次加入一条边来逐渐形成一棵生成树 。下面介绍两种实现上述通用算法的途径 。

1.1 Prim 算法

假设 N={V,E} 是连通网,ET 是 N 上最小生成树中边的集合。算法从 VT={u0} (u0∈V),ET={} 开始,重复执行下述操作:在所有 u ∈ VT,v∈V-VT 的边(u,v)∈E 中找一条代价最小的边(u0,v0)并入集合 ET,同时将 v0 并入 VT,直到 VT=V 为止。此时 ET 中必有 n-1 条边,则 T={VT,ET} 为 N 的最小生成树。

伪代码如下:

void Prim(G,T) {
	T = emptyset;                 // 初始化空树
    U = {w};                      // 添加任一顶点 w
    while((V-U) != emptyset) {    // 若树中不含全部顶点
         (u,v) 是使 uU  v(V-U),且权值最小的边;
        T = T  {(u,v)};         // 边并入树
        U = U  {v};             // 顶点归入树
    }
}

Prim 算法的时间复杂度为 O(|V|^2) (每次找点到点的最短距离),不依赖于 |E| ,因此它适用于求解边稠密的图的最小生成树。虽然采用其他方法能改进 Prim 算法的时间复杂度,但增加了实现的复杂性。

1.2 Kruskal 算法

假设 N=(V,E) 是连通网,对应的最小生成树 T=(VT,ET) ,Kruskal 算法步骤如下

初始化:VT=V,ET = emptyset 。即每个顶点构成一棵独立的树,T 此时是一个仅含 |V| 个顶点的森林。

循环(重复下列操作至 T 是一棵树):按 G 的边的权值递增顺序依次从 E-ET 中选择一条边,若这条边加入 T 后不构成回路,则将其加入 ET ,否则舍弃,直到 ET 中含有 n-1 条边 。

伪代码如下

void Kruskal(V,T) {
    T = V;      // 初始化树 T,仅含顶点
    numS = n;   // 连通分量数
    while(numS > 1) {  // 若连通分量数大于 1
         E 中取出权值最小的边 (v,u);
        if(v  u 属于 T 中不同的连通分量) {
            T=T{(v,u)};  // 将此边加入生成树中
            numS--;
        }
    }
}

根据图的相关性质,若一条边连接了两棵不同树中的顶点,则对这两棵树来说,它必定是连通的,将这条边加入森林中,完成两棵树的合并,直到整个森林合并成一棵树。

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

2. 最短路径

5.3 节所述的广度优先搜索查找最短路径只是对无权图而言的 。图是带权图时,把从一个顶点 v0 到图中其余任意一个顶点 vi 的一条路径(可能不止一条)所经过边上的权值之和,定义为该路径的带权路径长度,把带权路径长度最短的那条路径称为最短路径。

求解最短路径的算法通常都依赖于一种性质,即两点之间的最短路径也包含了路径上其他顶点间的最短路径。带权有向图 G 的最短路径问题一般可分为两类:一是单源最短路径,即求图中某一顶点到其他各顶点的最短路径,可通过经典的 Dijkstra 算法求解;二是求每对顶点间的最短路径,可通过 Floyd-Warshall 算法来求解。

2.1 Dijkstra 算法求单源最短路径问题

求带权有向图中某个源点到其余各顶点的最短路径时,最常用的是 Dijkstra 算法。该算法设置一个集合 S 记录已求得的最短路径的顶点,可用一个数组 s[] 来实现,初始化为 0,s[vi]=1 时表示将顶点 vi 放入 S,初始时把源点 v0 放入 S。此外,在构造过程中还设置了两个辅助数组:

  1. dist[] :记录从源点 v0 到其他各顶点当前的最短路径长度,dist[i] 的初值为 arcs[v0][i]
  2. path[]path[i] 表示从源点到顶点 i 之间的最短路径的前驱结点,在算法结束时,可根据其值追溯得到源点 v0 到顶点 vi 的最短路径。

假设从顶点 0 出发,即 v0=0 ,集合 S 最初只包含顶点 0,邻接矩阵 arcs 表示带权有向图,arcs[i][j] 表示有向边 <i,j> 的权值,若不存在有向边 <i,j> ,则 arcs[i][j] 为 ∞ 。Dijkstra 算法的步骤如下(不考虑对 path[] 的操作):

  1. 初始化:集合 S 初始化为 {0} ,集合 S 最初只包含顶点 0,邻接矩阵 arcs 表示带权有向图
  2. 从顶点集合 V-S 中选出 vj ,满足 dist[j]=Min{dist[i]|vi∈V-S} ,vj 就是当前求得的一条从 v0 出发的最短路径的重点,令 S=S∪{j}
  3. 修改 从 v0 出发到集合 V-S 上任一顶点 vk 可达的最短路径长度:若 dist[j]+arcs[j][k]<dist[k] ,则令 disk[k]=dist[j]+arcs[j][k]
  4. 重复 2~3 操作共 n-1 次,直到所有的顶点都包含在 S 中。

显然,Dijkstra 算法基于贪心策略。算法的主要部分为一个双重循环,外层循环内有两个并列的单层循环,任取一个循环内的操作为基本操作时,基本操作执行的总次数为双重循环执行的次数。使用邻接矩阵表示时,其时间复杂度为 O(|V|^2) 。使用带权的邻接表表示时,虽然修改 dist[] 的时间可以减少,但由于在 dist[] 中选择最小分量的时间不变,故时间复杂度仍为 O(|V|^2)

人们可能只希望找到从源点到某个特定顶点的最短路径,但这个问题和求解源点到其他所有顶点的最短路径一样复杂,时间复杂度也为 O(|V|^2) 。要找到所有结点对之间的最短距离,需要对每个结点运行一次 Dijkstra 算法,即时间复杂度为 O(|V|^3)

值得注意的是,边上带有负权值时,Dijkstra 算法并不适用。若允许边上带有负权值,则在与 S(已求得最短路径的顶点集,归入 S 内的结点的最短路径不再变更)内某点(记为 a)以负边相连的点(记为 b)确定其最短路径时,其最短路径长度加上这条负边的权值结果可能小于 a 原先确定的最短路径长度,而此时 a 在 Dijkstra 算法下是无法更新的。因此带负权值有向图的 Dijkstra 算法不一定得到正确的结果。

2.2 Floyd 算法求各顶点之间最短路径问题

求所有顶点之间的最短路径问题描述如下:已知一个各边权值均大于 0 的带权有向图,对每个顶点 vi 不等于 vj ,要求求出 vi 与 vj 之间的最短路径和最短路径长度。

Floyd 算法的基本思想是:递推产生一个 n 阶方阵序列 A^-1,A^0,…,A^k,…,A^(n-1),其中 A^k[i][j] 表示从顶点 vi 到顶点 vj 的路径长度,k 表示绕行第 k 各顶点的运算步骤。初始时,对于任意两个顶点 vi 和 vj,若它们之间存在边,则以此边上的权值作为它们之间的最短路径长度;若它们之间不存在有向边,则以 ∞ 作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点 k(k=0,1,…,n-1)作为中间顶点。若增加中间顶点后,得到的路径比原来的路径长度减少了,则以此新路径代替原路径。算法描述如下:

定义一个 n 阶方阵序列 A(-1),A(0),...A(n-1) ,其中,

A(-1)[i][j]=arcs[i][j]

A(k)[i][j]=Min{A(k-1)[i][j],A(k-1)[i][k]+A(k-1)[k][j]}, k=0,1,...,n-1

式中,A(0)[i][j] 是从顶点 vi 到 vj 、中间顶点是 v0 的最短路径的长度,A(k)[i][j] 是从顶点 vi 到 vj 、中间顶点的序号不大于 k 的最短路径的长度。Floyd 算法是一个迭代的过程,每迭代一次,在从 vi 到 vj 的最短路径上就多考虑了一个顶点;经过 n 次迭代后,所得到的 A(n-1)[i][j] 就是 vi 到 vj 的最短路径长度,即方阵 A(n-1) 中就保存了任意一对顶点之间的最短路径长度。

Floyd 算法的时间复杂度为 O(|V|^3) 。不过由于其代码很紧凑,且不包含其他复杂的数据结构,因此隐含的常数系数是很小的,即使对于中等规模的输入来说,它仍然是想当有效的。

Floyd 算法允许图中有带负权值的边,但不允许有包含带负权值的边组成的回路。Floyd 算法同样适用于带权无向图,因为带权无向图可视为有往返二重边的有向图,只要在顶点 vi 和 vj 之间存在无向边 (vi,vj) ,就可认为在这两个顶点之间存在权值相同的两条有向边 <vi,vj><vj,vi>

也可用单源最短路径算法来解决每对顶点之间的最短路径问题。每次运行时,轮流将一个顶点作为源点,并且在所有边权值均非负时,采用上面提到的 Dijkstra 算法,其时间复杂度为 O(|v|^2)·|v|=O(|V|^3)

3. 拓扑排序

有向无环图:若一个有向图中不存在环,则称为有向无环图,简称 DAG 图。

AOV 网 :若用 DAG 图表示一个工程,其顶点表示活动,用有向边 <Vi,Vj> 表示活动 Vi 必须先于活动 Vj 进行的这样一种关系,则将这种有向图称为顶点表示活动的网络 ,记为 AOV 网。在 AOV 网中,活动 Vi 是活动 VJ 的直接前驱,活动 Vj 是活动 Vi 的直接后继,这种前驱和后继关系具有传递性,且任何活动 Vi 不能以它自己作为自己的前驱或后继。

拓扑排序 :在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序:

  1. 每个顶点出现且只出现一次。
  2. 若顶点 A 在序列中排在顶点 B 的前面,则在图中不存在从顶点 B 到顶点 A 的路径。

或者定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得若存在一条从顶点 A 到顶点 B 的路径,则在排序中顶点 B 出现在顶点 A 的后面 。每个 DAG 图都有一个或多个拓扑排序序列。

对一个 DAG 图进行拓扑排序的算法有很多,下面介绍比较常用的一种方法的步骤:

  1. 从 DAG 图中选择一个没有前驱的顶点并输出。
  2. 从图中删除该顶点和所有以它为起点的有向边。
  3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的结点为止。后一种情况说明有向图中必然存在环。

伪代码如下

bool TopologicalSort(Graph G){
    // 若 G 存在拓扑序列,返回 true,否则返回 false,这时 G 中存在环
    InitStack(S);    // 初始化栈,存储入度为 0 的顶点
    for(int i=0; i < G.vexnum; i++)
        if(indegree[i]==0) 
            push(S,i);     // 将所有入度为 0 的顶点入栈
    int count = 0;  // 计数,记录当前已经输出的顶点数
    while(!IsEmpry(S)) {  // 栈不空,则存在入度为 0 的顶点
        Pop(S,i);        // 栈顶元素出栈
        print[count++] = i;  // 输出顶点 i
        for(p=G.vertices[i].firstarc;p;p=p->nextarc) {
            // 将所有 i 指向的顶点的入度减 1,并且将入度减为 0 的顶点压入栈 S
            v= p->adjvex;
            if(!(--indegree[v]))
                Push(S,v);    // 入度为 0,则入栈
        }
    }
    if(count < G.vexnum)
        return false;  // 排序失败
    else
        return true;  // 拓扑排序成功
}

由于输出每个顶点的同时还要删除以它为起点的边,故拓扑排序的时间复杂度为 O(|V|+|E|) 。此外,利用上一节的深度遍历也可实现拓扑排序,自行思考,后面习题会涉及。

用拓扑排序算法处理 DAG 图时,应注意以下问题:

  1. 入度为零的顶点,即没有前驱活动的或前驱活动都已经完成的顶点,工程可以从这个顶点所代表的活动开始或继续。
  2. 若一个顶点有多个直接后继,则拓扑排序的结果通常不唯一;但若各个顶点已经排在一个线性有序的序列中,每个顶点有唯一的前驱后继关系,再做拓扑排序时,则排序的结果是唯一的。
  3. 由于 DAG 图中各顶点的地位平等,每个顶点编号是人为的,因此可以按照拓扑排序的结果重新安排顶点的序号,生成 DAG 图的新的邻接矩阵存储表示,这种邻接矩阵可以是三角矩阵;但对于一般的图来说,若其邻接矩阵是三角矩阵,则存在拓扑序列;反之则不一定成立。

4. 关键路径

在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成该活动所需的时间),则称这种有向图为用边表示活动的网络,简称 AOE 网。

AOE 网具有以下两个性质:

  1. 只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始;
  2. 只有在进入某一个顶点的各有向边所代表的活动都已经结束时,该顶点所代表的事件才能发生。

在 AOE 网中仅有一个入度为 0 的顶点,称为开始顶点(源点),它代表整个工程的开始;网中也仅存在一个出度为 0 的顶点,称为结束顶点(汇点),它表示整个工程的结束。

在 AOE 网中,有些活动是可以并行进行的,从源点到汇点的有向路径可能有多条,并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同,但是只有所有路径上的活动都已经完成,整个工程才能算结束。因此,从源点到汇点的所有路径中,具有最大路径长度的路径称为关键路径 ,而把关键路径上的活动称为关键活动。

完成整个工程的最短时间就是关键路径的长度,即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间,即若关键活动不能按时完成,则整个工程的完成时间就会延长。因此,只要找到了关键活动,就找到了关键路径,也就可以得出最短完成时间。

下面给出在寻找关键活动时所用到的几个参量的定义。

4.1 事件 vk 的最早发生时间 vc(k)

该事件是指从开始顶点 V 到 Vk 的最长路径长度。事件的最早发生时间决定了所有从 Vk 开始的活动能够开工的最早时间。可以用下面的递归公式来计算:

ve(源点)=0

ve(k)=Max{ve(j)+Weight(vj,vk)}Weight(vj,vk) 表示 <vj,vk> 上的权值 。

注意:在计算 ve(k) 时,是按从前往后的顺序来计算的。

4.2 事件 vk 的最迟发生时间 vl(k)

该时间是指在不推迟整个工程完成的前提下,即保证它所指向的事件 vi 在 ve(i) 时刻能够发生时,该事件最迟发生的时间。可用下面的递推公式来计算。

vl(汇点)=ve(汇点)

vl(j)=Min(vl(k)-Weight(vj,vk))Weight(vj,ck) 表示 <vj,vk> 的权值

注意:在计算 vl(j) 时,是按从后往前的顺序来计算的 。

4.3 活动 ai 的最早开始时间 e(i)

该时间是指该活动的起点所代表的事件最早发生的时间。若边 <vk,vj> 表示活动 ai ,则有 e(i)=ve(k)

4.4 活动 ai 的最迟开始时间 l(i)

该时间是指该活动的终点所代表时间的最迟发生时间与该活动所需时间只差。若边 <vk,vj> 表示活动 ai ,则有 l(i)=vl(j)-Weight(vk,vj)

4.5 一个活动 ai 的最迟开始时间 l(i) 和其最早开始时间 e(i) 的差额 d(i)=l(i)-e(i)

它是指该活动完成的时间余量,即在不增加完成整个工程所需总时间的情况下,活动 ai 可以拖延的时间。若一个活动的时间余量为零,则说明该活动必须要如期完成,否则就会拖延完成整个工程的进度,所以称 l(i)-e(i)=0l(i)=e(i) 的活动 ai 是关键活动 。

求关键路径的算法步骤如下:

  1. 求 AOE 网中所有事件的最早发生时间 ve() 。(这里可以得到汇点的完成时间)
  2. 求 AOE 网中所有事件的最迟发生时间 vl() 。(从汇点往回推)
  3. 求 AOE 网中所有活动的最早开始时间 e() 。(即起点事件的最早开始时间)
  4. 求 AOE 网中所有活动的最迟开始时间 l() 。(即终点事件最迟开始时间-活动所需时间)
  5. 求 AOE 网中所有活动的差额 d(),找出所有 d()=0 的活动构成关键路径。

对于关键路径,需要注意以下几点:

  1. 关键路径上的所有活动都是关键活动,它是决定整个工程的关键因素,因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动,因为一旦缩短到一定的程度,该关键活动就可能会编程非关键活动。
  2. 网中的关键路径并不唯一,且对于有几条关键路径的网,只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。