数据结构（六）：图的概念、存储方式、基本操作、最小生成树、最短路径、有向无环图、关键路径 | Prim、Kruskal算法 | BFS、Dijkstra、Floyd算法 | 拓扑排序 | 求关键路径_数据结构最短回路关键回路简单回路基本回路

第六章 图

一、图

图

• 基本概念
• 几种特殊的图

（一）图的定义

图G由顶点集V和边集E组成，记为G = (V, E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）集合。若V = {v1, v2, ..., vn}，则用**|V|表示图G中顶点的个数**，也称图G的阶，E = {(u, v) | u∈V, v∈V}，用**|E|表示图G中边的条数**。

G: Graph

V: Vertex

E: Edge

注意：线性表可以是空表，树可以是空树，但图不可以是空，即顶点集V一定是非空集。（但边集E可以是空集）

（二）图逻辑结构的应用

例1.如全国铁路线路图

每个车站可以看作是图的顶点，车站与车站间的铁路可以看作是图的边。

V：车站，E：铁路

例2.道路的交通图

V：路口，E：道路

例3.现在一些社交软件，好友关系是基于图这种结构来保存的

例4.微博粉丝关系

可以注意到，在微信好友关系的图中，各个边是没有方向的；

而在微博粉丝关系图中，边是有方向的。

因为微信好友关系，如果你和另一个人加了好友，那么你们两个之间的好友关系肯定是相互的。但是在微博里面，你关注了一个人，是单向的关系，除非你们两个互相关注。

这就是有向图和无向图。

（三）无向图、有向图

若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为(v, w)或(w, v)，因为(v, w) = (w, v)，其中v、w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v、w相关联。

G2 = (V2, E2)

V2 = {A, B, C, D, E}

E2 = {(A, B), (B, D), (B, E), (C, D), (C, E), (D, E)}

若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v, w>，其中v、w是顶点，v称为弧尾，w称为弧头，<v, w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。

<v, w>不等于<w, v>。

G1 = (V1, E1)

V1 = {A, B, C, D, E}

E1 = {<A,B>, <A,C>, <A,D>, <A,E>, <B,A>, <B,C>, <B,E>, <C,D>}

（四）简单图、多重图

简单图——①不存在重复边；②不存在顶点到自身的边

多重图——图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。

数据结构课程只探讨“简单图”！！

（五）顶点的度、入度、出度

例如微信好友关系图，我们如何评判某人是否是“交际达人”？只需看某人这个结点，连接的边数，即可。连接的边数越多，则越有可能是一个交际达人。

例如微博粉丝关注图，如何评判某人是否是“微博大V”？只需看这个人的结点，它作为弧尾的弧有多少条，即可。

因此，无论是有向图还是无向图，讨论某个结点所联系的边或弧的条数，是很有意义的一件事。

对于无向图：

• 顶点v的度是指依附于该顶点的边的条数，记为TD(v)。

对于无向图，所有顶点的度之和为多少？

• 为2|E|。即无向图的边数的2倍。

对于有向图：

入度是以顶点v为终点的有向边的数目，记为ID(v)；

出度是以顶点v为起点的有向边的数目，记为OD(v)。

顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

如上面这张有向图，对于顶点A

ID(A) = 1

OD(A) = 4

TD(A) = 1+4 = 5

在具有n个顶点、e条边的有向图中，所有顶点的入度之和 = 出度之和 = e。

（六）顶点—顶点的关系描述

• 路径——顶点vp到顶点vq之间的一条路径是指顶点序列，vp, v1, v2, ..., vm, vq。

  • 实际上就是在一张图中，从一个顶点到另一个顶点该怎么走。
  • 无向图中，沿着边的两个不同方向走都是可以的。
  • 在有向图中，由于边是有向边，所以路径的走法也是有向的。（如A能走向E，但E不能走向A）
  • 顶点之间也有可能不存在路径。

• 回路——第一个顶点和最后一个顶点相同的路径称为回路或环。

  • 如上左图中，B,D,E,B这条路径就是一个回路。

• 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径。

  • 如上左图，若想由A走到D，则可以按照A,B,D走，也可以按照A,B,E,B,D走。

• 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

• 路径长度——路径上边的数目。

• 点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。

  • 对于无向图中，u到v的距离和v到u的距离是相等的
  • 但是在有向图中，两顶点的距离就不见得相等了

• 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。

• 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。

（七）连通图、强连通图

若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。（指的是无向图）

常见考点：

对于n个顶点的无向图G，

若G是连通图，则最少有n-1条边。

• 即n个顶点，其中一个顶点与其余n-1个顶点各有一条边的情况。

若G是非连通图，则最多可能有
$$C_{n-1}^2$$
条边。

• 即n个顶点，其中1个顶点与另外n-1个顶点是毫无连接的，而另外n-1个顶点之间两两相连。

若图中任何一对顶点都是强连通的，则称此图为强连通图。（指的是有向图）

常见考点：

对于n个顶点的有向图G，

若G是强连通图，则最少有n条边（形成回路）

（八）研究图的局部——子图

设有两个图G = (V, E)和G’ = (V’, E’)，若V’是V的子集，且E’是E的子集，则称G’是G的子图。

当然，并非任意选几个顶点、任意选几条边，都能构成一个子图。我们的子图，首先要保证它是一个图。如下面这个就不是子图。

子图首先要符合图的定义。

若有满足V(G’) = V(G)的子图G’，则称其为G的生成子图。

• 即子图包含了原图的所有顶点

以上是无向图。实际上对于有向图来说，其子图、生成子图的概念是一样的。

（九）连通分量

无向图中的极大连通子图称为连通分量。

上图右侧的三个子图即为G的三个连通分量。

它们首先都是G的子图，其次都是连通图。

而且它们还有一个特性，就是极大，就是指，这个子图当中，包含尽可能多的顶点和边。

极大连通子图，即子图必须连通，且包含尽可能多的顶点和边。

连通分量这个概念也是有很多现实意义的，比如说全国铁路线路图

这个图里面有三个连通分量——整个大陆区域的铁路图、海南岛铁路图、台湾岛铁路图。

当然，对于大陆区域的铁路图，你可以把其中长江三角区的铁路图挑出来，那么挑出来的这个图，它是一个子图，但是并不是极大连通子图。

连通分量说的是无向图的。那么对于有向图，我们说的是强连通分量。

（十）强连通分量

有向图中的极大强连通子图称为有向图的强连通分量。

上图右侧的三个子图为G的三个强连通分量。

是怎么分出来的呢？

首先对于原图中，A、B、E、C、D这几个顶点之间，它们是强连通的。那我们把这个部分挑出来，它就是一个极大强连通子图。

F或G和其他的顶点之间并不是强连通的。F、G两个顶点，需要单独作为两个极大强连通子图。

极大强连通子图，即子图必须强连通，且同时保留尽可能多的边。

（十一）生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。（这是对于无向图而言的）

也就是说，这个子图要包含原图的全部顶点，同时要保持连通，并保证边尽可能的少。

可以看到，总共有5个顶点，我们加入4条边的话，就能够让这个子图连通了，而且是极小。

如果再多加一条边的话，那这个子图就不是极小的连通子图了。

那么这样我们就构造出了原图的一个极小连通子图，或者说构造了一个生成树。

当然我们还可以有别的不同的构造方式。

所以说一个连通图的生成树，有可能会有多个。

注意：若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

（十二）生成森林

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

把连通分量的这些子图，分别转化成与之对应的生成树，就形成了原图的一个生成森林。

其实生成树和生成森林有很多意义：

例如有图上顶点那么多的村庄，这些村庄之间如果要开通公路，但是由于经费有限，不可能把所有的路都修起来，但是又想让每个村庄之间道路都连通。如何能有一个成本最低的修路方案呢。

就可以用无向图，推出所有可能的生成树。因为生成树能保证是连通的，且能保证边的数量是尽可能的少的。

于是，通过生成树，就可以初步得到若干个修路的施工方案。

但是在不同的生成树之间，选择哪种方案，能让修路的成本最低呢？

其实就要看一下每一条边，修起路来的成本到底是多少。

于是在生成树的基础上，再将各个边的成本考虑进去，就能得到一个最经济的方案。

（十三）边的权、带权图/网

可以发现，图这种数据结构，我们除了在顶点部分保存信息外，有时候也需要给各条边赋予一个数值，来表示权值。用这个数值来表示一些具有现实含义的一些信息。

如上图，是给各边赋予了一个权值——表示实际距离。

• 边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
• 带权图/网——边上带有权值的图称为带权图，也称网。
• 带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。

以上是举的无向图的例子，实际上有向图也可以有类似的，给每条边赋予一个具有现实意义的权值，如下。

比如在微博的粉丝关系当中，我们可以给各条边赋予一个权值。这个权值表示的含义是指，这个粉丝转发这个被关注者的微博的概率是多少。

总之，这个图中的边的权值，要指代什么含义，具体要看你要用这个图解决什么问题。

（十四）几种特殊形态的图

• 无向完全图——无向图中任意两个顶点之间都存在边。

  • 显然，对于n个顶点的无向图来说，任意两个顶点之间都存在边，则总边数为
    $$C_n^2$$
    条。即n(n-1)/2。

• 有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧。

  • 显然，对于n个顶点的有向图来说，任意两个顶点之间都存在两条弧，则总边数为
    $$2C_n^2$$
    条。即n(n-1)。

• 稀疏图——边数很少的图称为稀疏图。
• 稠密图——反之称为稠密图。

当然这个边是多是少并没有一个绝对的界限。

课本上给出了一个说法：一般来说|E|<|V|log|V|时，可以将G视为稀疏图。

• 树——不存在回路，且连通的无向图
  • n个顶点的树，必有n-1条边。
  • 上图中，看上去不太像一棵树，但是实际上你把它整理一下，就是一棵树。

常见考点：

n个顶点的图，若|E|>n-1，则一定有回路。

也就是在一个树里面，你任意再加一条边，则必能形成一条回路。

• 森林。

• 有向树——一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树。
  • 可以把入度为0的那个顶点（上图的顶点A）看作树中的根结点。

注意：树是对于无向图来说的，要求是连通的。有向树是对于有向图来说的，但是并不要求是强连通的。

（十五）总结

1.定义：G = (V, E)，顶点集V，边集E

2.无向图（无向边/边）、有向图（有向边/弧）

3.顶点的度、入度、出度（无向图？有向图？）

4.边的权、带权图/网

5.点到点的关系

• 路径、回路、简单路径、简单回路
• 路径长度
• 点到点的距离（最短路径）
• 无向图顶点的连通性、连通图
• 有向图顶点的强连通性、强连通图

6.图的局部

• 子图
• 连通分量——极大连通子图
• 强连通分量——极大强连通子图
• 连通无向图的生成树——包含全部顶点的极小连通子图
• 非连通无向图的生成森林——各连通分量的生成树

7.几种特殊形态的图

• 完全图
• 稠密图、稀疏图
• 树、森林、有向树

8.常见考点：

对于n个顶点的无向图G，
$$\begin{gathered} ①所有顶点的度之和=2|E| \\ ②若G是连通图，则最少有n-1条边（树），若|E|>n-1，则一定有回路 \\ ③若G是非连通图，则最多可能有C_{n-1}^2条边 \\ ④无向完全图共有C_n^2条边 \end{gathered}$$
对于n个顶点的有向图G，
$$\begin{gathered} ①所有顶点的出度之和=入度之和=|E| \\ ②所有顶点的度之和=2|E| \\ ③若G是强连通图，则最少有n条边（形成回路） \\ ④有向完全图共有2C_n^2条边 \end{gathered}$$

二、图的存储

图的存储：

• 邻接矩阵
• 邻接表
• 十字链表
• 邻接多重表

（一）邻接矩阵法

1.邻接矩阵法存储图

对于无向图，u和v之间有一条边，就意味着v和u之间有一条边。也就是无向图中的每一条边，在邻接矩阵中对应两个1。

对于有向图，它的边都是有向的。有向图中的一个弧，在邻接矩阵中对应一个1。

邻接矩阵的实现也很简单，只需要用一个二维数组就可以。

#define MaxVertexNum 100	//顶点数目的最大值
typedef struct {
    char Vex[MaxVertexNum];	//顶点表
    int Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵，边表
    int vexnum, arcnum;	//图的当前顶点数和边数
}MGraph;
1
2
3
4
5
6

此处为了列举方便，我们把各个顶点就设为char类型了，即A、B、C、D……

实际上，顶点可以设置为更复杂的类型。

对于边的存储，也可以改用bool类型或枚举型变量表示。

（int型要4或8B大小，而bool或枚举型只需要1B大小）

对于顶点表Vex[]，其每个顶点在里面是有一个下标的，

而对于每两个顶点的边表Edge[][]来说，其横轴下标和纵轴下标，又可以与顶点表中对应下标的顶点相对应上。

邻接矩阵法的严谨定义如下：

思考：如何求顶点的度、入度、出度？

对于无向图，例如求B的度，我们可以检查邻接矩阵表中B这一行的非0元素的个数。（检查B这一列的也行）

总共有三个，所以B的度应该为3。

所以对于无向图求顶点的度来说，我们可以遍历它在邻接矩阵中，那一行或那一列中，非零元素的个数。

显然，这个操作的时间复杂度为O(n)。（n为顶点的个数）或者写成O(|V|)。

对于有向图，如果要求某顶点的出度，应该对应的是这个顶点的这一行中非零元素的个数。如果要求这个顶点的入度（也就是有几条边指向它），我们应该对应的去找这个顶点的这一列中非零元素的个数。而有向图的度，等于入度+出度。

第i个结点的出度 = 第i行的非零元素个数

第i个结点的入度 = 第i列的非零元素的个数

第i个结点的度 = 第i行、第i列的非零元素个数之和

其时间复杂度也是O(|V|)

邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(|V|)

以上是讨论边不带权值的情况。那对于这种不带权的图，我们只需要表示出各个顶点之间有没有邻接的关系就可以。所以我们在矩阵当中只需要用0和1这样的两种状态来表示。

2.邻接矩阵法存储带权图（网）

那么，如果我们存放的是一个带权图，或者说是一个网的话，那其实也很简单，我们只需要在对应的位置，给它写上这两个顶点构成的这个边的权值就可以了。

#define MaxVertexNum 100	//顶点数目的最大值
#define INFINITY 最大的int值	//宏定义常量“无穷”
typedef char VertexType;	//顶点的数据类型
typedef int EdgeType;		//带权图中边上权值的数据类型
typedef struct {
    VertexType Vex[MaxVertexNum];	//顶点
    EdgeType Edge[MaxVertexNum][VexVertexNum];	//边的权
    int vexnum, arcnum;		//图的当前顶点数和弧数
}MGraph;
1
2
3
4
5
6
7
8
9

这里的类型都可以根据实际需要改成其他类型。如权值int类型，可以根据需要改为浮点类型。

其中注意，可以用int的上限值表示“无穷”。

有些时候，也会把带权图中顶点自己指向自己的那个“边”的权值记为0。

所以，在做题的时候，带权图的邻接矩阵，如果遇到两个顶点的边的权值为0或∞的时候，就表示这两个点之间不存在边。这是做题的时候可能会遇到的情况。

3.邻接矩阵法的性能分析

既然它是要用于存储，我们肯定关心这个数据结构它所需要占用的空间，空间复杂度是多少。

显然，这个图如果有n个顶点的话，那么存储顶点的信息，需要定义一个一维数组存储顶点，那么需要O(n)的空间；另外还需要定义一个二维数组来存储边，又需要O(n^2)的空间。

综上，邻接矩阵法需要的空间复杂度为O(|V|^2)——之和顶点数有关，和实际的边数无关。

也就是说，如果一个图的顶点很多，但是边数很少的话，那么把它存在邻接矩阵中，是有很多空间是被浪费了的。

所以邻接矩阵这种存储方式，比较适合用于存储稠密图，也就是边数较多的图。

另外，对于无向图的邻接矩阵来说，它是一个对称矩阵，所以我们可以利用对称矩阵的压缩存储的方法，只存储上三角区/下三角区。

4.邻接矩阵法的性质

设图G的邻接矩阵为A（矩阵元素为0/1）（注意这个A指的是整个矩阵，不是顶点A）

则A^{n的元素`An[i][j]`等于由顶点i到顶点j的长度为n的路径的数目。（A}n表示的就是矩阵A的n次方）

这是什么意思呢？

我们举个例子来看一下，例如A^2

我们挑其中的一项看一下它具有什么实际意义，如a(1,2)*a(2,4)

其中a(1,2)的意思是A到B是否有边，a(2,4)表示B到D是否有边。

因此a(1,2)*a(2,4)便表示从A到D，但是是由A经过B到D的路径的数目。

那么其他项也是从A到D，但是是经过不同顶点到D的路径的数目。

把这些乘积的项都加起来，就表示从A到D，且长度为2的路径的数目。

矩阵的乘法自己去看线性代数。

同理的计算不再列举，可以自己按照上图琢磨一下。

如果是A^3，那么原理也是类似的。

看最右侧的那个结果，其中第一行第四列的值为1，就意味着，从A到D，长度为3的路径，只有一条。

其背后的含义是什么呢？

由于这个1是前一个矩阵的第一行对应相乘后一个矩阵的第四列得到的，我们分别看这四个加项的含义。

第一项（1*0）的含义是说：从A到A且长度为2的路径有一条；而从A到D长度为1的路径有0条。

所以我们没办法把这两条路径凑起来，拼成一个更长的路径。

第二项（0*1）同理。

第三项（1*1）的含义是说：从A到C且长度为2的路径有一条；从C到D且长度为1的路径有1条。

我们把这两条路径一拼接，就能得到从A到D，且是经过C的，长度为3的路径有1条。

第四项（0*0）同理。

最后，求和之后，就能得到，由A到D，长度为3的所有路径的数目。

当然，如果想了解从数学的角度对这块内容更严谨的证明，可以去看离散数学中关于图论部分的内容。

5.总结

邻接矩阵法要点回顾：

• 如何计算指定顶点的度、入度、出度（分无向图、有向图来考虑）？时间复杂度如何？
• 如何找到与顶点相邻的边（入边、出边）？时间复杂度如何？
• 如何存储带权图？
• 空间复杂度——O(|V|^2)，适合存储稠密图
• 无向图的邻接矩阵为对称矩阵，如何压缩存储？
• 设图G的邻接矩阵为A（矩阵元素为0/1），则A^n的元素An[i][j]等于由顶点i到顶点j的长度为n的路径的数目。

（二）邻接表法

上一小节中我们学习了图的邻接矩阵法的存储方式。这种存储方式是使用数组实现的顺序存储，空间复杂度高，不适合存储稀疏图。

这一小节我们学习的邻接表，是采用顺序+链式存储的方式，来实现的。

//顶点
typedef VNode {
    VertexType data;	//顶点信息
    ArcNode *first;		//第一条边/弧
}VNode, *AdjList[MaxVertexNum];

//用邻接表存储的图
typedef struct {
    AdjList vertices;	//用顶点结点声明的一个数组
    int vexnum, arcnum;	//当前有多少个顶点、多少个边
}ALGraph;

//边/弧
typedef struct ArcNode {
    int adjvex;	//边/弧指向哪个结点
    struct ArcNode *next;	//指向下一条弧的指针
    //InfoType info;	//边权值
}ArcNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

例如，由A指向B有一条边，那么在A的*first域中，就有一个顶点号为1的结点（顶点号为1的就是B），下一个依次为2、3（即C、D顶点）。

如果我们要存的是带权图，我们可以在存放边的类型中定义权值的信息。

其实不难发现，这种邻接表法的实现，和我们之前讲的树的孩子表示法，是相同的一种实现方式。

各个结点顺序存储，然后再用一个链表来指明和这个结点相连的各个边。

上面给的例子是无向图。我们也可以用邻接表来存放有向图。

原理是类似的。有一条弧是从A指向B，所以A的后面跟了顶点号为1的结点。

实际上就是，对于有向图来说，它后面这个链域存储的信息，只是由这个顶点向外射的一些弧。

而对于无向图来说，是不分方向的一个个边。实际上，在无向图中，每一条边在邻接表中都会对应两个结点。

比如这个，0号结点（A）后存放了一个1号结点（B）；同时，1号结点（B）后面也存放了一个0号结点（A）。而这两个结点表示了同一条边。

实际上在无向图中，边的数据的存放实际是有冗余的。是实际边的数量的两倍。

边结点的数量是2|E|，整体空间复杂度为O(|V|+2|E|)。

而有向图，每一条弧，都只对应于一个边结点。所以边结点的数量为|E|。

所以空间复杂度为O(|V|+|E|)。

接下来需要探讨的一个问题是：

• 如何求顶点的度、入度、出度？
• 如何找到与一个顶点相连的边/弧。

首先来看无向图，对于无向图我们只讨论度。

如何确定一个顶点的度是多少？

• 我们只需要遍历，和这个顶点相关的这个边链表就可以。有多少个边结点，它的度就是多少。同时，这些边结点就是与这个顶点相连的边。

再来看有向图，有向图的度=入度+出度。

• 如果要找到一个顶点的出度很简单，我们只需要遍历这个结点相关的边链表就可以。同时，它也反应了从这个顶点发射出去的弧有哪些。
• 但是如果我们要找一个顶点的入度，或者是指向该顶点的弧有哪些，就有些麻烦了。
  • 比如我们要统计A结点的入度，或者要找到指向A结点的弧。那唯一的办法就是，把所有的结点的边链表，都依次地遍历一遍。是很麻烦的，时间复杂度也会很高。这是邻接表法存储有向图的一个比较大的缺点。

此外，由于在一个图中，各个边出现的先后顺序是任意的，因此图的邻接表表示方式并不是唯一的。（如A的边链表可以是1、2、3，也可以是3、2、1）

而上一小节中我们讲的邻接矩阵，只要确定了顶点编号，图的邻接矩阵表示方式就是唯一的。

（这是选择题可能会考察的一个点）

总结

（三）十字链表法

十字链表用于存储有向图

邻接矩阵的缺点是空间复杂度太高；邻接表的缺点是当它存储有向图的时候，计算入度、找入边不方便。

采用十字链表来存储一个有向图的话，就可以很好解决这两个问题。

1.十字链表法存储有向图

例如顶点A。

若要找从A射出的弧，则找A顶点结点的“绿色”部分指针，找到0→1（即A→B），而在此个弧结点的“绿色”部分指针，存放着A发出的下一条弧0→2（即A→C），下一个绿色指针为空，意味着已经没有其他从A顶点出发的弧了。

若要找进入A的弧，则找A顶点结点的“橙色”部分指针，找到2→0（即C→A），继续找该弧结点的下一个“橙色”指针，找到下一个进入A的弧3→0（即D→A），下一个橙色指针为空，意味着已经没有其他指向A顶点的弧了。

我们需要定义两个结构体：弧结点、顶点结点。

从顶点结点沿着“绿色”指针向后寻找的话，可以找到所有从该结点发射出去的弧；

从顶点结点沿着“橙色”指针向后寻找的话，可以找到所有指向该顶点的弧。

那么，使用十字链表法，我们想找到一个顶点相连的所有的边，包括出边和入边，都是很方便的。

2.十字链表法性能分析

空间复杂度：O(|V| + |E|) （顶点的个数+边的个数）

可以看到，空间复杂度和邻接表是一样优秀的，并不会像邻接矩阵那样有空间的冗余。

此外，还可以很方便的找到所有的边，包括出边和入边。

• 如何找到指定顶点的所有出边？——顺着“绿色”线路找
• 如何找到指定结点的所有入边？——顺着“橙色”线路找

注意：十字链表只用于存储有向图

（四）邻接多重表

邻接多重表用于存储无向图

如果用邻接矩阵、邻接表存储无向图。

问题是一样的。邻接矩阵的缺点是，空间复杂度太高。而邻接表存储无向图的话，主要的问题是每条边对应两份信息，信息是冗余的，导致删除顶点、删除边等操作时间复杂度高。

怎么解决这些问题呢？我们可以用邻接多重表的方式来存储无向图。

例如，A结点，顺着它的指针域寻找，能够找到0—1（即A—B）这条边，之后继续顺着“橙色”（即iLink）指针继续寻找，则能够找到0—3（即A—D）这条边，接着继续顺着”橙色“指针，发现为空，则表示没有与A相连的边了。

对于B结点，顺着它的指针，找到0—1（即A—B）这条边，可见B结点在此处存放于右侧的编号域上（实际上在左边还是在右边是没区别的），于是我们便顺着“绿色”（即jLink）指针继续寻找，继续找到2—1（同样的，B也是在右边这个位置上的），4—1（B在右边），接着继续找“绿色”结点，为空，则到此为止找到所有和B相连的边的信息。

可见，利用邻接多重表想要找到某顶点的所有边是很方便的。同时每个边只对应一份边结点的数据，因此，就不必像邻接表那样，同时维护两份冗余的数据，可以保证我们在删除一个结点或删除一条边的时候，操作会方便很多。

比如，现在我们要删除A—B这条边。这条边对应的结点是0—1这个结点。那么我们想要把这个结点删掉，并且重新改变A结点、B结点的指针域，指向这个被删除结点的下一个结点即可。那么，A结点的指针域需要顺着被删除结点的“橙色”指针，指到下一个结点上去；B结点的指针域需要顺着被删除结点的“绿色”指针，指到下一个节点上去。

比如，要删除E这个顶点。

那么除了删除E这个顶点外，还需要删除与E相连的所有边。

通过与E相连的指针，可以找到，4—1和2—4两条边。

此时需要注意，将这两个边结点删除之后，会影响到另外两个指针的指向问题。即2—1中的“1”，和2—3中的“2”的下一结点指针指向。

不过，可以看到，对于2—1的“绿色”指针，它指向4—1后便停止了，没有再指向下一个结点。因此将4—1删除后，只需修改2—1的“绿色”指针为空即可。另一个受影响的结点同理。

可以看到，采用邻接多重表来存储无向图的话，它的空间复杂度很优秀，是O(|V| + |E|)，每条边只对应一份数据。此外，删除边、删除结点等操作很方便。

注意：邻接多重表只适用于存储无向图。

总结

对于十字链表和邻接多重表，其实现方式比较复杂。所以在考研当中不太可能让大家用手写的方式来实现十字链表和邻接多重表。因此这两种实现方式，只需要理解它们的一些特性就可以。

• 十字链表用来存放有向图，可以解决在邻接矩阵中空间复杂度较高的问题，以及在邻接表中不方便查找入度、入边的问题。
• 邻接多重表用来存放无向图，可以解决邻接矩阵中空间复杂度较高的问题，以及在邻接表中存放无向图需要存放两份冗余数据，导致删除边、删除顶点操作较复杂的问题。
• 另外，对于一个给定的图，采用十字链表或是邻接多重表，表示方式都是不唯一的。

三、图的基本操作

之前的小节中，我们已经学习了图的逻辑结构，和存储结构。

在这一小节中，我们要认识数据结构三要素当中的第三个要素，也就是基本操作。

图的基本操作：

• Adjacent(G, x, y)：判断图G是否存在边<x, y>或(x, y)。
• Neighbors(G, x)：列出图G中与结点x邻接的边。
• InsertVertex(G, x)：在图G中插入顶点x。
• DeleteVertex(G, x)：从图G中删除顶点x。
• AddEdge(G, x, y)：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。
• RemoveEdge(G, x, y)：若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。
• FirstNeighbor(G, x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
• NextNeighbor(G, x, y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
• Get_edge_value(G, x, y)：获取图G中边(x, y)或<x, y>对应的权值。
• Set_edge_value(G, x, y, v)：设置图G中边(x, y)或<x, y>对应的权值为v。

此外，还有图的遍历算法，包括深度优先遍历和广度优先遍历。

（加粗的两个操作，对图的遍历算法是很有意义的操作）

那么基本操作的实现，还是和图的存储结构密不可分的。

我们说过，考研当中最常考的还是邻接矩阵和邻接表法。（因为十字链表和邻接多重表实现起来较为复杂，所以不太会考察代码的书写而只考察性质的理解）

所以在此节中，我们只探讨邻接矩阵和邻接表这两种存储结构下的基本操作。

（一）Adjacent(G,x,y)

Adjacent(G, x, y)：判断图G是否存在边<x, y>或(x, y)。

1.无向图

对于无向图，想要判断是否有边是很方便的，只需要在邻接矩阵中找到这两个顶点构成的边，对应的元素是0还是1即可。因此只需要O(1)的时间复杂度。

而对于邻接表，我们想看有没有<B, D>这条边，我们只需要看B的邻接链域中有没有3即可。最好的情况是，B的第一个链结点就是D。所以最好的时间复杂度是O(1)，而最坏的时间复杂度是，找遍所有与B连接的结点都没有发现，而和B相连的结点最多有n-1条，因此最坏时间复杂度是O(|V|)。

2.有向图

有向图和无向图原理是一样的，此处不再赘述。

（二）Neighbors(G,x)

Neighbors(G, x)：列出图G中与结点x邻接的边。

1.无向图

在邻接矩阵中，如果想要找到和某顶点相邻的所有的边，那么只需要遍历和它对应的矩阵当中的这一行（或者这一列），看看哪一处是1，把这些为1的边给罗列出来就可以。时间复杂度是O(|V|)。

在邻接表中，由于当前我们存储的是无向图，所以只需要遍历和它相连的边结点链表就可以。最好的情况是O(1)（只连了一个边，甚至一个边都没有），最坏的情况是连接了n-1个边，最坏时间复杂度O(|V|)。

2.有向图

如果存储的是有向图，邻接矩阵中是类似的，如果要找到和某个顶点相连的边，想要找出边的话，只需要遍历和它对应的矩阵中的行；要找它的入边，只需要遍历和它对应的矩阵中的列。时间复杂度是O(|V|)。

如果是邻接表，要找出边，和刚才是一样的，只需要遍历和它相连的链表就可以。

而如果要找指向当前结点的入边的话，我们就得遍历整个邻接表所有的边结点。而整个邻接表的边数为|E|，因此其时间复杂度为O(|E|)。

（三）InsertVertex(G,x)

InsertVertex(G, x)：在图G中插入顶点x。

1.无向图

在邻接矩阵中，刚开始插入这个结点的时候，它和其他所有结点都是还没有相连接的，所以只需要在节点数组中加一位，邻接矩阵的行和列各加一位即可。

看似需要对大量数位进行置0操作，但实际上这些0，在你的矩阵空间初始化的时候就已经做好了，你只需要将下标进行一位的扩展即可完成。因此该操作的时间复杂度为O(1)。

对于邻接表，由于新插入的结点还没有任何边，所以将它的邻接域设为空即可。

2.有向图

对于有向图是类似的。此处不再赘述。

（四）DeleteVertex(G,x)

DeleteVertex(G, x)：从图G中删除顶点x。

1.无向图

例如我们要删除C这个结点。

那么在删除C这个结点之后，我们要将它在邻接矩阵中对应的行、列都清空。（不仅是置为0的问题，而是这一整行、一整列直接被删掉没有了）

那么我们需要把C之后的结点都向前移一位。并且邻接矩阵需要重新拼接一下。

这就意味着有大量的元素需要移动，而移动这么多的元素，需要的开销是很大的。所以这种方案不太科学。

那怎么办呢？

其实我们只需要将这一顶点对应的一整行、一整列数据置为0即可，而在存放结点的数组中新增一个bool类型属性，用来表示该结点是否为被删除过的结点即可。

用这种方式来实现删除，显然要比移动大量的元素要好很多。由于只需要修改一行或一列的数据，所以时间复杂度为O(|V|)。

而对于邻接表，我们需要删除其邻接链域中的所有结点，并将邻接链域置为空。此外，由于这是无向图，每个边是有两份数据的。因此我们还需要遍历所有其他所有边结点，看看是否有与之连接的边并删除。

其最好的时间复杂度为O(1)，最坏的时间复杂度为O(|E|)。

2.有向图

对于有向图，邻接矩阵法，删除的方法是一样的。

对于邻接表法，若要删出边，我们只需要删除从该顶点往外发射的边，很方便，只需要把它的边链域中的所有结点删除就可以，所以它的时间复杂度最好为O(1)、最坏为O(|V|)。而若要删入边，则我们需要遍历所有的边结点，看看哪些是指向它的入边，并删除，所以它的时间复杂度是O(|E|)。

（五）AddEdge(G,x,y)

AddEdge(G, x, y)：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。

1.无向图

那么对于无向图来说，邻接矩阵法只需要O(1)的时间复杂度。

对于邻接表法，例如我们想要添加C和F之间的一条边，我们需要在C的边结点链表后添加F结点，并且在F的边结点链表后添加C结点。（这是尾插法）这是添加到链表的尾部，其实也可以添加到链表的头部。若采用头插法，则只需要O(1)的时间复杂度。

2.有向图

是类似的，不再赘述。

（六）FirstNeighbor(G,x)

FirstNeighbor(G, x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。

1.无向图

对于无向图来说，邻接矩阵法，只需要看C结点这一行（或列）的第一个1在哪即可。最好时间复杂度为O(1)，最坏为O(|V|)。

对于邻接表法来说，就更简单，只需要找到它边结点链表中的第一个结点即可。只需要O(1)的时间复杂度。

2.有向图

对于有向图来说，邻接矩阵法，若要找出边，则只需要看该顶点在这一行的第一个1在哪里即可；若要找入边，则只需要看该顶点这一列的第一个1在哪里即可。

对于邻接表法，若要找出边，很容易，同上，即找边结点链表中的第一个结点。而若要找入边，就有些麻烦了，需要遍历所有的边结点。

（七）NextNeighbor(G,x,y)

NextNeighbor(G, x, y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。

1.无向图

对于无向图来说，邻接矩阵法，只需要找到该邻接点之后，继续往后遍历找到下一个1为止，即找到了下一个邻接点。

对于邻接表法，只需要找该边结点链域的下一个结点即可。

2.有向图

略。

（八）Get/Set_edge_value

• Get_edge_value(G, x, y)：获取图G中边(x, y)或<x, y>对应的权值。
• Set_edge_value(G, x, y, v)：设置图G中边(x, y)或<x, y>对应的权值为v。

实际上这两个操作，其实际需要花费开销的操作，还是在于找到那条边/弧。

实际上还是Adjacent(G,x,y)这一操作。

Adjacent(G, x, y)：判断图G是否存在边<x, y>或(x, y)。

这两个操作，和找边的时间开销是一样的，思路也是一样的。此处不再赘述。

四、图的遍历

• 广度优先遍历（BFS）
  • 与树的广度优先遍历之间的联系（因为树就是一种特殊的图）
  • 算法实现
  • 复杂度分析
  • 广度优先生成树
• 深度优先遍历（DFS）
  • 与树的深度优先遍历之间的联系
  • 算法实现
  • 复杂度分析
  • 深度优先生成树
  • 图的遍历和图的连通性

（一）广度优先遍历

1.回顾树的广度优先遍历（层序遍历）

对于和每个结点相连的结点，进行尽可能横向足够广的依次遍历。

首先，找到1号结点。其次找到与之相连的2、3、4结点。

由2、3、4结点，找到5、6、7、8号结点。

2.图的广度优先遍历

对于图也是类似的。比如我们从2号结点出发，开始进行图的广度优先遍历。

那同样地，首先我们找到2号结点。然后，找到与之相连的1、6号结点。

再由1、6出发，找到与它们相连的5、3、7号结点。

接着，再由5、3、7号结点，找到它们更下一层的结点，4、8。

3.树vs图

图的广度优先遍历，这个过程其实和树的广度优先是很类似的。我们看看有什么联系和区别。

首先，不论是树还是图的广度优先遍历，我们都需要实现这样一个操作，就是通过某一个结点，找到与之相邻的其它结点。因为只有实现了这个操作，我们才有可能一层一层的往下找到所有的结点。

对于树来说，找到与之相邻的其他结点，其实就是找它的孩子结点。而对于图来说，我们可以利用之前学过的两个基本操作来完成这件事情。

另外，对于树来说，是不存在“回路”的，搜索相邻的结点时，不可能搜到已经访问过的结点。而对于图来说，搜索相邻的结点时，有可能搜索到已经访问过的顶点，所以我们需要对这一问题进行处理，而处理起来也很简单， 我们只需要对每个结点进行一个标记来表示有没有被访问过就可以了。

4.代码实现

树的广度优先遍历（层序遍历）：

①若树非空，则根结点入队

②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

③重复②直到队列为空

图的广度优先遍历（Breadth-First-Search，BFS）要点：

• 找到与一个顶点相邻的所有顶点

  • 通过两个基本操作，FirstNeighbor(G,x)找到指定顶点的第一个邻接点；NextNeighbor(G,x,y)找到后一个邻接点。那么，通过这两个操作，就可以找到与一个顶点相邻接的所有的顶点。（当然，通过邻接矩阵法，和通过邻接表法，其操作实现起来是有所区别的）

• 标记哪些顶点被访问过

  • 定义一个数组bool visited[MAX_VERTEX_NUM];来标记每个顶点到底有没有被访问过就可以了

• 需要一个辅助队列

bool visited[MAX_VERTEX_NUM];	//访问标记数组

//广度优先遍历
void BFS(Graph G, int v) {	//从顶点v出发，广度优先遍历图G
    visit(v);		//访问初始顶点v
    visited[v] = TRUE;	//对v做已访问标记
    Enqueue(Q, v);	//顶点v入队列Q
    while(!isEmpty(Q)) {
        DeQueue(Q, v);	//顶点v出队列
        for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            //检测v所有邻接点
            if(!visited[w]) {	//w为v的尚未访问的邻接顶点
                visit(w);	//访问顶点w
                visited[w] = TRUE;	//对w做已访问标记
                EnQueue(Q, w);	//顶点w入队列
            }//if
        }//for
    }//while
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

其中，对于visited[]数组，刚开始我们把它全部设为false，并且数组的下标和各个结点的编号是一一对应的。（此处为了与顶点编号对应，数组的0号下标弃置不用）

对于上图：

从顶点2出发得到的广度优先遍历序列：2 1 6 5 3 7 4 8

从顶点1出发得到的广度优先遍历序列：1 2 5 6 3 7 4 8

从顶点3出发得到的广度优先遍历序列：3 4 6 7 8 2 1 5

每一“层”的顶点，应该按照什么样的一个顺序？

实际上，这要看是按照什么存储结构来存储的。

• 如果是用邻接表存储的，由于每个顶点后面的链表中，结点的顺序是不确定的，所以顺序不确定。这个遍历序列是可变的，是不唯一的。

  • 即：同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一。

• 如果是用邻接矩阵存储的，由于遍历某顶点的所有边，是按照该结点在矩阵中对应行的一个从左向右的遍历，所以遍历出来的序列应该是按照由小到大的一个递增的顺序。（一定是这样的）这个遍历序列是唯一的。

  • 即：同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一。

5.算法存在的问题

至此，我们发现一个问题。

刚刚对于图的广度优先遍历，无论是从哪个顶点出发，都是能够遍历到图中所有顶点的。

这是因为它是一个连通图。

如果是非连通图，则无法遍历完所有结点。

对于一个非连通图来说，通过刚才的代码。例如从2号结点出发，就没有办法访问到9、10、11三个结点。

怎么解决？

我们不是定义了一个visited[]数组吗，这个数组记录了所有顶点是否已经被访问的信息。那么当我们在第一次调用BFS这个函数遍历完毕之后，可以检查一下在visited数组当中能否找到值为false的顶点，如果能找到，那么从这个顶点出发，再次调用BFS这个函数，就可以了。

BFS算法（最终版）

bool visited[MAX_VERTEX_NUM];	//访问标记数组

void BFSTraverse(Graph G) {		//对图G进行广度优先遍历 
	for(i=0; i<G.vexnum; ++i) {
		visited[i] = FALSE;	//访问标记数组初始化 
	}
	InitQueue(Q);	//初始化辅助队列Q
	
	for(i=0; i<G.vexnum; ++i) {	//从0号结点开始遍历（如果是1号开始的就从1开始）
		if(!visited[i]){	//对每个连通分量调用一次BFS 
			BFS(G, i);	//v[i]未访问过，从v[i]开始再做一次BFS 
		}
	}
}

//广度优先遍历
void BFS(Graph G, int v) {	//从顶点v出发，广度优先遍历图G
	visit(v);	//访问初始顶点v
	visited[v] = TRUE;	//对v做已访问标记
	Enqueue(Q, v);	//顶点v入队列Q
	while(!isEmpty(Q)) {
		DeQueue(Q, v);	//顶点v出队列
		for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
			//检测v所有邻接点
			if(!visited[w]) {	//w为v的尚未访问的邻接顶点 
				visit(w);	//访问顶点w
				visited[w] = TRUE;	//对w做已访问标记
				EnQueue(Q, w);		//顶点w入队列 
			}//if
		}//for
	}//while
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

到此，我们就可以遍历完非连通图里的所有结点。

此外，对于无向图，调用BFS函数的次数 = 连通分量数。

6.复杂度分析

对于空间复杂度来说，其关键是要看辅助队列所需要的空间大小。

再看时间复杂度。在这个BFS算法中，我们首先要visit(v)这个顶点，其次对于每个顶点，我们还需要探索其所有的边。所以我们可以简要的认为，它的时间开销主要用于，探索每个顶点，和探索每条边。

对于邻接矩阵法存储的无向图来说：

对于邻接表法存储的无向图来说：

可以看出，这个算法的时间复杂度的分析，并不是单纯地看最深层循环的次数。

而是看关键代码的次数。这个算法的关键代码在于visit(v)，和深层for循环，两者兼具（访问顶点+找各条边）。

这是由问题的实际过程考虑得出的，而不要一味地只顾最深层循环。

7.广度优先生成树

标红的这些边，表示这个结点在被访问的时候，是由哪条边过去的。

例如4号结点，在被访问到的时候，是由3号结点过去的，而不是由7或8过去的。

对于这个n个结点的图来说，我们总共标红了n-1条边。如果把其余的那些边去掉，那么这个图其实就变成了树，因为它里面已经没有回路存在了。

那么这就是这个图的广度优先生成树。

这个生成树是由广度优先遍历，遍历的顺序得来的。

注意其中遍历序列的顺序。例如，由6得来的结点，有3、7，但是要注意在这个实际存储当中，是3在前、7在后的。

而，如果按照下面的存储，那么生成树中的次序也会随之改变，如下。

可以看到，两棵广度优先生成树，是有区别的。

广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一。

但是如果一个图是用邻接矩阵来存储的，那么它的广度优先生成树肯定也是唯一的了。

8.广度优先生成森林

对非连通图的广度优先遍历，可以得到广度优先生成森林。

很好理解，对于其中的每一个连通分量，都能得到一个广度优先生成树。

这两棵树放在一起，就可以组成一个广度优先生成森林。

9.练习：有向图的BFS过程

把刚才的例子由无向图改成有向图。

思考：

• 从1出发，需要调用几次BFS函数？
• 从7出发，需要调用几次BFS函数？

（代码实现和刚才的代码是一模一样的）

从1出发，肯定只能遍历到5。那么显然需要再次调用BFS函数。之后的过程可以自己思考一下。

如果从7号出发（或8号），由于从它出发，可以找到有向图中所有的结点，因此从它出发进行BFS，肯定只用一次就够了。

10.总结

图的BFS：

• 类似于树的层序遍历（广度优先遍历）
• 算法要点
  • 需要一个辅助队列
  • 如何从一个结点找到与之邻接的其他顶点
  • visited数组防止重复访问
  • 如何处理非连通图
• 复杂度
  • 空间复杂度：主要来自于辅助队列，O(|V|)
  • 时间复杂度
    • 访问结点的时间 + 访问所有边的时间
    • 邻接矩阵：O(|V|^2)
    • 邻接表：O(|V| + |E|)
• 广度优先生成树
  • 由广度优先遍历确定的树
  • 邻接表存储的图表示方式不唯一，因此遍历序列、生成树也不唯一
  • 遍历非连通图可以得到广度优先生成森林

（二）深度优先遍历

1.树的深度优先遍历

//树的先根遍历
void PreOrder(TreeNode *R) {
    if(R!=NULL) {
        visit(R);	//访问根结点
        while(R还有下一个子树T) {
            PreOrder(T);	//先根遍历下一棵子树
        }
    }
}
1
2
3
4
5
6
7
8
9

先根遍历序列：1 2 5 6 3 4 7 8

同样也有个问题。对于树来说，新找到的相邻结点一定是没有访问过的。但是对于图就不一样了，与之相邻的其他结点有可能是已经被访问过的。

2.图的深度优先遍历

bool visited[MAX_VERTEX_NUM];	//访问标记数组（初始都为false）

void DFS(Graph G, int v) {	//从顶点v出发，深度优先遍历图G
    visit(v);	//访问顶点v
    visited[v] = TRUE;	//设已访问标记
    for(w = FirstNeighbor(G,v); w>=0; w = NextNeighbor(G,v,w)) {
        if(!visited[w]){	//w为v的尚未访问的邻接顶点
            DFS(G,w);
        }//if
    }//for
}
1
2
3
4
5
6
7
8
9
10
11

如果由2号顶点出发。

2号顶点有子树1，则访问1号，1号还有子树5，则继续访问5号。

5号执行结束没有子树，则返回到1号结点，1号没有其他子树，则返回到2号顶点。

找到2号顶点的下一个邻接点，即6号顶点。

和6号相邻的，访问3号结点，接着访问4号顶点，接着访问7号结点，接着访问8号顶点。

8号执行完后，由于与之相邻的所有顶点都已经被访问过，因此可以结束执行，向上返回，一路返回到最上层。最终整个函数执行完毕。

从2出发的深度遍历序列：2 1 5 6 3 4 7 8。

这段代码也存在类似的问题，就是，如果是非连通图，则无法遍历完所有结点。

处理的方法类似。

我们在进行了一次DFS后，还可以扫描一次visited[]数组，如果在这个数组中发现了有某一个元素，它依然是false，那么就说明与之相对应的顶点是没有被访问过的，那么我们再从这个顶点出发再调用一次DFS函数就可以了。

3.代码实现

bool visited[MAX_VERTEX_NUM];	//访问标记数组

void DFSTraverse(Graph G) {		//对图G进行深度优先遍历
    for(v=0; v<G.vexnum; ++v) {
        visited[v] = FALSE;		//初始化已访问标记数据
    }
    for(v=0; v<G.vexnum; ++v) {	//本代码中是从v=0开始遍历（也可以从1开始）
        if(!visited[v]) {
            DFS(G, v);
        }
    }
}

void DFS(Graph G, int v) {	//从顶点v出发，深度优先遍历图G
    visit(v);	//访问顶点v
    visited[v] = TRUE;	//设已访问标记
    for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)) {
        if(!visited[w]) {	//w为v的尚未访问的邻接顶点
            DFS(G,w);
        }//if
    }//for
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.复杂度分析

空间复杂度

空间复杂度：来自函数调用栈（由于这个算法是递归调用的）。

最坏情况，递归深度为O(|V|)。

• 即，从1号顶点出发进行深度优先遍历，一直遍历到8号，才能发现其没有继续的子树，才能结束DFS并依次返回。那么此时函数调用栈中存放了8层递归。

最好情况，O(1)。

• 找到一个子树就结束DFS并返回上级。那么我们的递归调用栈只会有2层。

时间复杂度

广度优先和深度优先，都可以把代码的时间开销简化为访问各结点+探索各条边的时间开销。

无论是广度优先还是深度优先，其时间复杂度都是分为邻接矩阵和邻接表两种存储方式讨论的。

邻接矩阵存储的图：

• 访问|V|个顶点需要O(|V|)的时间
• 查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点
• 时间复杂度=O(|V|^2)

邻接表存储的图：

• 访问|V|个顶点需要O(|V|)的时间
• 查找各个顶点的邻接点共需要O(|E|)的时间
• 时间复杂度=O(|V|+|E|)

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一。

同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一。

5.深度优先生成树

和广度优先生成树类似。

把我们深度优先遍历，某结点是由一个结点的邻接访问过来的，把这些边标红，如图所示。把没有标红的边去掉，就成了一棵树。

当然，同一个图的邻接矩阵表示方式唯一，深度优先生成树也唯一；邻接表表示方式不唯一，因此得到的深度优先生成树也不唯一。

6.深度优先生成森林

如果一个图是非连通的，也就是说我们需要调用多次DFS函数，那么每调用一次，就会生成一棵深度优先生成树。

像这个无向图，总共有两个连通分量，因此总共需要调用两次DFS函数。因此也会对应的生成两棵深度优先生成树。

这两棵树就组成了深度优先生成森林。

7.总结

图的DFS：

• 算法要点
  • 递归地深入探索未被访问过的邻接点（类似于树的先根遍历的实现）
  • 如何从一个结点找到与之邻接的其他顶点
  • visited[]数组防止重复访问
  • 如何处理非连通图
• 复杂度分析
  • 空间复杂度，来自递归工作栈，O(|V|)
  • 时间复杂度，访问结点的时间+访问所有边的时间
    • 邻接矩阵：O(|V|^2)
    • 邻接表：O(|V|+|E|)
• 深度优先生成树
  • 由深度优先遍历确定的树
  • 邻接表存储的图表示方式不唯一，深度优先遍历序列、生成树也不唯一
  • 深度优先遍历非连通图可得深度优先生成森林
• 图的遍历和图的连通性
  • 无向图，DFS/BFS函数调用的次数=连通分量数
  • 有向图
    • 若从起始顶点到其他顶点都有路径，则只需调用1次BFS/DFS函数
    • 对于强连通图，从任一顶点出发都只需调用1次DFS/BFS函数

（三）图的遍历与图的连通性

1.无向图

对无向图进行BFS/DFS遍历，调用BFS/DFS函数的次数 = 连通分量数。

对于连通图，只需调用一次BFS/DFS。

2.有向图

对有向图进行BFS/DFS遍历，调用BFS/DFS函数的次数要具体问题具体分析。

若起始顶点到其他各顶点都有路径，则只需调用一次BFS/DFS函数。

对于强连通图，即从任一顶点都有到达其他任一顶点的路径，那么从任一结点出发都只需调用一次BFS/DFS函数。

五、最小生成树（最小代价树）

• 最小生成树的概念
• Prim算法
• Kruskal算法

（一）概念

之前我们已经学过什么是生成树。

连通图的生成树是包含图中全部顶点的一个极小连通子图。

若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

就在上一小节，我们也介绍了，广度优先生成树和深度优先生成树。

而此处我们要学的是最小生成树（最小代价树）。

来看一个问题：

道路规划要求：所有地方都连通，且成本尽可能的低。

比如我们先随便想出来了两种方案，如下

左边这种方案可以使所有地方都连通，是19块钱；右边的也可以都连通，代价是16块钱。

那么，还有没有更便宜的修路方案？

实际上，一个图有多个生成树。我们就是要在所有的生成树中，找出各边的权值之和，也就是代价最小的那棵生成树。

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

• 最小生成树可能有多个，但边的权值之和总是唯一且最小的。
• 最小生成树的边数 = 顶点数 - 1。砍掉一条则不连通，增加一条边则会出现回路。

• 如果一个连通图本身就是一棵树（也就是各点连通，且没有回路），则其最小生成树就是它本身。
• 只有连通图才有生成树，非连通图只有生成森林。

最小生成树，我们研究的对象是带权连通无向图。带权的、连通的、无向图。

求最小生成树：

• Prim算法
• Kruskal算法

（在考研中，这两个算法的代码考察概率不高，所以我们此处只是手动的理解它的实现过程）

（二）Prim算法（普里姆）

Prim算法（普里姆）：

从某一顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

（这个逻辑用手算执行的话，其实是很简单的了）

对于上图，利用Prim算法的执行过程为：

• 由P城开始构建生成树。此时，代价最小的新顶点纳入树中，应该是将学校纳入树中（1最小）。
• 接下来，若要继续纳入新顶点，则所有代价中，代价为4的是最小的，所以可以把矿场或者渔村纳入树中。我们先把矿场连进去。
• 接下来，若要把新结点连到这棵树里，最小的代价应该是2。即矿场—渔村这条边。于是把渔村连进去。
• 接下来，连入新结点代价最小的是P城—农场，代价为5。
• 最后，连入农场—电站，代价为3。

红色的边即为最小生成树的边。此时，可知最小代价为15。

那么，在连入矿场或者渔村时，由于两边权值均为4，刚刚我们选择了先连矿场。

如果先连渔村会如何，过程略。

最终我们得到了两个不同的最小生成树。

也就是我们刚才说的，同一个图可能有多个最小生成树，但是这些最小生成树虽然形态不同，但所有边的权值之和是唯一且相同的。

刚刚我们是从P城开始构建生成树的。现在我们换一个起始结点，看看结果如何。

例如从农场开始。

• 农场——电站（3）
• 农场——P城（5）
• P城——学校（1）
• P城——矿场（4）
• 矿场——渔村（2）

其最小代价也是15。

（三）Kruskal算法（克鲁斯卡尔）

Kruskal算法（克鲁斯卡尔）：

每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）。

直到所有结点都连通。

• 我们挑出所有边中权值最小的边，就是1这条边（P城——学校），这条边的两头连通了吗？没有。那么连上；
• 再从剩下的所有边当中挑选出权值最小的边，就是2这条边（渔村——矿场），这条边的两头连通了吗？没有。那么连上；
• 之后，权值最小的边应该是3这条边（农场——电站），这条边的两头连通了吗？没有。那么连上；
• 之后，权值最小的边应该是4（P城——矿场或者P城——渔村），我们选P城——矿场，这条边的两头连通了吗？没有。那么连上；
• 之后，剩余的所有边当中，权值最小的应该是4（P城——渔村），但由于这条边的两头已经连通了（即P城——矿场——渔村），所以我们跳过这条边不考虑。
• 那么权值最小的应该是5，有农场——P城，也有学校——矿场。但是由于学校、矿场这两个结点已经连通了（即学校——P城——矿场），所以也不考虑。因此，将P城——农场连起来。
• 到此为止，所有结点都已经连通了。

最小代价也是15。

（四）Prim算法 v.s. Kruskal算法

Prim算法（普里姆）：

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

时间复杂度：O(|V|^2)。

适合用于边稠密图，也就是|E|较大的场景。

Kruskal算法（克鲁斯卡尔）：

每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）；直到所有结点都连通。

时间复杂度：O(|E|log₂|E|)。

适合用于边稀疏图，也就是|E|较小的场景。

（五）代码实现（思想）

1.Prim算法

从v0开始。

• 由于当前树中只有v0，所以isJoin数组中只有v0是TRUE，其他为FALSE。此外，lowCost中的各个结点加入树的最低代价，是看从v0出发，加入各个结点的最低代价。

• 第1轮：循环遍历所有结点，找到lowCost最低的，且还没加入树的顶点。于是将v3加入树。

• 此时，由于v3的加入，isJoin数组中v3也是TRUE。且，此时lowCost中的各个结点加入树的最低代价，不止是看由v0出发的边，而是也要看v3出发的边，因此lowCost数组应该更新。

• 第2轮：和第1轮是一模一样的。循环遍历所有结点，找到lowCost最低的，且还没加入树的顶点。因此我们会把v2加入到树里面。并同时需要把lowCost数组的内容重新更新。

• 第3轮：同理。把v5加入。并且更新lowCost。
• 第4轮：同理。把v1加入。并且更新lowCost值。
• 第5轮：只剩下v4。所以再把v4加入。

由v0开始，总共需要n-1轮处理。

每一轮处理：循环遍历所有结点，找到lowCost最低的，且还没加入树的顶点。接着，再次循环遍历，更新还没加入的各个顶点的lowCost值。（所以每一轮的时间复杂度为O(2n)）。

所以总的时间复杂度的数量级为O(n^2)，也就是O(|V|^2)。

算法的大致执行就是这样的。有能力的可以自己动手实现一遍。但是对于考研初试阶段来说我们可以先不展开此处代码的编写。

2.Kruskal算法

由于这个算法每次要选择权值最小的一条边。所以我们要做这样的一个预处理，就是要先把各条边按照权值递增的顺序做一个排序。那么这个算法的执行，就是要把所有的这些边都检查一遍。

• 第1轮：检查第1条边的两个顶点是否连通（是否属于同一个集合）。将v0——v3连起来。

  • 进行这个判断实际上是用到了并查集，并查集相关的内容由于在408中不要求掌握，我们只是大概说一下。
  • 我们首先把不同的顶点看作一个个不同的集合。那么v0和v3刚开始是从属于不同的集合的。也就意味着它们此时不连通。那么我们就可以把这条边给选上。
  • 同时，如果把这两个顶点给连上的话，那么这两个顶点此时就变成了同一个集合。

• 第2轮：检查第2条边的两个顶点是否连通（是否属于同一个集合）。将v2——v5连起来。

• 第3轮：检查第3条边的两个顶点是否连通（是否属于同一个集合）。将v1——v4连起来。

• 第4轮：检查第4条边的两个顶点是否连通（是否属于同一个集合）。将v2——v3连起来。

• 第5轮：检查第5条边的两个顶点是否连通（是否属于同一个集合）。由于已连通，则跳过。

• 接下来的过程省略，总之我们需要把所有边都遍历一遍。在遍历到每条边的时候我们都要判断，这条边的两个顶点，它们是否从属于同一个集合。如果不属于一个集合，那就把这条边选上。

整个图里，总共有|E|条边。

那么这个算法总共要执行|E|轮。

每轮判断两个顶点是否属于同一集合，需要O(log₂|E|)。（需要用到并查集）。

总时间复杂度为O(|E|log₂|E|)。

其实Prim算法还可以优化一下。有兴趣的可以去看一看《算法导论》这本书。

六、最短路径

（一）最短路径问题

“G港”是个物流集散中心，经常需要往各个城市运东西，怎么运送距离最近？——单源最短路径问题

比如G港到Y城，可以选择G港——R城——Y城，也可以选择G港——P城——Y城，但是有长有短。

所谓“单源”，就是指从一个源头出发，到各个结点的最短路径是多少。

各个城市之间也需要互相往来，相互之间怎么走距离最近？——每对顶点间的最短路径

比如R城和M城之间，走哪条路比较近？Y城和P城之间，走哪条路比较近？

最短路径问题

• 单源最短路径
  • BFS算法（无权图）
  • Dijkstra算法（带权图、无权图）
• 各顶点间的最短路径
  • Floyd算法（带权图、无权图）

（二）BFS求无权图的单源最短路径

注：无权图可以视为一种特殊的带权图，只是每条边的权值都为1。

对这个图执行一次广度优先遍历，我们就可以得到由某个源点出发，到其他各个结点的最短路径。

代码实现：

先看BFS算法。

bool visited[MAX_VERTEX_NUM];	//访问初始数组

//广度优先遍历
void BFS(Graph G, int v) {
    visit(v);
    Enqueue(Q,v);
    while(!isEmpty(Q)) {
        DeQueue(Q,v);
        for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)) {
            if(!visited[w]) {
                visit(w);
                visited[w] = TRUE;
                EnQueue(Q,w);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

我们要通过BFS算法来求单源最短路径，那么主体框架不变，对其中的一些地方的处理进行一些改变就可以。如下。

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u) {
    //d[i]表示从u到i结点的最短路径
    for(i=0; i<G.vexnum; ++i) {
        d[i] = ∞;	//初始化路径长度
        path[i] = -1;	//最短路径从哪个顶点过来
    }
    d[u] = 0;
    visited[u] = TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q)) {	//BFS算法主体过程
        DeQueue(Q,u);	//队头元素u出队
        for(w=FirstNeighbor(G,u); w>=0; w=NextNeighbor(G,u,w)) {
            if(!visited[w]) {		//w为u的尚未访问的邻接点
                d[w] = d[u] + 1;	//路径长度+1
                path[w] = u;		//最短路径应从u到w
                visited[w] = TRUE;	//设已访问标记
                EnQueue(Q,w);	//顶点w入队
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

就是对BFS算法的小修改。

在visit一个顶点时，修改其最短路径长度d[]并在path[]记录前驱结点。

可以看出。2到8的最短路径长度 = d[8] = 3

通过path数组可知，2到8的最短路径为：8<--7<--6<--2

之前也说到，通过广度优先遍历，能够得到广度优先生成树。那么也可以观察一下这个广度优先生成树：

这个生成树，它的每个结点在第几层，也直接地反映了从根结点2，到达它的最短路径是多少。

不难得知，通过广度优先遍历构造出的这个广度优先生成树，它的高度一定是最小的。

（三）Dijkstra算法

迪杰斯特拉（1930~2002），1972年图灵奖得主。

在408的许多考点中，都有他的研究成果：

• 提出“goto有害理论”——操作系统，虚拟存储技术，5分
• 信号量机制PV原语——操作系统，进程同步，15分
• 银行家算法——操作系统，死锁
• 解决哲学家进餐问题——操作系统，死锁，15分
• Dijkstra最短路径算法——数据结构大题、小题，10分

1.BFS算法的局限性

BFS算法的局限性：

BFS算法求单源最短路径只适用于无权图，或所有边权值都相同的图。

2.Dijkstra算法

• 带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。

这里以有向图举例。为什么不用无向图呢，因为无向图的边等价于两条有向边，是一样的道理。我们只需要说清楚有向图的原理，无向图自然也就清楚了。

由v0作为源点出发。

我们需要设三个数组

• final数组，表示各顶点是否已找到最短路径。显然先设v0为TRUE。
• dist数组（distance），表示目前已知条件下，到达某结点的最短路径长度。
  • 此时只有一个v0是可知的，那么目前来看，到v1的最短路径是10，到v4的最短路径是5，而到v2和v3是∞。
• path数组，和BFS算法中的path数组是一个意思，就是记录通往结点的路径是由哪个结点过来的，也就是最短路径上的前驱结点。
  • v1结点目前能找到的最好的一条路径，是从v0过来的，那么path设为0。v4同理。

以上是三个数组的初始化，接下来我们开始一轮一轮的处理。

第一轮：

循环遍历所有结点，找到还没确定最短路径，且dist最小的顶点Vi，令final[i] = TRUE。

• 那么显然，在V1~V4中，dist最小的顶点是V4的5。并将V4的final设为TRUE。也就是说，我现在已经可以确定V4的最短路径长度就是5，并且它的直接前驱是0号结点。

检查所有邻接自Vi的顶点，若其final值为false，则更新dist和path信息。

• 也就是检查V1~V3，看看它们如果由V4过来的话，有没有可能比之前的路径更短。
  • 对于V1：如果改用从V4过来，那么总长度为5+3=8，比原先的10更短，则更新。
  • 对于V2：原先我们根本就没有到达V2的路径，现在如果我们从V4出发，则有一条到V2的路径，则更新。
  • 对于V3：和V2同理，更新。

第一轮处理结果如下

第二轮：

处理逻辑和第一轮是相同的。

• 遍历V1~V3，看看谁的dist最小，找到V3，将V3的final设为TRUE。
• 检查所有能够从V3过去的顶点，当然我们只需要检查final为false的顶点。
  • 从V3过去的顶点有V0和V2，但是V0我们不需要考虑，所以只看V2。
  • 对V2这个顶点，如果我们是从V3过去的，那么路径长度为7+6=13的路径，显然比原先的14更短，则更新V2的dist为13，并更新V2的path为3。

第二轮处理结果：

第三轮：

• 遍历V1~V2，看看谁的dist最小，则找到V1，并将其final设为TRUE。
• 检查所有从V1过去，且final为false的顶点。即V2。
  • 对于V2，检查是否需要更新dist和path信息。
  • 若V2是由V1过去的，则路径长度为8+1=9，比原先的13短。于是更新dist为9，更新path为1。

第三轮处理结果：

第四轮：

• 遍历V2，V2的dist最小，将V2的final设为TRUE。
• 所有结点的final全部为TRUE。此时已经找不到final为false的顶点了。
• 算法到此结束。

以上就是Dijkstra算法的执行过程。

通过执行结果可知，

V0到V2的最短（带权）路径长度为：dist[2] = 9

通过path[]可知，V0到V2的最短（带权）路径：V2<--V1<--V4<--V0

3.Dijkstra算法的时间复杂度

对于考研来说，这个算法只需要理解手动执行的过程，能够手算即可。

我们也简单的提一下，如果用代码实现，大致的思路是什么样的。

• 初始：若从V0开始。令final[0] = TRUE；dist[0] = 0；path[0] = -1。其余顶点final[k] = false；dist[k] = arcs[0][k]；path[k] = (arcs[0][k]==∞) ? -1 : 0。
• 第n-1轮处理：
  • 循环遍历所有顶点，找到还没确定最短路径，且dist最小的顶点Vi，令其final[i] = true。并遍历所有邻接自Vi，且还没确定最短路径的顶点，即final[j] == false，若final[j] == false && dist[i]+arcs[i][j] < dist，则令dist[j] = dist[i] + arcs[i][j]; path[j] = i;。（注：arcs[i][j]表示Vi到Vj的弧的权值）

现在探讨一下其时间复杂度的问题

对于每一轮处理来说，我们都要循环遍历所有顶点，找到还没确定最短路径，且dist最小的顶点。所以需要O(n)的时间复杂度。此外，找到这个结点之后，还需要检查所有和它相邻的邻接点，又需要O(n)的时间复杂度。

所以每一轮处理的时间复杂度为O(2n)，即O(n)。

而总共需要n-1轮处理。所以整个算法的时间复杂度为O(n²)。即O(|V|²)。

可以发现，这个算法其实和Prim算法是比较类似的。此代码的dist[]数组，和Prim算法中的lowCost[]数组的作用是很类似的。

4.用于负权值带权图

这是Dijkstra算法的一个小坑。

如果带权图里，有负权值的边。那么Dijkstra算法有可能就会失效，找不到最短路径。

按照算法的规则，我们执行一遍：

• 初始：如上图所示。
• 第一轮：
  • 遍历V1、V2，找到V2的dist最短，设其final为true，path为0。
  • 第一轮结束。
• 第二轮：
  • 只剩下V1，将其final设为true，path为0。
• 此时所有结点的final均为TRUE，算法执行完毕。

最终结果如下：

但是，事实上，V0到V2的最短带权路径长度为5。

因此，Dijkstra算法不适用于有负权值的带权图。

（四）Floyd算法

弗洛伊德（1936—2001），1978年图灵奖得主。

• Floyd算法（Floyd-Warshall算法）
• 堆排序算法

Floyd算法：求出每一对顶点之间的最短路径。

使用动态规划思想，将问题的求解分为多个阶段。（每个阶段之间有一个递进的关系）

对于n个顶点的图G，求任意一对顶点Vi—>Vj之间的最短路径可分为如下几个阶段：

• 初始：不允许在其他顶点中转，最短路径是？
• 0：若允许在V0中转，最短路径是？
• 1：若允许在V0、V1中转，最短路径是？
• 2：若允许在V0、V1、V2中转，最短路径是？
• ……
• n-1：若允许在V0、V1、V2……V(n-1)中转，最短路径是？

这个动态规划的思想可能不太好理解，但是这个算法的执行过程实际来讲还是比较简单的。

1.一个简单的例子

我们来把这个算法流程跑一遍。

我们设置两个矩阵（二维数组）。

第一个矩阵，其实就是这个有向图的邻接矩阵。

由于初始阶段，我们不允许有其他顶点中转的情况出现，因此，例如V0——V2，就只能走13这条路。

所以，第一个矩阵中，第一行第三列就是13。

第二个矩阵，存放的就是，我们目前能够找到的最短路径当中，两个顶点之间的一个中转点。

初始阶段，所有顶点之间都不可以有中转点，所以全是-1。

以上是初始阶段的流程。

0阶段：

若允许在V0中转，最短路径是？——求A(0)和path(0)。

我们要基于上一轮求得的两个矩阵的信息，得到这一轮的两个矩阵中应该填入的最优信息。

求解的方法很简单，我们需要遍历上一阶段留下来的这个矩阵A，对于矩阵A当中的每一个具体的元素，我们都需要进行以下处理：
$$\begin{gathered} 若A^{(k-1)}[i][j]>A^{(k-1)}[i][k]+A^{(k-1)}[k][j] \\ 则A^{(k)}[i][j]=A^{(k-1)}[i][k]+A^{(k-1)}[k][j]; \\ pat{h}^{(k)}[i][j]=k \\ 否则A^{(k)}和path(k)保持原值 \end{gathered}$$

例如对于矩阵A中，第三行第二列，也就是V2——V1的这个数据。如果允许在V0中转，那么考虑
$$\begin{gathered} A^{(-1)}[2][1]>A^{(-1)}[2][0]+A^{(-1)}[0][1]=11 \\ 则A^{(0)}[2][1]=11; \\ pat{h}^{(0)}[2][1]=0; \end{gathered}$$

当然，对于这个矩阵中的所有位置的元素，都需要依次循环遍历一遍，各进行判断。（按照上面的处理方法）

实际上，在对所有位置元素均各执行一遍判断之后，需要改变的也就只有这一个位置，如下图

1阶段：

若允许在V0、V1中转，最短路径是？——求A(1)和path(1)。

我们需要在基于0阶段得到的两个矩阵的基础上，来计算该阶段的矩阵内容，也就是1阶段的最优解。

那还是利用刚才的这个规则：
$$\begin{gathered} 若A^{(k-1)}[i][j]>A^{(k-1)}[i][k]+A^{(k-1)}[k][j] \\ 则A^{(k)}[i][j]=A^{(k-1)}[i][k]+A^{(k-1)}[k][j]; \\ pat{h}^{(k)}[i][j]=k \\ 否则A^{(k)}和path(k)保持原值 \end{gathered}$$
我们要基于前一个阶段的矩阵的值，来对此阶段的矩阵内容进行一个判断。

对所有元素都遍历一遍之后，我们会发现这样一个地方，是满足需要被处理的条件的：
$$\begin{gathered} A^{(0)}[0][2]>A^{(0)}[0][1]+A^{(0)}[1][2]=10 \\ 则A^{(1)}[0][2]=10; \\ pat{h}^{(1)}[0][2]=1; \end{gathered}$$

经过修改之后，矩阵会变成这样：

2阶段：

若允许在V0、V1、V2中转，最短路径是？——求A(2)和path(2)。

要以1阶段得出的矩阵信息，作进一步处理，得到此阶段的最优解。

依然是同样的处理规则。依次扫描矩阵中的所有元素，并处理满足条件的元素。

全部扫描过后，可以发现只有一个地方满足，如下
$$\begin{gathered} A^{(1)}[1][0]>A^{(1)}[1][2]+A^{(1)}[2][0]=9 \\ 则A^{(2)}[1][0]=9; \\ pat{h}^{(2)}[1][0]=2; \end{gathered}$$

到此，我们就求出了A(2)和path(2)：

到了这一步，从A(-1)和path(-1)开始，我们已经经过了**n轮递推，**每一轮递推，我们都会增加考虑一个新的结点作为中转点，得到A(n-1)和path(n-1)。到此，我们便得到了每两个顶点之间最短路径的长度，和路径上的信息。（n指的是总结点个数）

观察两表，

例如，V1到V2的最短路径。检查A数组，发现长度是4；再检查path数组，发现它们之间是不经过任何中转点的，因此这条最短路径为V1—V2。

例如，V0到V2的最短路径。查找A数组，发现长度是10；再查path数组，V0到V2之间的中转点是1号中转点，因此这条最短路径为V0—V1—V2。

同理，V1到V0的最短路径长度为9，路径为V1—V2—V0。

所以，Floyd算法的思想虽然有些抽象，但是实现起来还是比较简单的。

Floyd算法核心代码：

//......准备工作，根据图的信息初始化矩阵A和path（如上图）
for(int k=0; k<n; k++) {		//考虑以Vk作为中转点
    for(int i=0; i<n; i++) {	//遍历整个矩阵，i为行号，j为列号
        for(int j=0; j<n; j++) {
            if(A[i][j] > A[i][k] + A[k][j]) {	//以Vk为中转点的路径更短
                A[i][j] = A[i][k] + A[k][j];	//更新最短路径长度
                path[i][j] = k;		//中转点
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

可见，这个算法的时间复杂度为O(n³)，即O(|V|³)。（三层嵌套）；空间复杂度为O(|V|²)。（两个矩阵）。

注意，上面这个例子，只是有三个结点，这个例子虽然能帮助我们理解Floyd算法的流程，但是，这个例子在我们考虑加入中转点的时候，最多也就只需要走两条边。

而对于Floyd算法的真正的作用、效果，这个例子体现的并不是很好。

2.一个较复杂的例子

0阶段：

若允许在V0中转，最短路径是？

依次检查矩阵中所有元素，检查规则为：
$$\begin{gathered} 若A^{(k-1)}[i][j]>A^{(k-1)}[i][k]+A^{(k-1)}[k][j] \\ 则A^{(k)}[i][j]=A^{(k-1)}[i][k]+A^{(k-1)}[k][j]; \\ pat{h}^{(k)}[i][j]=k \\ 否则A^{(k)}和path(k)保持原值 \end{gathered}$$
代码体现如下：

for(int i=0; i<n; i++) {		//遍历整个矩阵，i为行号，j为列号
    for(int j=0; j<n; j++) {
        if(A[i][j] > A[i][k] + A[k][j]) {	//以Vk为中转点的路径更短
            A[i][j] = A[i][k] + A[k][j];	//更新最短路径长度
            path[i][j] = k;	//中转点
        }
    }
}
1
2
3
4
5
6
7
8

对于这个代码，此阶段就是执行k=0的情况。

遍历矩阵中所有元素后，会发现所有元素都不需要更新。

得到A(0)和path(0)：

实际上，从这个图本身也很好理解。V0这个结点只有出边，没有入边。那么，没有任何一个结点能够进入V0处，又怎么可能在V0中转呢？所以两矩阵内容并没有发生任何改变。

1阶段：

若允许在V0、V1中转，最短路径是？

依然是遵循同样的规则/代码（k=1）。

遍历过后，发现需要更改的地方，如下
$$\begin{gathered} 第一处需要更新： \\ {A}^{(0)}[2][3]>A^{(0)}[2][1]+A^{(0)}[1][3]=2 \\ {A}^{(1)}[2][3]=2; \\ pat{h}^{(1)}[2][3]=1; \\ 第二处需要更新： \\ {A}^{(0)}[2][4]>A^{(0)}[2][1]+A^{(0)}[1][4]=6 \\ {A}^{(1)}[2][4]=6; \\ pat{h}^{(1)}[2][4]=1; \end{gathered}$$
经过这一轮的处理，两矩阵更新如下：

2阶段：

若允许在V0、V1、V2中转，最短路径是？

遍历过后，发现需要更改的地方，如下：
$$\begin{gathered} A^{(1)}[0][1]>A^{(1)}[0][2]+A^{(1)}[2][1]=2 \\ {A}^{(2)}[0][1]=2;pat{h}^{(2)}[0][1]=2; \\ ----------- \\ {A}^{(1)}[0][3]>A^{(1)}[0][2]+A^{(1)}[2][3]=3 \\ {A}^{(2)}[0][3]=3;pat{h}^{(2)}[0][3]=2; \\ ----------- \\ {A}^{(1)}[0][4]>A^{(1)}[0][2]+A^{(1)}[2][4]=7 \\ {A}^{(2)}[0][4]=7;pat{h}^{(2)}[0][4]=2; \end{gathered}$$

注意：

分析此步骤所反映出的结果。

也就是有两处需要优化：

0结点到1结点，改为了0—2，再2—1，OK；

0结点到3结点，改为了0—2，再2—3，？？？

通过看图，我们发现V2到V3之间没有“边”呀？为什么呢？

这就是因为，在上一阶段，对于V2到V3的路径，已经是由V1中转过的结果了（也就是为什么每一阶段要在上一阶段两个矩阵中的信息的基础之上进行求最优解）。而不是单纯的理解为V2到V3是否有”边“的问题。

实际上，这个A^{(1)}[2][3]，它反映的就是在上一阶段处理2结点到3结点最短路径问题，所得的结果。（即1阶段中，允许由V0、V1中转，所求得的V2到V3的最短路径）。

由此，我们就能很好的体会到，我们在之前就已经考虑到，增加V1作为中转节点，然后，现在我们的计算，是基于之前已经求得的最优结果的基础之上，再增加V2作为中转点。

所以此处这个0结点到3结点的最优路径，表面上看是0—2，再2—3，其实是0—2，再2—1，再1—3。

而对于整个路径来看，其实就已经考虑到了以V0、V1、V2作为中转点的所有情况了。

此阶段处理完后，两矩阵的最新信息如下：

3阶段：略。

4阶段：略。

结束。最终得到的两个矩阵内容如下：

现在我们来看一下，怎么解读这两个矩阵中的信息：

例如，要找V0到V4的最短路径。

• 由A矩阵可知长度为4。
• 由path矩阵
  • 首先可以知道V0到V4需要经过一个中转点是V3，也就是说V0需要先到V3，V3再到V4。但是由图中可以看出，V0到V3并没有一条直接存在的路径供我们经过，其实V0到V3的最短路径，其中还是要经过一些中转节点的。而V3到V4是不需要中转的（由path的值为-1即可看出）。
  • 再看V0到V3怎么走。由path数组可知，V0到V3，中间还要经过V2。也就是V0需要先到V2，V2再到V3。V0到V2（path的值为-1）是没有中转点的；而V2到V3（path值为1）还需要经过V1中转点。
  • 到这一步，整理一下，即V0 V2 V1 V3 V4，实际上这就是最终结果了。

总结一下获取最短路径走法的过程（通过path矩阵递归地找到完整路径）：

• V0——————V3——————V4
• V0———V2——V3——————V4
• V0———V2—V1—V3——————V4

可以用path矩阵配合上递归算法很好的解决这个问题。

但是单从考试的角度来看，会手算即可。

但是有个问题，在手算A矩阵的时候，由于这是5行5列的矩阵，我们如果要把所有元素依次完整地执行一遍，其实我们总共需要5³=125次检查。所以在考试的时候，不可能会给你这么复杂的一个图的。让你在考场上进行125次加法、比大小，是没什么意义的。所以考试的时候给的图一般阶数都比较小。

3.Floyd算法用于负权图

//......准备工作，根据图的信息初始化矩阵A和path（见上图）
for(int k=0; k<n; k++) {	//考虑以Vk作为中转点
    for(int i=0; i<n; i++) {	//遍历整个矩阵，i为行号，j为列号
        for(int j=0; j<n; j++) {
            if(A[i][j] > A[i][k] + A[k][j]) {	//以Vk作为中转点的路径更短
                A[i][j] = A[i][k] + A[k][j];	//更新最短路径长度
                path[i][j] = k;		//中转点
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

自己练习，用Floyd算法对此负权图执行一遍。

会发现，Floyd算法可以用于负权值带权图。（就解决了Dijkstra算法解决不了的问题）

但是，这个算法也有它所解决不了的问题。

4.不能解决的问题

Floyd算法不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径。

对于这个图，其中的这个回路来说，你会发现，你走这个回路，走的次数越多，你的带权路径长度会越来越小。因此根本就找不到最短路径。

（五）总结

注：也可用Dijkstra算法求所有顶点间的最短路径，重复|V|次即可，总的时间复杂度也是O(|V|³)

BFS算法有两种时间复杂度的情况，是由于图的存储方式，是邻接矩阵还是邻接表存储的区别导致的。

七、有向无环图

（一）有向无环图（DAG）

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）。

（二）DAG描述表达式

之前我们说过，算术表达式可以用树来表示。

但是对于上图来说，不难看出，有两部分是重复的，((c+d)*e)出现了两次。

实际上，图中红色、绿色两棵子树，其计算结果是一样的。所以其实可以去除其中一棵，只保留一棵。

就成了如下这种样子：

这么做的好处显而易见，能够节省存储空间。

而现在产生的这种结构，其实就是有向无环图。

其实我们继续再看一下，里面还有重复的部分：(c+d)。可以继续进行“合并”。

合并后，就变成如下这样：

到此，继续观察，还是有相同的“子树”：b出现了两次。

“合并”后，结果如下：

这个过程，如果不细心的话，有可能会无法找全所有可以合并的点。

但是在考研408真题中，又会遇到类似的题，如下：

经过合并，如下图所示，此题选A。

由于这种题容易遗漏可以合并的点，因此总结以下解题规律：

• 顶点中不可能出现重复的操作数。

因此，有以下解题步骤：

• 第一步：把各个操作数不重复地排成一排，如下图所示。

• 第二步：标出各个运算符的生效顺序（先后顺序有点出入无所谓，目的是为了不重不漏地处理完毕所有运算符）

• 第三步：按顺序加入运算符，注意“分层”。（分层的意思见下图）

• 第四步：从底向上逐层检查同层的运算符是否可以合体。

  （为什么一层一层检查同层的运算符，不难体会到，如果是不同层的，则是一定不可能合并的。这也是第三步构造的过程中要注意“分层”的原因）

  • 看最下面一层运算符。有四个加法。但是最左边的那一个加号，它是对a和b进行相加，右边三个加号，均是对c和d进行相加。因此右边三个加号可以合并，而左边一个加号不能合并。

    

    

• 运算符合体完毕如下图所示。此时我们就得到了一个最简的有向无环图。

（三）拓扑排序

1.如何进行拓扑排序

AOV网（Activity On Vertex NetWork，用顶点表示活动的网）：

用DAG图（有向无环图）表示一个工程。顶点表示活动，有向边<Vi, Vj>表示活动Vi必须先于活动Vj进行。

如果存在环路，则一定不是AOV网。

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

①每个顶点出现且只出现一次。

②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

或定义为：

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

上述定义可能看不懂，我们直接看如何进行拓扑排序。

拓扑排序实际上就是：找到做事的先后顺序。

例如这个AOV网，我们可以从准备厨具或买菜开始做起。

• 例如我们将准备厨具作为第一件事开始。

• 那么第二件事是什么？第二件事一定是买菜。因为如果不这样，那么是不可能进行其他操作的。

• 第三件事，同理，可以先选择打鸡蛋，也可以先选择洗番茄。例如我们先选择洗番茄。

• 第四件事，我们可以先选择打鸡蛋，也可以先选择切番茄。例如我们选择先切番茄。

• 至此，剩下的事情顺序，就必须是打鸡蛋、下锅炒、吃了。最终拓扑排序如下所示：

拓扑排序的实现：

①从AOV网中选择一个没有前驱（入度为0）的顶点并输出。

②从网中删除该顶点和所有以它为起点的有向边。

③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止（说明有回路）。

**注：**如果③的结果为当前网中不存在无前驱的顶点，则说明有回路，则说明其是不可以拓扑排序的。

例如，若有回路，则，到这一步时，发现没有入度为0的结点。说明原图存在回路。

所以，对于存在回路的图，是不可能存在拓扑排序序列的。

如果原图是一个DAG图（有向无环图），那么就存在拓扑排序序列。

2.拓扑排序的代码实现

其实代码实现思路很简单，就是把刚才说的那两个需要不断重复的步骤①②，不断地重复，直到达到③的条件就可以。

#define MaxVertexNum 100	//图中顶点数目的最大值
typedef struct ArcNode {	//边表结点 
	int adjvex;		//该弧所指向的顶点的位置
	struct ArcNode *nextarc;	//指向下一条弧的指针
	//InfoType info;	//网的边权值 
}ArcNode 

typedef struct VNode {	//顶点表结点 
	VertexType data;	//顶点信息
	ArcNode *firstarc;	//指向第一条依附该顶点的弧的指针 
}VNode, AdjList[MaxVertexNum];

typedef struct {
	AdjList vertices;	//邻接表
	int vexnum, arcnum;	//图的顶点数和弧数 
}Graph;		//Graph是以邻接表存储的图类型

bool TopologicalSort(Graph G) {
	InitStack(S);	//初始化栈，存储入度为0的顶点
	for(int i=0; i<G.vexnum; i++) {
		if(indegree[i] == 0)
			Push(S, i);	//将所有入度为0的顶点进栈 
	}
	int count = 0;	//计数，记录当前已经输出的顶点数
	while(!IsEmpty(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，则入栈 
		}
	}//while
	if(count < G.vexnum)
		return false;	//排序失败，有向图中有回路 
	else 
		return true;	//拓扑排序成功 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

时间复杂度：

由于每个顶点都需要处理一次，每条边都需要处理一次。

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

若采用邻接矩阵，则需O(|V|²)

（四）逆拓扑排序

1.如何进行逆拓扑排序

对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序：

①从AOV网中选择一个没有后继（出度为0）的顶点并输出。

②从网中删除该顶点和所有以它为终点的有向边。

③重复①和②直到当前的AOV网为空。

上图的逆拓扑排序如下：

2.逆拓扑排序的代码实现

把“拓扑排序”中，进行入度为0的条件判断改为出度为0即可实现逆拓扑排序的代码。

自己练习：模仿拓扑排序的思想实现逆拓扑排序。

自己思考：使用不同的存储结构（即改用邻接矩阵实现）对时间复杂度的影响。

对于逆拓扑排序来说，由于每次都要寻找该顶点的入边，若采用邻接表存储，则需要重新整个遍历所有邻接表，找到指向该顶点的边。是很低效的。而如果采用邻接矩阵，会很方便。

甚至，还可以采用“逆邻接表”：邻接表中，每一个顶点所对应的边的信息，是由该顶点发射出的边；而逆邻接表中，每一个顶点所对应的边的信息，是指入该顶点的边。

3.逆拓扑排序的实现（DFS算法）

用深度优先算法实现拓扑排序或逆拓扑排序。

这里先不讲。

但是这里先补充一个课本中没有讲的，DFS算法实现逆拓扑排序。

void DFSTraverse(Graph G) {	//对图G进行深度优先遍历 
	for(v=0; v<G.vexnum; ++v) {
		visited[v] = FALSE;	//初始化已访问标记数据 
	}
	for(v=0; v<G.vexnum; ++v) {	//本代码中是从v=0开始遍历 
		if(!visited[v])
			DFS(G, v);
	}
}

void DFS(Graph G, int v) {	//从顶点v出发，深度优先遍历图G 
	visit(v);	//访问顶点v
	visited[v] = TRUE;	//设已访问标记
	for(w=FirstNeighbor(G, v); w>=0; w=NextNeighbor(G,v,w)) {
		if(!visited[w]) {	//w为u的尚未访问的邻接顶点 
			DFS(G, w);
		}
	}
    print(v);	//输出顶点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

在DFS算法的基础上，添加一个print(v);的操作，输出出来的就是逆拓扑序列。

上图，本身是不存在环路的。且我们的代码实现也没有考虑回路的问题。

思考：如果存在回路，则不存在逆拓扑排序序列，那么如何判断回路的存在？试着对代码进行一个改进。

（五）总结

拓扑排序

• AOV网
  • 顶点代表活动，有向边<Vi, Vj>表示活动Vi必须先于Vj进行
  • AOV网一定是DAG图，不能有环
• 拓扑排序
  • ①从AOV网中选择一个没有前驱（入度为0）的顶点并输出
  • ②从网中删除该顶点和所有以它为起点的有向边
  • ③重复①和②直到当前的AOV网为空
• 逆拓扑排序
  • ①从AOV网中选择一个没有后继（出度为0）的顶点并输出
  • ②从网中删除该顶点和所有以它为终点的有向边
  • ③重复①和②直到当前的AOV网为空
• 另一种实现方式：用DFS实现拓扑排序/逆拓扑排序
• 性质
  • 拓扑排序、逆拓扑排序序列可能不唯一
  • 若图中有环，则不存在拓扑排序序列/逆拓扑排序序列

八、关键路径

（一）AOE网

AOE网：

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网（Activity On Edge NetWord）。

AOV网，V表示Vertex，指用顶点表示活动；

AOE网，E表示Edge，指用边表示活动。

顶点表示事件，是一瞬间发生的事情；边表示活动，是需要持续一段时间的。

AOE网具有以下两个性质：

①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；

②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。

（二）关键路径

AOE网还有一些概念：

• 在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；
• 也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

找到关键活动是哪些，我们就知道了影响整个项目的，是哪些事。

对于上图：

• 最快多久可以开始做？——现在，立刻（0分钟）
• 最快多久可以开切？——1分钟
• 最快多久可以开炒？——4分钟
• 最快多久可以吃？——6分钟

事件Vk的最早发生时间Ve(k)——决定了所有从Vk开始的活动能够开工的最早时间。

（等于其前驱活动的最早开始时间 + 该活动需要消耗的时间）

例如，可以切了事件它的最早发生时间为1分钟，则在它之后的所有活动最早也要在1分钟时开工。

活动ai的最早开始时间e(i)——指该活动弧的起点所表示的事件的最早发生时间。

上图，黄色为事件的最早发生时间，红色为活动的最早开始时间。

如果有一个人说：6分钟后我一定要吃到，不然我会被饿死。

之后厨师分析了一下：整个项目6分钟可以结束。

由于炒菜需要2分钟，于是推出：4分钟时一定要开始炒菜这一活动。（如果4分钟时不能完成可以炒了事件，就意味着6分钟不可能结束）

继续往前推，由切番茄需要3分钟，可以推出：可以切了事件，必须在1分钟时就发生。

继续，由洗番茄需要1分钟，推出：开始必须是现在。

上述我们从后往前推，推出了每个事件允许发生的最迟的时间。

事件Vk的最迟发生时间Vl(k)——它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。

活动ai的最迟开始时间l(i)——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。

上图，红色表示活动的最早开始时间，绿色表示活动的最迟开始时间。

活动ai的时间余量d(i) = l(i) - e(i)，表示在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间。

若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i)=e(i)的活动a(i)是关键活动。

（三）求关键路径的步骤

①求所有事件的最早发生时间ve()

②求所有事件的最迟发生时间vl()

③求所有活动的最早发生时间e()

④求所有活动的最迟发生时间l()

⑤求所有活动的时间余量d()

到第⑤步，由于d(i)=0的活动就是关键活动，由关键活动可得关键路径。

1.求所有事件的最早发生时间

①求所有事件的最早发生时间ve()

（某一事件的最早发生时间，等于其前驱活动的最早开始时间 + 该活动需要消耗的时间）

按拓扑排序序列，依次求各个顶点的ve(k)：

ve(源点) = 0

ve(k) = Max{ ve(j) + Weight(Vj, Vk) }，Vj为Vk的任意前驱

首先我们要对这个AOE网进行一个拓扑排序。

拓扑序列：V1、V3、V2、V5、V4、V6

根据拓扑排序序列的顺序，来依次计算各个顶点所代表的事件的最早发生时间。

这是因为，拓扑排序表示活动所必需的先后次序，我们根据拓扑排序序列依次计算最早发生时间，可以做到有条不紊。

• ve(1) = 0
• ve(3) = 0 + 2 = 2
• ve(2) = 0 + 3 = 3
• ve(5) = 3 + 3 = 6
• ve(4) = max{ ve(2) + 2，ve(3) + 4 } = 6
• ve(6) = max{ ve(5) + 1，ve(4) + 2，ve(3) + 3 } = 8

2.求所有事件的最迟发生时间

②求所有事件的最迟发生时间vl()

（某一事件的最迟发生时间，等于其后继活动的最迟发生时间 - 该活动需要消耗的时间）

按逆拓扑排序序列，依次求各个顶点的vl(k)：

vl(汇点) = ve(汇点)

vl(k) = Min{ vl(j) - Weight(Vk，Vj) }，Vj为Vk的任意后继

逆拓扑排序序列：V6、V5、V4、V2、V3、V1

• vl(6) = 8（也就是把上一步计算得到的汇点的最早发生时间，赋给此处）
• vl(5) = 8 - 1 = 7
• vl(4) = 8 - 2 = 6
• vl(2) = min{ vl(5) - 1，vl(4) - 2 } = 4
• vl(3) = min{ vl(4) - 4，vl(6) - 3 } = 2
• vl(1) = 0

3.求所有活动的最早发生时间

③求所有活动的最早发生时间e()

（某活动的最早发生时间，等于其弧尾事件的最早发生时间）

若边<Vk, Vj>表示活动ai，则有e(i) = ve(k)

4.求所有活动的最迟发生时间

④求所有活动的最迟发生时间l()

（某活动的最迟发生时间，等于其弧头事件的最迟发生时间 - 该活动所需时间）

若边<Vk, Vj>表示活动ai，则有l(i) = vl(j) - Weight(Vk, Vj)

5.求所有活动的时间余量

⑤求所有活动的时间余量d()

用活动的最迟发生时间 - 活动的最早发生时间

d(i) = l(i) - e(i)

6.找出关键路径

根据最终得到的各个活动的时间余量，可以发现活动a2、a5、a7的时间余量都等于0，也就是说这几个活动是绝对不允许拖延的。因此我们就找到了所有的关键活动。

关键活动：a2、a5、a7

关键路径：V1——>V3——>V4——>V6

（四）关键活动、关键路径的特性

• 若关键活动耗时增加，则整个工程的工期将增长

• 缩短关键活动的时间，可以缩短整个工程的工期

• 当缩短到一定程度时，关键活动可能会变成非关键活动

• 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的

  • 要么把两条路径上的关键活动分别都加速。要么把这两个关键路径的交集路线上的活动加速（也相当于给两条路径都加速了）。

（五）总结

关键路径

• AOE网
  • 在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销
  • 相关概念
    • 在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始
    • 也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束
    • 从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动
• 求解方法
  • ①求所有事件的最早发生时间
  • ②求所有时间的最迟发生时间
  • ③求所有活动的最早发生时间
  • ④求所有活动的最迟发生时间
  • ⑤求所有活动的时间余量
  • ⑥根据时间余量为0的活动，得出关键活动、关键路径
• 特性
  • 若关键活动耗时增加，则整个工程的工期将增长
  • 缩短关键活动的时间，可以缩短整个工程的工期
  • 当缩短到一定程度时，关键活动可能会变成非关键活动
  • 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的