大家好，我是讯享网，很高兴认识大家。



文章目录

• ​​0 笔记说明​​
• ​​1 图的基本概念​​
• ​​2 图的存储及基本操作​​

• ​​2.1 邻接矩阵法​​
• ​​2.2 邻接表法​​
• ​​2.3 十字链表法​​
• ​​2.4 邻接多重表法​​
• ​​2.5 图的基本操作​​

• ​​3 图的遍历​​

• ​​3.1 广度优先搜索​​

• ​​3.1.1 BFS算法的性能分析​​
• ​​3.1.2 BFS算法求解单源最短路径问题​​
• ​​3.1.3 广度优先生成树​​

• ​​3.2 深度优先搜索​​

• ​​3.2.1 DFS算法的性能分析​​
• ​​3.2.2 深度优先生成树​​

• ​​3.3 图的遍历与图的连通性​​

• ​​4 图的应用​​

• ​​4.1 最小生成树​​

• ​​4.1.1 Prim算法​​
• ​​4.1.2 Kruskal算法​​

• ​​4.2 最短路径​​

• ​​4.2.1 Dijkstra算法求单源最短路径​​
• ​​4.2.2 Floyd算法求各顶点间最短路径​​

• ​​4.3 有向无环图描述表达式​​
• ​​4.4 拓扑排序​​
• ​​4.5 关键路径​​

---

来源于​​2020 王道考研 数据结构​​，博客内容是对自己笔记的书面整理，根据自身学习需要，我可能会增加必要内容。

---

图、顶点和边的英语分别为：graph、vertex、edge。

图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集，E(G)表示图G中顶点之间的关系，也就是边集合。若V={v₁,v₂,…,v_n}，则用|V|表示图G中顶点的个数，也称图G的阶，E={(u,v)|u∈V,v∈V}，用|E|表示图G中边的条数。举个栗子：

讯享网

注意：线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边。

下面是图的一些基本概念及术语：

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

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

3、简单图。图G若满足：① 不存在重复边；② 不存在顶点到自身的边，则称图G为简单图。举个栗子：

4、多重图。若图G中存在重复边或存在顶点到自身的边，则G为多重图。举个栗子：

5、完全图，也称简单完全图。对于无向图，|E|的取值范围是0到n(n-1)/2，有n(n-1)/2条边的无向图称为无向完全图，即在完全图中任意两个顶点之间都存在边。对于有向图，|E|的取值范围是0到n(n-1)，即有n(n-1)条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。下图分别为无向完全图和有向完全图：

6、子图。设有两个图G=(V,E)和G’=(V’,E’)，若V’是V的子集，且E’是E的子集，则称G’是G的子图。若有满足V(G’)=V(G)的子图G’，则称G’为G的生成子图。注意：并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图，即E的子集中的某些边关联的顶点可能不在这个V的子集中。举个栗子，以下图从左到右为G、G1、G2，其中G1是G的子图，而且还是G的生成子图，G2不是G的子图，G2连图都不是：

7、连通、连通图和连通分量。在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。如下图中的v和w是连通的：

无向图中的极大连通子图称为连通分量。对于G的一个连通子图G’，如果不存在G的另一个连通子图G’’，使得G’∈G’’，则称G’为G的极大连通子图，也就是连通分量。举个栗子，下图为一个无向图：

若一个图有n个顶点，并且边数小于n-1，则此图必是非连通图。注意：弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图，极大连通子图是无向图的连通分量，极大即要求该连通子图尽可能包含原图中所有的边；极小连通子图是既要保持图连通又要使得边数最少的子图。举个栗子，下图为无向图，其中右图为左图的一个极小连通子图：

8、强连通、强连通图、强连通分量。在有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。如下图中的v和w是强连通的：

一般在无向图中讨论连通性，在有向图中考虑强连通性。9、生成树、生成森林。连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。举个栗子，以下图从左到右为G、G1、G2，G1、G2均是G的生成树：

注意：包含无向图中全部顶点的极小连通子图，只有生成树满足条件，因为砍去生成树的任一条边，图将不再连通。10、顶点的度、入度和出度。图中每个顶点的度定义为以该顶点为一个端点的边的数目。对于无向图，顶点v_i的度是指依附于该顶点的边的条数，记为TD(v_i)。在具有n个顶点、e条边的无向图中，有：

即无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个顶点相关联。对于有向图，顶点v_i的度分为入度和出度，入度是以顶点v_i为终点的有向边的数目，记为ID(v_i)；而出度是以顶点v_i为起点的有向边的数目，记为OD(v_i)。顶点v_i的度等于其入度和出度之和，即TD(v_i)=ID(v_i)+OD(v_i)。在具有n个顶点、e条边的有向图中，有：

即有向图的全部顶点的入度之和与出度之和相等，并且等于边数。这是因为每条有向边都有一个起点和终点。11、边的权和网。在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。下面是2个示例：

12、稠密图、稀疏图。边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足|E|<|V|log|V|时，可以将G视为稀疏图。下面是2个示例：

13、路径、路径长度和回路。顶点v_p到顶点v_q之间的一条路径是指顶点序列v_p,v_i1,v_i2,…,v_in,v_q，关联的边可理解为路径的构成要素。路径上边的数目称为路径长度。下面是一个示例：

第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n个顶点，并且有大于n-1条边，则此图一定有环。下面是2个示例：

14、简单路径、简单回路。在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

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

16、有向树。只有一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树。下面是一个示例：

---

图的存储方式必须要完整、准确地反映顶点集和边集的信息。根据不同图的结构和使用的算法，采用不同的存储方式将对程序的效率产生相当大的影响，因此所选的存储结构应适合于欲求解的问题。

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，即各顶点之间的邻接关系。存储顶点之间邻接关系的二维数组称为邻接矩阵。结点数为n的图G=(V,E)的邻接矩阵A是n×n阶的。将G的顶点编号为v₁,v₂,…,v_n。若(v_i,v_j)∈E，则A[i][j]=1，否则A[i][j]=0，如下：

对于带权图，也就是网而言，若顶点v_i和v_j之间有边相连，则邻接矩阵中对应项存放着该边对应的权值w_i,j，若顶点v_i和v_j不相连，则用∞来代表这两个顶点之间不存在边，如下：

邻接矩阵法的空间复杂为O(n²)。

图的邻接矩阵存储表示法具有以下特点：

① 无向图的邻接矩阵一定是一个对称矩阵。因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素；

② 对于无向图，邻接矩阵的第i行(或第i列)非零元素或非∞元素的个数正好是第i个顶点的度TD(v_i)；

③ 对于有向图，邻接矩阵的第i行、第i列非零元素或非∞元素的个数分别是第i个顶点的出度OD(v_i)、入度ID(v_i)；

④ 用邻接矩阵法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是若要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价较大；

⑤ 稠密图适合使用邻接矩阵的存储表示；

⑥ 设图G的邻接矩阵为A，Aⁿ的元素Aⁿ[i][j]等于由顶点i到顶点j的长度为n的路径的数目。举个栗子，下图为一个有向图：

（1）A²[2][5]=2，表示从顶点2到顶点5长度为2的路径有2条，也就是说从顶点B到顶点E长度为2的路径有2条，确实是这样，两条路径为：B-C-E、B-A-E；

（2）A²[2][3]=1，表示从顶点2到顶点3长度为2的路径有1条，也就是说从顶点B到顶点C长度为2的路径有1条，确实是这样，路径为：B-A-C；

（3）A³[2][5]=1，表示从顶点2到顶点5长度为3的路径有1条，也就是说从顶点B到顶点E长度为3的路径有1条，确实是这样，路径为：B-A-C-E。

当要存储的图为稀疏图时，使用邻接矩阵法会浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储，大大减少了这种不必要的浪费。

邻接表法，是指对图G中的每个顶点v_i建立一个单链表，第i个单链表中的结点表示依附于顶点v_i的边(对于有向图则是以顶点v_i为尾的弧)，这个单链表就称为顶点v_i的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种结点：顶点表结点和边表结点，如下图所示：

图的邻接表存储具有以下特点：

① 若G为无向图，则所需的存储空间为O(|V|+2|E|)；若G为有向图，则所需的存储空间为O(|V|+|E|)。无向图的倍数2是由于每条边在邻接表中存储了两次；

② 对于稀疏图，采用邻接表表示将极大地节省存储空间；

③ 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，只需读取该结点的邻接表即可。在邻接矩阵中，给定一顶点，要找出它的所有邻边，则需要扫描邻接矩阵中该结点对应的那一行，花费的时间为O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低；

④ 在无向图的邻接表表示中，结点的度为该结点边表的长度。在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，可以采用逆邻接表的存储方式来加速求解给定顶点的入度，这实际上与邻接表存储方式是类似的；

⑤ 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

十字链表是有向图的一种链式存储结构。

1）尾域(tailvex)和头域(headvex)分别指示弧尾和弧头这两个顶点在图中的位置；

2）链域hlink指向弧头相同的下一条弧；链域tlink指向弧尾相同的下一条弧；info域指向该弧的相关信息。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上。

顶点结点中有3个域：

1）data域存放顶点相关的数据信息，如顶点名称；

2）firstin、firstout分别指向以该顶点为弧头、弧尾的第一个弧结点。

在十字链表中，既容易找到以顶点V_i为尾的弧，也容易找到以顶点V_i为头的弧，因而容易求得顶点的出度和入度。图的十字链表表示是不唯一的，但一个十字链表表示唯一确定一个图。

邻接多重表是无向图的一种链式存储结构。

在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边或执行删除边等操作时，需要分别在两个顶点的边表中遍历，效率较低。

无向图的邻接多重表的存储结构的C++代码如下：

图的基本操作独立于图的存储结构，对不同的存储方式，具体操作的算法的具体实现会有着不同的性能。在设计具体算法的实现时，应考虑采用何种存储方式的算法效率会更高。

图的基本操作主要包括(仅抽象地考虑，故忽略掉各变量的类型)：

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

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

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

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

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

6、RemoveEdge(G,x,y)：若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边。

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

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

9、Get_edge_value(G,x,y)：获取图G中边(x,y)或<x,y>对应的权值。

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

---

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。可以将树看作为一种特殊的图，所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

图的遍历比树的遍历要复杂得多，因为图的任一顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设置一个辅助数组visited[]来标记顶点是否被访问过。图的遍历算法主要有两种：广度优先搜索(遍历)和深度优先搜索(遍历)。

广度优先搜索(Breadth-First-Search，BFS)类似于二叉树的层序遍历算法。基本思想是：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w₁,w₂,…,w_i，然后依次访问w₁,w₂,…,w_i的所有未被访问过的邻接顶点，然后再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点…直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中任意一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先遍历图的过程是以v为起始点，由近至远依次访问和v有路径相通且路径长度依次为1、2、…的顶点。广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像后面要讨论的深度优先搜索那样有回退的情况，因此它不是一个递归算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。广度优先搜索算法的伪代码如下：

辅助数组visited[]用于标记每个顶点是否被访问过，每个顶点的初始状态为False，代表未被访问过。在图的遍历过程中，一旦顶点v_i被访问，就立即置visited[i]为true，以防止顶点v_i被重复访问。下面通过一个实例演示广度优先搜索的过程，给定图G如下图所示：

从上例不难看出，图的广度优先搜索的过程与二叉树的层序遍历是完全一致的，这也说明了图的广度优先搜索遍历算法是二叉树的层次遍历算法的扩展。

图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的BFS序列是唯一的，基于邻接表的遍历所得到的BFS序列是不唯一的。

3.1.1 BFS算法的性能分析

无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q，n个顶点均需入队一次，在最坏的情况下，空间复杂度为O(|V|)。

采用邻接表存储方式时，每个顶点均需搜索一次(或入队一次)，故时间复杂度为O(|V|)，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为O(|E|)，算法总的时间复杂度为O(|V|+|E|)。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为O(|V|)，故算法总的时间复杂度为O(|V|²)。

3.1.2 BFS算法求解单源最短路径问题

若图G=(V,E)为非带权图，定义从顶点u到顶点v的最短路径d(u,v)为从u到v的任意一条路径中最少的边数；若从u到v没有路径，则d(u,v)=∞。使用BFS可求解一个满足上述定义的非带权图的单源最短路径问题，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。

通过BFS算法求解单源最短路径问题的伪代码如下：

3.1.3 广度优先生成树

深度优先搜索(Depth-First-Search，DFS)类似于树的先序遍历。DFS的基本思想如下：首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点w₁，再访问与w₁邻接且未被访问的任一顶点w₂……不断重复上述过程，当不能再继续向下访问时，依次回退到最近刚被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

DFS算法的伪代码如下：

图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列是唯一的，基于邻接表的遍历所得到的DFS序列是不唯一的。

3.2.1 DFS算法的性能分析

DFS算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为O(|V|)。遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所用的存储结构。以邻接矩阵表示时，查找每个顶点的邻接点所需的时间为O(|V|)，故总的时间复杂度为O(|V|²)。以邻接表表示时，查找所有顶点的邻接点所需的时间为O(|E|)，访问顶点所需的时间为O(|V|)，此时，总的时间复杂度为O(|V|+|E|)。

3.2.2 深度优先生成树

图的遍历算法可以用来判断图的连通性。

对于无向图来说，若无向图是连通的，则从任一结点出发，仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。因此在BFSTraverse()和DFSTraverse()中添加了第二个for循环，再选取初始点，继续进行遍历，以防止一次无法遍历图的所有顶点。对于无向图，上述两个函数调用BFS(G,i)、DFS(G,i)的次数均等于该图的连通分量数；而对于有向图则不是这样，因为一个连通的有向图分为强连通的和非强连通的，它的连通子图也分为强连通分量和非强连通分量，非强连通分量一次调用BFS(G,i)或DFS(G,i)无法访问到该连通分量的所有顶点。

---

图的应用主要包括：

（1）最小生成树；

（2）最短路径；

（3）拓扑排序；

（4）关键路径。

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

3）最小生成树的边数为顶点数减1。

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

基于上述性质的最小生成树算法主要有Prim算法和Kruskal算法，二者都是基于贪心算法的策略。下面是一个通用的最小生成树算法伪代码：

简而言之就是通过不断加入一条最小权值边以逐渐形成一棵生成树。下面介绍两种实现上述通用算法的具体算法。

假设G={V，E}是连通图，其最小生成树T=(U,E_T)，其中U是最小生成树T的顶点集，E_T是最小生成树T的边集。Prim算法描述如下：

（1）初始化：向空树T=(U,E_T)中添加图G=(V,E)的任一顶点u₀，使U={u₀}，E_T=Ø；

（2）不断重复接下来的操作直至U=V：从图G中选择满足{(u,v)|u∈U,v∈V-U}且具有最小权值的边(u,v)，加入树T，置U=U∪{v}，E_T=E_T∪{(u,v)}。

Prim算法的伪代码如下：

Prim算法的C++代码如下：

Prim算法中有两个for循环嵌套，因此时间复杂度为O(|V|²)，其复杂度不依赖于边数|E|，因此Prim算法适用于求解稠密图的最小生成树。

与Prim算法从顶点开始扩展最小生成树不同，Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

Kruskal算法：初始时为只有n个顶点而无边的非连通图T={V，{}}，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边。以此类推，直至T中所有顶点都在一个连通分量上。

假设G=(V，E)是连通图，其最小生成树T=(U,E_T)。Kruskal算法的步骤如下：

（1）初始化：U=V，E_T=Ø，即每个顶点构成一棵独立的树，T此时是一个仅含|V|个顶点的森林；

（2）不断重复接下来的操作直至T是一棵树：按G的边的权值递增顺序依次从E-E_T中选择一条边，若这条边加入T后不构成回路，则将其加入E_T，否则舍弃，直到E_T中含有n-1条边。

Kruskal算法的伪代码如下：

Kruskal算法的C++代码如下：

在上述Kruskal算法的代码中，采用了堆这种数据结构来存放边的集合。此外，由于生成树T中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此采用了并查集（可浏览​​此博文​​的【4.4 树的应用——并查集】一节）的数据结构来描述T。上述算法的时间复杂度为O(|E|log|E|)，其复杂度不依赖于顶点数|V|，因此Kruskal算法适用于求解稀疏图的最小生成树。

【3.1.2 BFS算法求解单源最短路径问题】一节所述的广度优先搜索查找最短路径只是对无权图而言的。当图是带权图时，把从一个顶点v₀到图中其余任意一个顶点v_i的一条路径(可能不止一条)所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径。

求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。带权有向图G的最短路径问题一般可分为两类：

（1）单源最短路径，即求图中固定的某一顶点（即单源顶点）到其他顶点的最短路径。可通过Dijkstra算法求解；

（2）各顶点间最短路径。可通过Floyd算法求解。

Dijkstra算法设置了三个辅助数组：

（1）dist[]：记录从源点v₀到其他各顶点当前的最短路径长度，它的初始状态为：若从v₀到v_i有弧，则令dist[i]=edge[0][i]，否则置dist[i]=∞；

（2）path[]：path[i]表示从源点v₀到顶点v_i之间的最短路径上的最后一条边的除顶点v_i外的另一个顶点。在算法结束时，可根据其值追溯得到源点v₀到顶点v_i的最短路径上经过的顶点序列。它的初始状态为：源点v₀下标的值初始化为-1，若源点v₀到顶点v_i有一条有向边(无向边)，则令path[i]=0，否则path[i]=-1；

（3）s[]：s[i]=0表示顶点v_i未确定最短路径，s[i]=1表示顶点v_i已确定最短路径。它的初始状态为：除源点v₀下标的值为1外其他值全部初始化为0。

假设从源点v₀出发，使用邻接矩阵edge表示带权有向图，edge[i][j]表示有向边<i,j>的权值，若不存在有向边<i,j>，则edge[i][j]为∞。

Dijkstra算法的步骤如下：

1）初始化：按照前面提到的方式初始化三个数组dist[]、path[]、s[]；

2）从s[i]=0的顶点集中选出某个顶点v_j，使其满足dist[j]=Min{dist[i]}，v_j就是当前求得的一条从v₀出发的最短路径的终点，令s[j]=1；

3）判断是否需要修改从v₀出发到s[k]=0的每个顶点v_k可达的最短路径长度：若dist[j]+edge[j][k]<dist[k]，则更新dist[k]=dist[j]+edge[j][k]，且令path[k]=j；

4）重复步骤2、3共n-1次，直到对于任意一个顶点v_i都有s[i]=1。上述的步骤3解决了一个疑问——为什么加入新顶点后需要更新从顶点v₀到未确定好的顶点间的最短路径长度？直接举例说明：

对于上图，假设刚开始没有顶点v₁和边<0,1>、<1,2>，只有顶点v₀、v₂和边<0,2>，设源点为v₀，因此dist[2]=7。当加入顶点v₁后，因为3+1=4<7，因此dist[2]需要更新为4。下面举一个例子，对于下图：

当使用邻接矩阵表示法存储图时，Dijkstra算法的时间复杂度为O(|V|²)。当使用邻接表表示法存储图时，虽然修改dist[]数组的时间减少了，但由于在dist[]数组中选择最小值的时间不会变，因此Dijkstra算法的时间复杂度仍为O(|V|²)。有时候只希望找到从源点到某个特定顶点的最短路径，但这个问题和求解源点到其他所有顶点的最短路径一样复杂，因此时间复杂度也为O(|V|²)。

当图的边上带有负权值时，Dijkstra算法并不管用，这是由于在Dijkstra算法中已求得最短路径的顶点的最短路径不能再进行变更，就算某最短路径长度加上负边的权值结果小于原先已确定的最短路径长度，此时在Dijkstra算法下也是无法更新为该最短路径长度的。举个栗子，对于下图所示的带权有向图，利用Dijkstra算法不一定能得到正确的结果：

在上图中，假设从顶点0到顶点2已确定好了最短路径，路径长度为5。当加入了顶点1时，因为存在通路v₀→v₁→v₂，因此从顶点0到顶点2的最短路径长度变为7-5=2。但是由于已求得最短路径的顶点的最短路径不可以再变更，也就是说此时从顶点0到顶点2的最短路径长度在Dijkstra算法下是无法更新的。

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

求所有顶点之间的最短路径问题描述如下：已知一个各边权值均大于0的带权有向图，对任意两个顶点v_i≠v_j，要求求出v_i与v_j之间的最短路径及最短路径长度。

Floyd算法的基本思想是：递推产生一个n阶方阵的序列：A^(-1)，A⁽⁰⁾,…,A⁽¹⁾,…,A^(n-1)，其中A^(k)[i][j]表示从顶点v_i到顶点v_j的路径长度，且绕行的顶点编号不大于k。初始时，对于任意两个顶点v_i和v_j，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在边，则以∞作为它们之间的最短路径长度。之后逐步尝试在原路径中加入顶点k作为中间顶点，其中k=0,1,…,n-1。若增加中间顶点k后，得到的路径的长度比原来的路径长度减少了，则以此新路径代替原路径。

Floyd算法描述如下：定义一个n阶方阵的序列A^(-1)，A⁽⁰⁾,…,A⁽¹⁾,…,A^(n-1)，初始化A^(-1)[i][j]=edge[i][j]；当k=0,1,…,n-1时，A^(k)[i][j]=Min{A^(k-1)[i][j], A^(k-1)[i][k]+A^(k-1)[k][j])。如下：

A⁽⁰⁾[i][j]是从顶点v_i到v_j、中间顶点是v₀的最短路径的长度，A^(k)[i][j]是从顶点v_i到v_j、中间顶点的序号不大于k的最短路径的长度。Floyd算法是一个迭代的过程，每迭代一次，在从v_i到v_j的最短路径上就多考虑了一个顶点。经过n次迭代后，所得到的A^(n-1)[i][j]就是v_i到v_j的最短路径长度，即方阵A^(n-1)中保存了任意一对顶点之间的最短路径长度。举个栗子，对于下图：

刚开始时，A^(-1)为：

最后得到的A⁽³⁾[i][j]就是从顶点i到顶点j的最短路径长度，如A⁽³⁾[2][3]=4，则从顶点2到顶点3的最短路径长度为4。

Floyd算法的C++代码如下：

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

Floyd算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。Floyd算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。

其实也可以用Dijkstra算法来解决每对顶点之间的最短路径问题：轮流将每个顶点作为源点，并且在所有边权值均非负时，运行一次Dijkstra算法，其时间复杂度也为O(|V|²)·|V|=O(|V|³)。

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

上述二叉树可表示​​，在表达式中，有一些相同的子表达式：(c+d)和(c+d)*e，而在上图的二叉树中，这些结点也重复出现。利用有向无环图可实现对相同子式的共享，从而节省存储空间。下图为该表达式的有向无环图表示：

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

由一个有向无环图的顶点组成的序列，当：① 每个顶点出现且只出现一次；② 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。则称该序列为该图的一个拓扑排序序列。

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

对一个AOV网进行拓扑排序的步骤：

① 从AOV网中选择一个入度为0的顶点并输出；

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

由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为O(|V|+|E|)。

对一个AOV网，如果采用下列步骤进行排序：

① 从AOV网中选择一个出度为0的顶点并输出；

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

不断重复①和②直到当前的AOV网为空。则称得到的序列为逆拓扑排序序列。

用拓扑排序算法处理AOV网时，应注意以下问题：

① 对于入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续；

② 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；

③ 由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成AOV网的新的邻接矩阵。

对于一般的图来说，若其邻接矩阵是三角矩阵，则一定存在拓扑排序序列，反之不一定成立。

以顶点表示事件、以有向边表示活动、以边上的权值表示完成该活动的开销的带权有向图，称之为用边表示活动的网络，英文为Activity On Edge Network，即AOE网。

AOE网和AOV网都是有向无环图，不同之处：

（1）AOE网使用边表示活动；AOV网使用顶点表示活动；

（2）AOE网中的边有权值；AOV网中的边无权值，仅表示顶点之间的前后关系。

AOE网具有以下两个性质：

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

（2）只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

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

在AOE网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。

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

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

以下是在寻找关键活动时所用到的5个量：

（1）事件v_k的最早发生时间ve(k)：它是指从源点v₁到顶点v_k的最长路径长度。事件v_k的最早发生时间决定了所有从v_k开始的活动能够开工的最早时间。可用下面的递推公式来计算：

ve(源点)=0，ve(k)=Max{ve(j)+Weight(v_j,v_k)}，v_k为v_j的任意后继，Weight(v_j,v_k)表示<v_j,v_k>上的权值。

计算ve(k)值时，按从前往后的顺序进行，可以在拓扑排序序列的基础上计算：

① 初始时，令ve[1…n]=0；

② 输出一个入度为0的顶点v_j时，计算它所有直接后继顶点v_k的最早发生时间，若ve[j]+Weight(v_j,v_k)>ve[k]，则ve[k]=ve[j]+Weight(v_j,v_k)。以此类推，直至输出全部顶点。

（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(k)时，按从后往前的顺序进行，可以在逆拓扑排序序列的基础上计算——在拓扑排序中，增设一个栈以记录拓扑排序序列，拓扑排序结束后从栈顶至栈底依次弹出的序列便为逆拓扑排序序列。过程如下：

① 初始时，令vl[1…n]=ve[n]；

② 栈顶顶点v_j出栈，计算其所有直接前驱顶点v_k的最迟发生时间，若vl[j]-Weight(v_k,v_j)<vl[k]，则vI[k]=vl[j]-Weight(v_k,v_j)。以此类推，直至输出全部栈中顶点。

（3）活动a_i的最早开始时间e(i)：它是指该活动弧的起点所表示的事件的最早发生时间。若边<v_k,v_j>表示活动a_i，则有e(i)=ve(k)。

（4）活动a_i的最迟开始时间l(i)：它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。若边<v_k,v_j>表示活动a_i，则有l(i)=vl(j)-Weight(v_k,v_j)。

（5）一个活动a_i的最迟开始时间l(i)和其最早开始时间e(i)的差额d(i)=l(i)-e(i)：它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动a_i可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称l(i)-e(i)=0，即l(i)=e(i)的活动a_i是关键活动。

因此，该AOE网的关键路径为：{a₂，a₅，a₇}，关键活动为：v₁、v₃、v₄、v₆。

对于关键路径，需要注意以下2点：

1）关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。

2）网中的关键路径并不唯一，且对于有多条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

---

END