数据结构复盘——第六章：图

---

第一部分：图的一些专业术语

1、有向图和无向图

• 有向图中，顶点对有序，称为从顶点x到顶点y的一条有向边。因此和是不同的两条边。也可以称作一条弧，x叫弧尾，y叫弧头
• 无向图中，顶点对(x，y)有序，称为与顶点x和顶点y相关联的一条边。这条边没有特定的方向，因此(x，y)和(y，x)是同一条边。

2、简单图和多重图

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

• 多重图：① 某两个结点之间的边数多于一条；② 允许顶点通过同一条边和自己关联。

3、完全图（也称简单完全图）

• 在无向图中，若任意两个顶点之间都存在边（即图一共具有n(n-1)/2条边），则称为无向完全图；
• 在有向图中，若任意两个顶点之间都存在往返的两条有向边（即图一共具有n(n-1)条弧），则称为有向完全图；

4、稠密图和稀疏图

• 由很少条边或弧的图称为稀疏图，反之称为稠密图

5、邻接点

• 在无向图中，若两个顶点 a、b 之间存在边（a，b），那么就称顶点 a 与 b 互为 邻接点，即 a 和 b 相邻接；
  • 边（a，b）依附于顶点 a 和 b，或者说边（a，b）与顶点 a 和 b 相关联。
• 在有向图中，若两个顶点 a、b 之间存在弧 ，那么就称顶点 a 邻接到 顶点 b，顶点 b 邻接自 顶点 a；
  • 弧 与顶点 a 和 b 相关联。

6、连通，连通图和连通分量

• 在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。
• 连通与邻接不同：邻接一定连通，但连通不一定邻接。
• 若图中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
• 无向图中的极大连通子图称为连通分量。
  ① 任何连通图的连通分量只有一个，即本身；（最少为1）
  ② 非连通图有多个连通分量；（最多为顶点个数）

7、强连通，强连通图和强连通分量

• 在有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。
• 若图中任何一对顶点都是强连通的，则称此图为强连通图。
• 有向图中的极大强连通子图称为有向图的强连通分量。
  ① 任何强连通图的强连通分量只有一个，即本身；（最少为1）
  ② 非强连通图有多个强连通分量；（最多为顶点个数）

8、路径，路径长度和回路

• 顶点v到顶点w之间的一条路径是指顶点序列。
• 路径上边或弧的数目称为路径长度。
• 第一个顶点和最后一个顶点相同的路径称为回路或环。

9、简单路径和简单回路

• 在路径序列中，顶点不重复出现的路径称为简单路径。（没有重复经过某一地点）
• 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或简单环。（不重复经过某一地点回到出发点）

10、距离

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

11、生成树和生成森林

• （无向）连通图的生成树是包含图中全部顶点的一个极小连通子图。
• 若图中顶点数为n，则它的生成树含有n-1条边。
  ① 如果一个图有n个顶点和小于n-1条边，则是非连通图；
  ② 如果一个图有n个顶点和多于n-1条边，则一定有环；
  ③ 但是要注意有n-1条边的图不一定就是生成树，这是一个必要不充分条件（还得是连通图）。
• 在（无向）非连通图中，每个连通分量都可以得到一个极小连通子图，即生成树，这些生成树就组成了非连通图的生成森林。

12、子图

• 当一个图A的顶点的集合和关系（边）的集合都是另一个图B的顶点的集合和关系（边）的集合的子集时，就称A是B的子图；
• 并非只要是图B的顶点的集合和关系（边）的集合的子集就可以构成子图，因为这样的两个子集可能构不成图（边所关联的顶点可能不是子集中包含的顶点），所以说这是一个必要不充分条件（这个两个子集还得是某个图的顶点与边的集合）。
• 极小连通子图：极小连通子图子图是既要保证图连通，又要使得边数最少的子图，删去任意一条边该子图将不再连通；
• 极大连通子图：极大连通子图需要包含连通分量中所有的边，也就是说某些情况下可以和极小连通子图相同。

13、度，入度和出度

• 顶点v的度是指和顶点相关联的边的数目；
• 对于有向图，顶点v的度分为入度和出度：
  ① 入度是指向顶点v的弧的数目；
  ② 出度是由顶点v发出的弧的数目；

14、有向树

• 有一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树；
• 一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

15、权和网

• 在实际应用中，图的每条边可以标上具有某种含义的数值，该数值称为该边上的权；
• 这些权可以表示从一个顶点到另一个顶点的距离或耗费，通常我们将这种带权的图称为网。

---

第二部分：图的存储方式

1、邻接矩阵

用一个一维数组存储图中顶点的信息，存储顶点信息的一维数组称为顶点表；
用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。
       
一个含有n个顶点的图，其邻接矩阵（Adjacency Matrix）是具有如下性质的n阶方阵：（ $v_i、v_j$ 是图的顶点）$$A[i][j]=\{\begin{array}{l}1，若弧<v_i,v_j>或边(v_i,v_j)存在\\ 0，反之邻边不存在\end{array}$$
若是含有n个顶点的网，其邻接矩阵（Adjacency Matrix）则是有如下性质的n阶方阵：（ $w_{i,j}$ 是边的权值）$$A[i][j]=\{\begin{array}{l}{w}_{i,j}，若弧<v_i,v_j>或边(v_i,v_j)存在\\ \infty ，反之邻边不存在\end{array}$$
    

对于无向图的邻接矩阵：

• 对称矩阵，主对角线元素为0；
• 顶点的度 = i 行元素和 = i 列元素和。

对于有向图的邻接矩阵：

• 可能不对称，但主对角线元素均为0；
• 顶点的出度 = i 行元素和；
• 顶点的入度 = i 列元素和。

2、邻接表

邻接表是图的一种链式存储结构，为每个顶点 $v_i$ 建立了一个单链表存储依附于它的边 $(v_i，v_j)$ （如果是有向图则是以顶点 $v_i$ 为尾的弧 $<v_i，v_j>$ ），同时将表头结点存储在顺序表中。因此邻接表便由两部分组成：

• 表头结点表（也叫顶点表）：由所有表头结点以顺序结构的形式存储。表头结点包括数据域data和链域firstarc，其中：
  • 数据域用于存储顶点名称和其他有关信息；
  • 链域用于指向链表中第一个结点。
• 边表（有向图叫出边表）：由表示图中顶点间关系的 n 个边链表组成。边链表包含表头结点和边结点，其中边结点包括邻接点域adjvex和链域nextarc（以及数据域info），其中：
  • 邻接点域指示了边 $(v_i，v_j)$ 的邻接点 $v_j$ 在图中的位置，即 $v_j$ 在顶点表中的数组下标；（有向图中就是弧 $<v_i，v_j>$ 的头 $v_j$ 在图中的位置）
  • 链域用于指向与当前顶点邻接的下一条边的结点；（边表中连接顺序不代表边/弧在图中具有先后顺序）
  • 若包含数据域，则数据域存储了当前边/弧的权值等相关信息。

在无向图中顶点 $v_i$ 的度恰为第 i 个链表中的边结点个数。
在有向图中第 i 个链表中的边结点个数只是顶点 $v_i$ 的出度，要求入度则需遍历整个邻接表（或构建一个逆邻阶表）。

【注意】
① 图的邻接表和二叉树的孩子链表用的是同一存储结构：顺序表+链表（主要是链式存储）；
② 由于单链表中各边结点的连接次序可以是任意的，所以图的邻接链表表示法不唯一；
③ 我们之前提到了图是可以生成树和森林的，因为树的双亲孩子关系与有向图的首尾关系非常相似，所以图和树的存储方式是可以相互参考的（博主不确定方法提出的先后）。

3、邻接多重表

无向图的邻接表容易求得顶点和边的各种信息，但是由于一条边被存储在相关联的两个顶点的边链表中，对边执行标记与删除等操作时需要分别在两个链表中遍历查找结点，效率较低。
改进后的邻接多重表是更适合无向图执行这类操作的一种链式存储结构（主要是链式存储，包含顺序存储的顶点表）。

顶点结点中包含两个域：

• 存储顶点相关信息的data数据域；
• 指向第一条依附于该顶点的边的firstedge指针域。

边结点中包含六个域：（数据域和指针域都是“i 在前，j 在后”）

• mark：标志域，用于标记该条边是否被操作过。例如在对图中顶点做遍历操作时，为了防止多次操作同一节点，mark域为 0 表示还未被遍历；mark域为 1 表示该节点已被遍历；
• ivex和jvex：数据域，分别存储该边两端依附的顶点在图中的位置，即在顶点表中的数组下标；
• ilink：指针域，指向下一条依附于顶点 ivex 的边；
• jlink：指针域，指向下一条依附于顶点 jvex 的边；
• info：指针域，用于指向和该边相关各种信息的存储地址（注意和邻接表中区分，那里 info 是数据域）。

【说明】
① 上图中是没有添加mark标志域和info指针域的邻接多重表。
② 其实无向图的邻接表和邻接多重表的各种基本操作和实现都是类似的，区别就在于同一条边在邻接多重表中仅有一个结点。
③ 通常边结点存储在数组下标靠前的顶点的边链表中，而另一个顶点指向之前已经创建的边结点即可。如果上方创建了多个包含当前顶点的边结点，一般指向离自己最近的那个（如上图中顶点 d 指向了边（c，d）所在的结点）。

绘制的邻接多重表要以美观为主：（便于观察）

• 我们可以先指向上方包含该顶点的边结点，再创建新的边结点，如顶点 v2 先指向边（v1，v2）的结点，再创建并指向边（v2，v3）的结点；
• 我们也可以先创建新的边结点，再指向上方包含该顶点的边结点，如顶点 v4 先创建并指向边（v4，v5）的结点，再指向边（v3，v4）的结点；
• 边结点不一定要与相关联的顶点平行，只要指针指向了就行，如边（v4，v5）的结点与顶点 v6 平行。

4、十字链表

在邻接链表中我们提到了计算有向图的入度十分困难，往往需要遍历整个邻接表或构建逆邻接表。
改进后的十字链表是更方便有向图计算入度和出度的一种链式存储结构（主要是链式存储，包含顺序存储的顶点表）。

顶点结点中包含三个域：（指针域“头在前，尾在后”）

• data：数据域，存储顶点相关的数据信息；
• firstin：指针域，指向以该顶点为弧头的第一个弧节点；
• firstout：指针域，指向以该顶点为弧尾的第一个弧节点。

弧结点中包含五个域：（数据域“发出（尾）在前，接收（头）在后”）

• tailVex（尾域）：数据域，表示该弧的弧尾顶点在图中的位置，即顶点表中的数组下标；
• headVex（头域）：数据域，表示该弧的弧头顶点在图中的位置，即顶点表中的数组下标；
• hLink：指针域，指向弧头相同的下一条弧；
• tLink：指针域，指向弧尾相同的下一条弧；
• info：指针域，指向和该弧相关各种信息的存储地址。

【说明】
① 上图中是没有添加info指针域的十字链表。
② 可以看到绘制十字链表的弧结点时数据域所在位置（头两个）和邻接多重链表（第一、三个）是不一样的，并且不含标志域mark。
③ 十字链表也和多重链表一样，弧结点之间均没有先后顺序之分，所以有向图的十字链表表示、无向图的多重链表表示不唯一。但是反过来一个十字链表可以确定一个有向图，一个多重链表可以确定一个无向图。

• 绘制十字链表时注意要在顶点表间留有空隙，否则不便于firstin指针域指向弧结点；（横向也要留有足够的空隙）
• 可以先将每个顶点作为弧尾的指针补全，然后再将每个顶点作为弧头的指针补全。

第二部分习题

【分析】邻接表、邻接矩阵都是既可以存储有向图又可以存储无向图的，且我们得到的是一个对称的邻接矩阵，所以图 G 有两种可能。

---

第一和二部分小结

图含有大量的专业术语，第一部分中分为15个小点；
图还有四种存储方式，都是顺序+链式存储结构，两种即可存储有向图又可存储无向图，两种分别只能存储无向图或有向图。

---

第三部分：图的遍历

1、深度优先搜索

深度优先搜索也叫深度优先遍历，它的核心思想就是：深究到底。

① 我们先选中某一顶点作为起点，访问该顶点；
② 然后在当前顶点的邻接点中选择一个未被访问过的顶点，访问该顶点。重复该步骤直到当前顶点不存在未被访问的邻接点；
③ 回到最近访问过的一个顶点，要求该顶点还存在未被访问的邻接点，选择其中一个（未被访问的）顶点，访问该顶点；
④ 重复步骤二和三，直到图中所有顶点都被访问过。

由于邻接点选择的不同，访问的顺序也会不同，所以深度优先遍历得到的序列是不唯一的。

【补充】有向图只能沿着弧的指向走，即当前顶点所邻接到的下一个顶点；

2、广度优先搜索

广度优先搜索也叫广度优先遍历，它的核心思想就是：广撒网。
广度优先遍历有点类似于树的层次遍历，但又有着相对严格的顺序要求，这里用到队列来辅助解释遍历过程：

① 我们先选中某一顶点作为起点，将其加入队列，并访问队列中的顶点；
② 将当前顶点的所有未被访问过的邻接点按某一顺序加入队列，然后将当前顶点移出队列；
③ 访问队列中的下一个顶点；
④ 重复步骤二和三，直到队列为空，出队的顺序即为遍历的顺序；

由于入队的顺序不同，访问的顺序也会不同，所以广度优先遍历得到的序列也是不唯一的。

【补充】有向图只能入队以当前顶点为弧尾的弧所关联的顶点，即它所邻接到的顶点；

3、图遍历的生成树

对于无向图来说：

• 若是连通图，在原图中保留顶点与遍历时所经过的边，将构成一个极小连通子图，即深度/广度优先生成树；
• 若是非连通图，需要从多个顶点出发进行遍历，从而构成多个极小连通子图，组成深度/广度优先生成森林；

对于有向图来说：

• 若是强连通图，在原图中保留顶点与遍历时所经过的边，将构成一个极小连通子图，即深度/广度优先有向（生成）树；
• 若是非强连通图，需要从多个顶点出发进行遍历，从而构成多个极小连通子图，组成深度/广度优先生成森林；

• 其实一个强连通的有向图就等价于一个连通的无向图，二者基于邻接矩阵存储的形式是完全一样的（参照第二部分习题）；
• 需要注意，基于邻接矩阵存储的生成树是唯一的；而基于邻接表存储的生成树不是唯一的（参照邻接表部分结点顺序自由）。

---

第四部分：最小生成树

1、最小生成树的定义和性质

最小生成树也叫最小代价树，是带权连通图（即连通网）的生成树集合中，各边权值之和最小的那颗生成树。
最小生成树具有如下性质:

• 带权连通图G的各边权值可能相同，因此最小生成树不是唯一的，即最小生成树的树形不唯一；
  • 仅当图G中的各边权值互不相等时，G的最小生成树是唯一的；
  • 若无向连通图G的边数比顶点数少1，即G本身是一棵树时，则G的最小生成树就是它本身。
• 虽然最小生成树不唯一，但其对应各边的权值之和总是唯一的，而且是最小的；
• 最小生成树的边数为顶点数减1；

2、Prim（普里姆）算法构建最小生成树

① 任意选择带权连通图的一个顶点作为起点，并加入顶点集合；
② 将还在顶点集合外，但与顶点集合内的顶点邻接的顶点找出，选择与这些顶点相关联的边中，权值最小的一条加入边集合，并将对应的那个顶点加入顶点集合；
③ 重复步骤二，直到顶点集合和边集合构成一个含有n个顶点和n-1条边的极小连通子图，它就是最小生成树。

3、Kruskal（克鲁斯卡尔）算法构建最小生成树

① 将带权连通图的全部顶点加入顶点集合；
② 在顶点集合内所有未被连通的顶点之间选择权值最小的一条边加入边集合；
③ 重复步骤二，直到顶点集合和边集合构成一个含有n个顶点和n-1条边的极小连通子图，它就是最小生成树。

第四部分习题

---

第五部分：最短路径

1、最短路径的定义

对于无权图而言，最短路径就是从一个顶点 A 到另一个顶点 B 需经过的边数最少的路径。通常使用广度优先搜索就可以实现：

• 从顶点A出发，开始广度优先搜索，在搜索到顶点B时停止搜索，所得到的子图中顶点A到顶点B的路径就是最短路径。

对于带权图而言，最短路径就是从一个顶点 A 到另一个顶点 B 所经过的边权值之和最小的路径。这类最短路径一般可以分为两类：

• 一类是单源最短路径，即求图中某一个顶点（单个源点）到其他各顶点（多个终点）的最短路径，通常使用经典的迪杰斯特拉算法求解；
• 另一类是求每对顶点间的最短路径，通常使用弗洛伊德算法求解。

2、Dijkstra（迪杰斯特拉）算法生成最短路径

我们通常将一条路径开始的顶点称为源点，结束的顶点称为终点，迪杰斯特拉算法生成的就是开始于同一个顶点的单源最短路径。
我们规定只有和某一顶点通过一条边/弧直接连接的顶点才算能够到达的顶点：
① 首先选择一个顶点A作为源点，列表记录源点到各个顶点的距离，其中能够到达的顶点的距离为边/弧的权值，无法到达的顶点的距离为$\infty$；
② 选择表中记录的距离最近的一个顶点B加入路径，并且后续表格中不再对源点到该顶点的距离做记录；
③ 计算增加顶点B后，能够到达的顶点与源点间的距离，如果小于之前记录的值，就更新表中关于距离和前置路径的记录；
④ 重复步骤二和三直到计算出源点到各个（可以到达的）顶点的最短距离。

（PS：上图中表格和书上相比，行列互换了：此处行是各个终点，列是已经确定的路径集合；书上相反）

【补充】

• 该算法只要求图必须连通而不一定强连通，所以用于有向图时可能会出现源点与某些顶点间不存在路径的情况；
• 有向图中那些与源点间没有路径的顶点（一般来说没有入度只有出度），就需要以自身为源点计算新的单源最短路径；
• 如果图甚至不连通，那就好比要你开车往返于日本和中国间送货，根本没有路，去不了也回不来；

3、Floyd（弗洛伊德）算法生成最短路径

弗洛伊德算法主要求解带权有向图中任意两顶点间的最短路径。我们同样规定只有和某一顶点通过一条弧直接连接的顶点才算能够到达的顶点：
① 先用一个邻接矩阵记录带权有向图各顶点间的距离，若弧$<v_i，v_j>$存在则$A[i][j]$为权值，若弧$<v_i，v_j>$不存在则$A[i][j]$为无穷；
② 在$v_i$和$v_j$之间插入$v_k$，若插入后的路径$(v_i,v_k,v_j)$存在且长度比$A[i][j]$要小，则更新$A[i][j]$为当前路径长度（保存的路径也要更新）；
③ 重复执行步骤二，其中k值按执行次序从0增加到n-1，即步骤二共需执行n次。

第五部分习题

用迪杰斯特拉算法求下列有向图的最短路径。

（PS：同样的图中表格和书上相比行列互换了）

---

第三到五部分小结

图的深度和广度遍历方式常考察算法代码，但还是要了解理论实现方式；
图的遍历是建立生成树（极小连通子图）最可靠的一种办法；
最小生成树是对生成树这一知识点的延伸，主要包含普里姆和克鲁斯卡尔两种算法；
最短路径部分常考察Dijkstra（迪杰斯特拉）算法，需要重点掌握。

思考：单源最短路径与最小生成树的区别

首先要明确一点，生成树一定是对于连通图/强连通图而言的，否则不可能存在某一路径将所有顶点连通——即构成生成森林；
而最小生成树就是在所有生成树当中选择一个各边权值之和最小的生成树，因此同样也要求带权图是连通的无向图或强连通的有向图。
而单源最短路径则仅要求带权图必须是连通的无向图或有向图，从某一顶点到各顶点的所有路径中选出权值最小的一条路径，这也就意味着：

• 对于带权的无向连通图而言，单源最短路径就是最小生成树的其中一种结构。因为各边权值可能出现相同值，所以最小生成树结构往往不唯一，虽然各边权值总和是最小值，却无法保证以根结点作为源点时，到达各顶点的路径最短；而反过来从某一顶点到达其他各顶点都存在最短路径，那么各边权值总和必然为最小值，因此以该顶点作为根节点的生成树必然也是最小生成树。
• 对于带权的有向连通图而言，单源最短路径与最小生成树需分情况讨论。
  • 若该有向图同时还是强连通图，那么同样满足单源最短路径就是最小生成树的其中一种结构；
  • 否则该有向图根本不存在最小生成树，同时需要注意单个顶点同样无法到达其他所有顶点，即单源最短路径不包含全部顶点。

所以求解单源最短路径问题时老老实实使用DJ算法；而求解最小生成树问题时除了采用原有的两种方法，也可以尝试DJ算法。

---

第六部分：拓扑排序

1、有向无环图与拓扑的定义

一个无环（没有顶点存在指向自身的弧）的有向图称为有向无环图，简称DAG图。
所谓“拓扑”就是把实体抽象成与形状大小无关的“点”，而把连接实体的关系抽象成“线”。

2、拓扑排序的步骤

对一个AOV网进行拓扑排序的一种常用方法：
① 从AOV网中选择一个没有前驱（入度为0）的顶点并输出；
② 从网中删除该顶点和所有以它为起点的有向边；
③ 重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止（后一种情况说明有向图中必然存在环）。

AOV网：若用DAG图表示一个工程，其顶点表示活动，用有向边$<V_i,V_j>$表示活动$V_i$必须先于活动$V_j$进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为AOV网。

3、拓扑排序的实际意义

不同于前面最小生成树和最小路径等问题，拓扑排序不关心各个顶点之间的距离以及顶点本身所代表的实体，它更关心不同的顶点之间是否存在一种拓扑关系——邻接。
拓扑排序主要用于处理有向无环图，如果图中各顶点代表的是各种事务，那么研究顶点之间的“邻接”拓扑关系就是研究各事务间开展的先后顺序：

• 某一顶点A的入度为0，表明该顶点没有邻接于任何其他顶点，也就是说该顶点A不存在任何一个前驱顶点；
• 转换回顶点A代表的实际意义，就是说当前事务A之前没有任何其他事务需要处理；
• 在当前顶点A被去除之后，原本该顶点邻接到的其他顶点入度均-1，也就是说以该顶点A为弧尾所连接的弧头顶点们，有可能成为下一个入度为0的顶点（不排除还有其他入度为0的顶点B作为弧尾连接着这些顶点们）；
• 转换回顶点A代表的实际意义，就是说当前事务A完成后，以该事务A作为前置事务的其他事务有可能可以启动了（不排除还有其他前置事务B等）；
• 只有指向某一顶点的所有弧都被去除了，该顶点才能被去除——只有某一事务的所有前置事务都完成了，这一事务才能开始进行；
• 最终有向图变为空——事务全部处理完成；
• 最终有向图中不存在无前驱的顶点（有环，前驱是自己）——有无法执行的事务（有错误，该事务开始的条件就是自身已被完成）。

第六部分习题

【分析】拓扑排序所得序列并不唯一。当存在多个入度为0的顶点时不同的选择顺序会产生不同的序列——当有多个优先级相同的事务时，执行事务的先后顺序会产生不同的事务流程。

---

第七部分：关键路径

1、AOE网的定义

AOE网：若用带权的DAG图表示一个工程，其顶点表示事件，用有向边（弧）表示活动，弧上的权值表示完成活动的开销（如活动持续时间），则将这种有向图称为用边表示活动的网络，记为AOE网。
AOV网和AOE网虽然都是有向无环图，但它们间有一些区别：

• 边和顶点的含义不同：AOV网中顶点就代表某项活动（可以理解为某一事务），而弧/有向边仅仅反映活动的先后顺序；AOE网中顶点确代表某一事件（可以理解为事务发生的诱因），而弧/有向边才代表某项活动（可以理解为某一事务）；
• 有无权值：AOV网中有向边是没有权值的；AOE网中有向边具有权值，且权值代表有向边这一活动的开销。

2、关键路径的定义

在 AOE 网中仅有一个入度为0的顶点，称为开始顶点（源点)，它表示整个工程的开始；网中也仅存在一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。
在 AOE 网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。

• 【定义】因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
• 【意义】完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。

3、关键路径的求解

因为关键活动影响了整个工程的时间，如果关键活动不能按时完成，则整个工程的完成时间就会延长，即关键路径长度增加。
所以只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。寻找关键活动通常关注如下几个参量：

• 事件$v_k$的最早开始时间：指从源点$v_1$到顶点$v_k$的最长路径长度。
  • 初始时将所有顶点的事件最早开始时间置为0；
  • 每个顶点的事件最早开始时间为它的所有前驱顶点的“事件最早开始时间+对应活动持续时间”中的最大值；
  • 可以基于拓扑排序进行运算，当输出一个入度为0的顶点时，计算它所有后继顶点的事件最早开始时间，如果大于顶点当前记录的事件最早开始时间就更新记录。
• 事件$v_k$的最晚开始时间：指从汇点$v_n$到顶点$v_k$的最长路径长度。
  • 初始时将所有顶点的事件最晚开始时间置为与汇点$v_n$的最早开始时间相同；
  • 每个顶点的事件最晚开始时间为它的所有后继顶点的“事件最晚开始时间-对应活动持续时间”中的最小值；
  • 可以拟用拓扑排序进行运算，当输出一个出度为0的顶点时，计算它所有前驱顶点的事件最晚开始时间，如果小于顶点当前记录的事件最晚开始时间就更新记录。
• 活动$<v_i,v_j>$的最早开始时间：等于弧尾顶点，即事件$v_i$最早开始时间。
• 活动$<v_i,v_j>$的最晚开始时间：等于弧头顶点，即事件$v_j$最晚开始时间-活动持续时间。
• 活动$<v_i,v_j>$的时间余量：等于活动的最早开始时间-最晚开始时间。

【补充】
① 活动$<v_i,v_j>$的最晚开始时间不一定等于事件$v_i$的最晚开始时间，但事件$v_i$的最晚开始时间一定等于与它关联的所有活动$<v_i,>$的最晚开始时间的最小值；
② 活动最晚开始时间不可能小于活动最早开始时间；事件最晚开始时间也不可能小于事件最早开始时间；
③ 当事件$v_i$的最早与最晚开始时间相等时，说明存在某一活动$<v_i,v_j>$，它的最晚开始时间是最小值且与最早开始时间相等，即活动$<v_i,v_j>$的最晚开始时间和最早开始时间与事件$v_i$一致。

如果一个活动时间余量为0，说明该活动必须如期完成，否则将拖延整个工程的进程。因此将时间余量为0的活动就是关键活动，由这些活动（带权弧）组成的从源点到汇点的路径就是关键路径。

【★★★】关键路径可能不止一条！！！（详见第七部分习题）

由 补充 - ③ 可知，若活动$<v_i,v_j>$的时间余量为0：（以下两点可用于快速确定关键活动）

• 则活动的最晚开始时间与事件$v_i$的最晚开始时间相同，即事件$v_j$的最晚开始时间-活动$<v_i,v_j>$持续时间=事件$v_i$的最晚开始时间；
• 并且事件$v_i$和事件$v_j$均满足最晚开始时间=最早开始时间，因为事件$v_i$的最早开始时间+活动$<v_i,v_j>$持续时间=事件$v_j$的最早开始时间。

第七部分习题

下列AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（C）。

【分析】缩短工期就是指汇点处事件的最早开始时间和最晚开始时间均减小。

• 首先，关键路径上的所有活动都是关键活动，因此可以通过加快关键活动来缩短整个工程的工期。但要注意不能任意缩短，因为缩短到一定程度时，某些关键活动可能会变成非关键活动；
• 其次，网中的关键路径并不唯一，只提高一条关键路径上的关键活动速度并不能缩短工期，并且还可能导致关键路径变为非关键路径。
• 因此这道题目的核心就是找出所有关键路径，并且加快那些包括在所有关键路径上的关键活动，才能达到缩短工程工期的目的。

本题中关键路径有：$v_1\to v_3\to v_2\to v_4\to v_6$ 和 $v_1\to v_3\to v_2\to v_5\to v_6$ 以及 $v_1\to v_3\to v_5\to v_6$，综合选项分析只有 d 和 f 两个关键活动是包含了所有关键路径的。

---

第六到七部分小结