王道-数据结构-ch6-图

王道

图

知识结构

• 图的定义
• 图结构的存储
  • 顺序存储结构：
    • 邻接矩阵法(有向图，无向图)
  • 链式存储结构：
    • 邻接表法（树的孩子表示法）、邻接多重表(无向图)、十字链表(有向图)
• 图的遍历
  • 深度优先遍历
  • 广度优先遍历
• 图的相关应用
  • 最小生成树:Prim算法、Kruskal 算法
  • 最短路径:Dijkstra算法、Floyd 算法
  • 拓扑排序:AOV网
  • 关键路径:AOE 网

存储结构	优势
邻接矩阵法
邻接表法
邻接多重表
十字链表

$\color{red}{\text{注意}}$:图的顺序存储和图的链式存储中指的$\color{green}{\text{稀疏图}}$和$\color{green}{\text{稠密图}}$是对于边而言的，边稠密，边稀疏
拓扑排序是关键路径的前提，时间复杂度为什么是O（n+e）

• $\mho$(要补充的内容) $\color{red}{\text{Q}}$：图的广度优先搜索和深度优先搜索的优劣，同理树
• $\color{red}{\text{Q}}$:邻接矩阵中没有边应该用0还是无穷表示
• 很喜欢考$\color{red}{\text{所有}}$，$\color{red}{\text{总数}}$

单词	含义
Directed Acyclic Graph	有向无环图
Critical Path	关键路径

图的基本概念

图的定义

图$G$由顶点集$V$和边集$E$组成，记为$G=(V,E)$，其中$V(G)$表示图$G$中顶点的有限非空集;$E(G)$表示图$G$中顶点之间的关系(边）集合。若$V=\lbrace v_1,v_2,\cdots, v_n \rbrace$，则用$\lvert V \rvert$表示图$G$中顶点的个数，$E= \lbrace (u, v) \vert u \in V,v \in V$，用$\lvert E \rvert$表示图$G$中边的条数。

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

有向图

若$E$是$\color{red}{\text{有向边}}$(也称$\color{green}{\text{弧}}$）的有限集合时，则图$G$为有向图。弧是顶点的$\color{green}{\text{有序对}}$，记为$< v, w >$，其中$v$, $w$是顶点，$v$称为$\color{green}{\text{弧尾}}$，$w$称为$\color{green}{\text{弧头}}$，$< v, w >$称为从$v$到$w$的弧，也称$v$邻接到$w$。

图6.1(a)所示的有向图G可表示为

$$\begin{cases} G_1=(V_1, E_1) , \cr V= \lbrace 1,2,3 \rbrace , \cr E = \lbrace <1,2>,<2,1>,<2,3>\rbrace \end{cases}$$

无向图

若$E$是$\color{green}{\text{无向边}}$（简称边）的有限集合时，则图$G$为无向图。边是顶点的无序对，记为$(v, w)$或$(w, v)$。可以说$w$和$v$互为邻接点。边$(v, w)$依附于$w$和$v$，或称边$(v, w)$和 $v, w$相关联。

图6.1(b)所示的无向图$G_1$,可表示为

$$\begin{cases} G_1=(V_2, E_2) , \cr V= \lbrace 1,2,3,4 \rbrace , \cr E = \lbrace (1,2), (1,3), (1,4), (2,3), (2,4),(3,4)\rbrace \end{cases}$$

简单图、多重图

一个图$G_2$如果满足:①不存在重复边;②不存在顶点到自身的边，那么称图G为简单图。图6.1中$G$和 $G$均为$\color{green}{\text{简单图}}$。若图$G$中某两个顶点之间的边数大于1条，又允许顶点通过一条边和自身关联，则称图$G$为$\color{green}{\text{多重图}}$。多重图和简单图的定义是相对的。数据结构中仅讨论简单图。

完全图(也称简单完全图)

对于无向图，$\lvert E \rvert$的取值范围为0到$n(n -1)/2$，有$n(n -1)/2$条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，$\lvert E \rvert$的取值范围为0到$n(n-1)$，有$n(n -1)$条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。图6.1中$G$,为无向完全图，而$G$为有向完全图。

子图

设有两个图$G=(V, E)$和$G’=(V’,E’)$，若$V’$是$V$的子集，且$E’$是$E$的子集，则称$G’$是$G$的子图。若有满足$V(G’)=V(G)$的子图$G’$，则称其为$G$的生成子图。图6.1中$G_3$为$G_1$的子图。

注意:并非$V$和$E$的任何子集都能构成$G$的子图，因为这样的子集可能不是图，即$E$的子集中的某些边关联的顶点可能不在这个$V$的子集中。

$\color{red}{\text{必须是真子集吗}}$

连通、连通图和连通分量

在无向图中，若从顶点$v$到顶点$w$有路径存在，则称$v$和$w$是$\color{green}{\text{连通}}$的。若图$G$中任意两个顶点都是连通的，则称图$G$为$\color{green}{\text{连通图}}$，否则称为$\color{green}{\text{非连通图}}$。无向图中的$\color{green}{\text{极大连通子图}}$称为$\color{green}{\text{连通分量}}$，在图6.2(a)中，图$G_4$有3个连通分量如图6.2(b)所示。假设一个图有n个顶点，如果边数小于$n -1$，那么此图必是$\color{green}{\text{非连通图}}$;思考，如果图是非连通图，那么最多可以有多少条边?$\color{green}{\text{n-2}}$(考虑图是一个树)

非连通情况下边最多的情况:由$n-1$个顶点构成一个完全图，此时再任意加入一条边则变成连通图。

极大连通子图：点和边尽可能多

顶点的度、入度和出度

在无向图中，顶点$v$的度是指依附于顶点$v$的边的条数，记为$TD(v)$。在图6.1(b)中，每个顶点的度均为3。对于具有$n$个顶点、$e$条边的无向图，$\color{red}{\displaystyle \sum_{i=1}^n TD(v,)=2e}$，即无向图的全部顶点的度$i=1$的和等于边数的2倍，因为每条边和两个顶点相关联。

在有向图中,顶点$v$的度分为入度和出度,入度是以顶点v为终点的有向边的数目,记为ID(v);而出度是以顶点v为起点的有向边的数目，记为OD(v)。在图6.1(a)中，顶点2的出度为2、入度为1。顶点v的度等于其入度与出度之和，即TD(v)= ID(v)+OD(v)。对于具有n个顶点、e条边的有向图，艺ID(y)=>oD(v,)=e，即有向图的全部顶点的入度之和与出度之和相等，并且等
i=1
于边数，这是因为每条有向边都有一个起点和终点。

边的权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为$\color{green}{\text{带权图}}$，也称$\color{green}{\text{网}}$。

稠密图、稀疏图

边数很少的图称为$\color{green}{\text{稀疏图}}$，反之称为$\color{green}{\text{稠密图}}$。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图$G$满足$\lvert E \rvert < \lvert V \rvert log\lvert V \rvert$时，可以将$G$视为稀疏图。

路径、路径长度和回路

顶点$v$,到顶点 $v$之间的一条路径是指顶点序列$vp,v{i1},v{i2},\cdots,v{i_m},v_q$,，当然关联的边也可理解为路径的构成要素。路径上边的数目称为$\color{green}{\text{路径长度}}$。第一个顶点和最后一个顶点相同的路径称为$\color{green}{\text{回路}}$或$\color{green}{\text{环}}$。若一个图有n个顶点，并且有大于n-1条边，则此图$\color{red}{\text{一定有环}}$。

简单路径、简单回路

在路径序列中，顶点不重复出现的路径称为$\color{green}{\text{简单路径}}$。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为$\color{green}{\text{简单回路}}$。

距离

从顶点$u$出发到顶点$v$的最短路径若存在，则此路径的长度称为从$u$到$v$的$\color{green}{\text{距离}}$。若从$u$到$v$根本不存在路径，则记该距离为无穷($\infty$)。

有向树

一个顶点的入度为0、其余顶点的入度均为1的有向图，称为$\color{green}{\text{有向树}}$。

图的存储及基本操作

邻接矩阵法:稠密图

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。

结点数为$n$的图$G=(V, E)$的邻接矩阵$A$是$n \times n$的。将$G$的顶点编号为$v_1,v_2, \cdots, v_n$。若$(v_i, v_j) \in E$,$A[i][j]=1$，否则$A[i][j]=0$。

无权图

$$A[i][j] = \begin{cases} 1, & \text{若}(v_i,v_j) \text{或} <v_i, v_j>\text{是}E(G)\text{中的边} \cr 0, &\text{或}\infty,\text{若}(v_i,v_j) \text{或} <v_i, v_j>\text{不是}E(G)\text{中的边} \end{cases}$$

带权图的表示，用$\infty$来表示两个顶点之间不存在边

$$A[i][j] = \begin{cases} w_{ij}, & \text{若}(v_i,v_j) \text{或} <v_i, v_j>\text{是}E(G)\text{中的边} \cr 0\text{或}\infty, &\text{或}\infty,\text{若}(v_i,v_j) \text{或} <v_i, v_j>\text{不是}E(G)\text{中的边} \end{cases}$$

图的邻接矩阵存储结构定义如下:

#define MaxvertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
  VertexType Vex [MaxVertexNum];//顶点表
  EdgeType Edge[MaxVertexNum] [MaxVertexNum];//邻接矩阵,边表
  int vexnum, arcnum;//图的当前顶点数和弧数
}MGraph;

在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略)。
当邻接矩阵的元素仅表示相应边是否存在时，EdgeType可采用值为0和1的枚举类型。
无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。
邻接矩阵表示法的空间复杂度为$O(n^2)$，其中$n$为图的顶点数$\lvert V \rvert$。

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

①无向图的邻接矩阵一定是一个对称矩阵（并且唯一)。因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
②对于无向图，邻接矩阵的第$i$行（或第$i$列）非零元素(或非元素）的个数正好是顶点$i$的度 $TD(v)$。对于有向图,邻接矩阵的第$i$行非零元素(或非$\infty$元素)的个数正好是顶点$i$的出度$OD(v_i)$;第$i$列非零元素（或非元素）的个数正好是顶点$i$的入度$ID(v_i)$。(口诀：行出列入)
④用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图
中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。$\color{red}{\text{稠密图适合使用邻接矩阵的存储表示}}$。
⑥设图$G$的邻接矩阵为$A$，$A^n$的元素$A[i][j]$等于由顶点$i$到顶点$j$的长度为$n$的路径的数目。该结论了解即可，证明方法请参考离散数学教材。

邻接表法:稀疏图

相当于树的孩子表示法，一个数组下标表示$\color{green}{\text{对应顶点}}$顶点编号，内容是一个链表，内容是$\color{green}{\text{其}}$指向的顶点编号（邻接表），逆邻接表:指向$\color{green}{\text{其}}$的定点编号

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

顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc)构成，边表（邻接表）结点由邻接点域(adjvex）和指向下一条邻接边的指针域(nextarc)构成。

$\color{red}{\text{有趣的是}}$，虽然$\color{green}{\text{顶点表}}$叫顶点$\color{yellow}{\text{表}}$，但他其实“本质”只是个一维数组，$\color{red}{\text{边表}}$里面名字中又有$\color{green}{\text{边}}$，又有$\color{green}{\text{表}}$，但其实要么只记录$\color{green}{\text{入点}}$（指向对应顶点表的点），或者$\color{green}{\text{出点}}$（顶点表中的点指向的点），而$\color{green}{\text{表}}$，也“无从谈起”，他其实是散落着的一种状态，靠指针连接起来（中文的日常用语中的表有有列是一个二维的“excel”），这里取其英文名的直译无论从编程上还是理解上都更直观，adjacency list（邻接点的清单）

无向图和有向图的邻接表的实例分别如图6.7和图6.8所示。

图的邻接表存储结构定义如下:

#define MaxVertexNum 100 // 图中顶点数目的最大值
typedef struct ArcNode { //边表结点
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *next; //指向下一条弧的指针
// InfoType info;//网的边权值
}ArCNode;
typedef struct VNode {//顶点表结点
VertexType data;//顶点信息
ArcNode *first;//指向第一条依附该顶点的弧的指针
} VNode, AdjList [MaxvertexNum];
typedef struct{
AdjList vertices;//邻接表
int vexnum, arcnum;//图的顶点数和弧数
}ALGraph;//ALGraph是以邻接表存储的图类型

图的邻接表存储方法具有以下特点:

若$G$为无向图，则所需的存储空间为$O(\lvert V \rvert +2 \lvert E \rvert )$;若$G$为有向图，则所需的存储空间为$O(\lvert V \rvert +\lvert E \rvert )$。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。
对于稀疏图,采用邻接表表示将极大地节省存储空间。
在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为$O(n)$。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。(总结：查某顶点的边效率高，查顶点间是否存在边效率低)
在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数;但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。
图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

十字链表:有向图

十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。这些结点的结构如下图所示。

弧结点中有5个域:尾域(tailvex）和头域(headvex）分别指示弧尾和弧头这两个顶点在图中的位置;链域hlink指向弧头相同的下一条弧;链域tlink 指向弧尾相同的下一条弧;info域指向该弧的相关信息。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上。

顶点结点中有 3个域: data域存放顶点相关的数据信息，如顶点名称;firstin和firstout两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。图6.9为有向图的十字链表表示法。注意，顶点结点之间是顺序存储的。

顶点结点中有3个域: data域存放顶点相关的数据信息，如顶点名称;firstin和firstout两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。

$\color{red}{\text{有趣的是}}$，如何$\color{green}{\text{理解}}$中文翻译中的十字呢？如果将边（弧）节点的nextIn(hlink)和nextOut(tlink)域看成两个轴的话，那么确实相当于一个十字穿过了边（弧）节点，又有$\color{green}{\text{链}}$(指针)，这名字到有几分合理。如何快速找到一个顶点节点的所有的nextOut弧节点(tailvex）呢？看弧节点的tailvex就行了，

图6.9为有向图的十字链表表示法。注意，顶点结点之间是顺序存储的。

在十字链表中，既容易找到$V$为尾的弧，又容易找到$V$为头的弧，因而$\color{red}{\text{容易求得顶点的出度和入度}}$。图的十字链表表示是不唯一的，但一个十字链表表示确定一个图。

邻接多重表：无向图

实际上相当于压缩无向图$\color{green}{\text{邻接表}}$的压缩存储方式，一条边仅由一个节点表示

邻接多重表是$\color{green}{\text{无向图}}$的另一种链式存储结构。

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

与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构如下所示。

其中，$\text{mark}$为标志域，可用以标记该条边是否被搜索过;$\text{ivex}$和$\text{jvex}$为该边依附的两个顶点在图中的位置; $\text{ilink}$ 指向下一条依附于顶点$\text{ivex}$的边; $\text{jlink}$指向下一条依附于顶点$\text{jvex}$的边，$\text{info}$为指向和边相关的各种信息的指针域。

每个顶点也用一个结点表示，它由如下所示的两个域组成。

其中，data域存储该顶点的相关信息，firstedge域指示第一条依附于该顶点的边。

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

图6.10为无向图的邻接多重表表示法。邻接多重表的各种基本操作的实现和邻接表类似。

图的基本操作

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。

图的遍历

为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组$\text{visited[ ]}$来标记顶点是否被访问过。

广度优先搜索

广度优先搜索（Breadth-First-Search, BFS）类似于二叉树的$\color{red}{\text{层序遍历算法}}$。基本思想是:首先访问起始顶点$v$，接着由$v$出发，依次访问$v$的各个未访问过的邻接顶点$w_i, w_2,\cdots, w_i$，然后依次访问$w_i, w_2,\cdots, w_i$的所有未被访问过的邻接顶点;再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。Dijkstra单源最短路径算法和 Prim最小生成树算法也应用了类似的思想。

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

广度优先搜索算法的伪代码如下:

bool visited [MAX VERTEX NUM];//访问标记数组
void BFSTraverse (Graph G){ //对图G进行广度优先遍历
  for(i=0;i<G.vexnum;++i)
    visited[i]=FALSE; //访问标记数组初始化
  InitQueue (Q);//初始化辅助队列o
  for(i=0;i<G.vexnum;++i) //从0号顶点开始遍历
  if(!visited[ i])//对每个连通分量调用一次BFS
    BFS(G,i);//v，未访问过，从Vi开始 BFS
}
//从顶点v出发，广度优先遍历图G
void BFS(Graph G,int v){
visit(v); //访问初始顶点v
visited[v]=TRUE; //对v做已访问标记
Enqueue (Q,v);//顶点v入队列O
while(!isEmpty(Q)){
  DeQueue (o,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(O,w);//顶点w入队列
    }//if
}//while

下面通过实例演示广度优先搜索的过程,给定图G如图6.11所示。

假设从a结点开始访问，a先入队。此时队列非空，取出队头元素a,由于b,c与a邻接且未被访问过，于是依次访问b,c，并将b, c依次入队。队列非空，取出队头元素b，依次访问与b邻接且未被访问的顶点d, e，并将d, e入队（注意: a与b也邻接，但a已置访问标记，故不再重复访问)。此时队列非空，取出队头元素c，访问与c邻接且未被访问的顶点f,g，并将f, g入队。此时，取出队头元素d，但与d邻接且未被访问的顶点为空，故不进行任何操作。继续取出队头元素e，将h入队列$\cdots$最终取出队头元素h后，队列为空，从而循环自动跳出。遍历结果为abcdefgh。
从上例不难看出，图的广度优先搜索的过程与二叉树的层序遍历是完全一致的，这也说明了图的广度优先搜索遍历算法是二叉树的层次遍历算法的扩展。

BFS 算法的性能分析

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

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

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

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

void BFS MIN Distance (Graph G, int u){//d[i]表示从u到i结点的最短路径
for(i-0;i<G.vexnum;++i)
  d[i]=-1;//初始化路径长度
visited[u]-TRUE;d[u]-0;
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的尚未访问的邻接顶点
      visited[w]=TRUE;//设已访问标记
      d[w]=d[u]+1;//路径长度加1
      EnQueue(o, w); //顶点w入队
    }//if
  }//while
}

广度优先生成树

在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树，如图6.12所示。需要注意的是，一给定图的邻接矩阵存储表示是唯一的，故其$\color{green}{\text{广度优先生成树}}$也是$\color{green}{\text{唯一}}$的，但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。

广度优先也会生成森林：参考文献

深度优先搜索

与广度优先搜索不同，深度优先搜索（Depth-First-Search，DFS）类似于树的$\color{red}{\text{先序遍历}}$。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。

它的基本思想如下:首先访问图中某一起始顶点$v$，然后由$v$出发，访问与$v$邻接且未被访问的任一顶点$w_1$，再访问与$w_1$,邻接且未被访问的任一顶点$w_2\cdots$重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

一般情况下，其递归形式的算法十分简洁，算法过程如下:

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

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为v的尚未访问的邻接顶点
    DFS(G,w);
  } //if
}

以图6.11的无向图为例，深度优先搜索的过程:首先访问a，并置a访问标记;然后访问与a邻接且未被访问的顶点b，置b访问标记;然后访问与b邻按且不ovP的-控日d油v记。此时d已没有未被访问过的邻接点，故返回上一个切问过的明点 b，vP马只*孜工个B以问的顶点e，置e访问标记$\cdots$以此类推，直至图中所有的顶点都被访问一次。遍历结果为abdehcfg。

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

DFS算法的性能分析

DFS 算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为$O(\lvert V \rvert )$。

遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所用的存储结构。以邻接矩阵表示时,查找每个顶点的邻接点所需的时间为$O(\lvert V \rvert )$,故总的时间复杂度为$O(\lvert V \rvert^2 )$。以邻接表表示时，查找所有顶点的邻接点所需的时间为$O(\lvert V \rvert )$，访问顶点所需的时间为$O(\lvert E \rvert )$，此时，总的时间复杂度为$O(\lvert V \rvert +\lvert E \rvert )$。

深度优先的生成树和生成森林

与广度优先搜索一样,深度优先搜索也会产生一棵深度优先生成树。当然，这是有条件的，即对连通图调用DFS才能产生深度优先生成树，否则产生的将是深度优先生成森林，如图6.13所示。与 BFS类似，基于邻接表存储的深度优先生成树是不唯一的。

图的遍历与图的连通性

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

图的应用

最小生成树

最小生成树的代码和应用，更清晰的算法版本，

• 代码思路总结：prim：有一个距离列表信息，每加一个就更新距离列表信息，储存最短的路径
  • memset(dist, 0x3f, sizeof dist);，其中0x3f相当于设为infinity

prim算法

// [来源](https://blog.csdn.net/esjiang/article/details/114481882?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-8.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-8.no_search_link)

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int w[N][N], dist[N];
int n, m;
bool st[N];

int prim(){
  // 将所有的距离都设置为无限大
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int res = 0;
    
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            // t == -1 || 保证t不等于-1
            if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        // 设置为已访问
        st[t] = true;
        // 更新最小生成树的距离的和
        res += dist[t];
        // 更新距离列表信息
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], w[t][j]);
    }
    return res;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];
    
    int t = prim();
    cout << t << endl;
    return 0;
}

Kruskal算法

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 220;
struct Edge{
    int a, b, w;
    bool operator < (const Edge &W) const {
        return w < W.w;
    }
}edge[M];
int n, m;
int p[N];

int find(int x){
    // 路径压缩
    // 《算法笔记.胡凡》 pp.330
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ){
        scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].w);
    }
    
    sort(edge, edge + m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    int res = 0;
    
    for (int i = 0; i < m; i ++ ){
        int a = edge[i].a, b = edge[i].b, c = edge[i].w;
        a = find(a), b = find(b);
        // 下标为a的节点，认下标为b的节点做爸爸
        // 加入到最小生成树中
        // 通过并查集看是不是同一个集合中
        if (a != b) {
          p[a] = b;
          res += c;
        }
    }
    
    cout << res << endl;
    
    return 0;
}

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

证明是生成树：没有回路

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

不难看出，最小生成树具有如下性质:
1）最小生成树不是唯一的，即最小生成树的树形不唯一，$\Re$中可能有多个最小生成树。当图G中的各边权值互不相等时，G的最小生成树是唯一的;若无向连通图G的边数比顶点数少1，即G本身是一棵树时，则G的最小生成树就是它本身。

2）最小生成树的边的权值之和总是唯一的，虽然最小生成树不唯一，但其对应的边的$\color{green}{\text{权值之和}}$总是$\color{green}{\text{唯一}}$的，而且是最小的。

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

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

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

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

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

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

Prim算法

Prim（普里姆）算法的执行非常类似于寻找图的最短路径的$\color{green}{\text{Dijkstra算法}}$。

Prim算法构造最小生成树的过程如图6.15所示。初始时从图中任取一顶点(如顶点1)加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1。以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。此时T中必然有n-1条边。

Prim算法的步骤如下:

假设$G=\lbrace V,E \rbrace$是连通图，其最小生成树$T=(U, E_T)$，$E_T$是最小生成树中边的集合。

初始化:向空树$T=(U,E_T)$中添加图$G=(V, E)$的任一顶点$u_0$，使$U=\lbrace u_0 \rbrace，E_T=\emptyset$。
循环(重复下列操作直至U=V):从图G中选择满足$\lbrace (u, v) \vert u \in U,v \in V-U \rbrace$且具有最小权值的边$(u, v)$，加入树T，置$U=U \cup \lbrace v \rbrace$，$E_T=E_T \cup u \lbrace (u, v) \rbrace$。

Prim算法的时间复杂度为$O(\lvert V \rvert^2 )$，不依赖于$O(\lvert E \rvert )$因此它适用于求解$\color{green}{\text{边稠密的图}}$的最小生成树。

Kruskal算法

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

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

假设$G=(V,E)$是连通图，其最小生成树$T=(U, E_T)$。

初始化:$U=V, E_T=\emptyset$。即每个顶点构成一棵独立的树，$T$此时是一个仅含$\lvert V \rvert$个顶点的森林。循环（重复下列操作直至T是一棵树):按G的边的权值递增顺序依次从$E-E_T$中选择一条边，若这条边加入T后$\color{green}{\text{不构成回路}}$，则将其加入$E_T$,否则舍弃，直到$E_T$中含有$n-1$条边。

Kruskal 算法的简单实现如下:

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

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

通常在Kruskal算法中，采用堆（见第7章）来存放边的集合，因此每次选择最小权值的边只需$O(log \lvert E \rvert)$的时间。此外，由于生成树T中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集的数据结构来描述T，从而构造T的时间复杂度为$O(\lvert E \rvert log\lvert E \rvert)$。

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

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

因此，Kruskal算法适合于边稀疏而顶点较多的图。

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

最短路径:DP思想,贪心

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

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

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

使用邻接矩阵表示时，时间复杂度为$O(\lvert V \rvert^2 )$。使用带权的邻接表表示时，虽然修改$\text{dist [ ]}$的时间可以减少，但由于在$\text{dist[ ]}$中选择最小分量的时间不变，时间复杂度仍为$O(\lvert V \rvert )$。

人们可能只希望找到从源点到某个特定顶点的最短路径，但这个问题和求解源点到其他所有顶点的最短路径一样复杂，时间复杂度也为O(\lvert V \rvert^2)。

每个节点有三个节点信息，节点是否被访问，到起点的距离，被访问节点的父亲节点的信息

• update，每加入一个节点，更新所有与该节点$\color{green}{\text{相邻的节点}}$的信息，该$\color{green}{\text{加入节点}}$加边的权值小于$\color{green}{\text{相邻的节点}}$当前距离时，$\color{red}{\text{更新}}$节点距离，将父亲变成$\color{green}{\text{加入节点}}$
• scan：$\color{red}{\text{扫描}}$距离列表信息，找到未选顶点中$\color{green}{\text{距离最短的节点}}$
• add：添加$\color{green}{\text{距离最短的节点}}$到已选节点集合中，

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

代码简洁优雅著称，三个循环即可，$\color{red}{\text{动态规划的思想}}$

$\color{red}{\text{Q：}}$中间点在不断的变化，他怎么能保证一定挂载到最短路径上？某个中间点一开始是无穷，那么第一次循环他必不可能挂载到中间路径上，后面会变成更小的，万一此时有节点经过他最短他好像也挂不上去最短路径上了了？

视频1：天勤

视频2，可视化

参考文献1：知乎

有向无环图描述表达式

有向无环图:若一个有向图中不存在环，则称为有向无环图，$\color{green}{\text{简称DAG图}}$。

有向无环图是描述含有公共子式的表达式的有效工具。例如表达式

((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

可以用上一章描述的二叉树来表示，如图6.20所示。仔细观察该表达式，可发现有一些相同的子表达式(c+d)和(c + d)*e，而在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间，图6.21所示为该表达式的有向无环图表示。

拓扑排序

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

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

${\textstyle\unicode{x2460}}$ 每个顶点出现且只出现一次。

${\textstyle\unicode{x2461}}$ 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

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

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤;

${\textstyle\unicode{x2460}}$ 从AOV网中选择一个没有前驱的顶点并输出。

${\textstyle\unicode{x2461}}$ 从网中删除该顶点和所有以它为起点的有向边。

${\textstyle\unicode{x2462}}$ 重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

图6.22所示为拓扑排序过程的示例。每轮选择一个入度为0的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为{1,2,4,3,5}。

拓扑排序算法的实现如下:

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;//拓扑排序成功
}

由于输出每个顶点的同时还要删除以它为起点的边,故拓扑排序的时间复杂度为O(IV+ |E)此外，利用上一节的$\color{green}{\text{深度优先遍历}}$也可实现拓扑排序，请读者仔细思考其原因及实现方法。

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

${\textstyle\unicode{x2460}}$ 从AOV网中选择一个没有后继（出度为0）的顶点并输出。

${\textstyle\unicode{x2461}}$ 从网中删除该顶点和所有以它为终点的有向边。

${\textstyle\unicode{x2462}}$ 重复①和②直到当前的AOV网为空。

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

${\textstyle\unicode{x2460}}$入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动$\color{green}{\text{开始}}$或$\color{green}{\text{继续}}$。

${\textstyle\unicode{x2461}}$ 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一;但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。

${\textstyle\unicode{x2462}}$ 由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成AOV网的新的邻接存储矩阵，这种$\color{green}{\text{邻接矩阵}}$可以是$\color{green}{\text{三角矩阵}}$;但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列;反之则不一定成立。

拓扑排序大话数据结构中的代码描述

p300

关键路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网。AOE网和AOV网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE网中的边有权值;而AOV网中的边无权值,仅表示顶点之间的前后关系。

AOE网具有以下两个性质:

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

在AOE网中仅有一个入度为0的顶点，称为$\color{green}{\text{开始顶点（源点)}}$，它表示整个工程的开始;网中也仅存在一个出度为0的顶点，称为$\color{green}{\text{结束顶点（汇点)}}$，它表示整个工程的结束。

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

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

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

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

公式中的max:某个事件节点有多个前驱来算最早发生时间，要等其最晚的前驱完成
ve(k),vertex early k

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

$ve$(源点)=0

$ve(k) = Max \lbrace ve(j) + Weight(v_j, v_k) \rbrace$,$v_k$为$v_j$的任意后继，$Weight (v_j, v_k)$表示$$上的权值

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

${\textstyle\unicode{x2460}}$ 初始时，令$ve[1…n]$=0。

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

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

公式中的min：某个事件节点有多个后继用来算最迟发生时间，为了保证最迟发生时间不会发生改变，选由后继算出来的最小的最迟发生时间
vl(k),vertex late k

它是指在不推迟整个工程完成的前提下，即保证它的后继事件$v_j$,在其最迟发生时间$vl(j)$能够发生时，该事件最迟必须发生的时间。可用下面的递推公式来计算:

vl(汇点)= ve(汇点)

$vl(k)= Min\lbrace vl(j) -Weight(v_k, v_j) \rbrace$, $v_k$为$v_j$的任意前驱

$\color{red}{\text{注意:}}$在计算vl(k)时，按从后往前的顺序进行，可以在逆拓扑排序的基础上计算。

计算 $vl()$值时，按从后往前的顺序进行，在上述拓扑排序中，增设一个栈以记录拓扑序列，拓扑排序结束后从栈顶至栈底便为逆拓扑有序序列。过程如下:

${\textstyle\unicode{x2460}}$ 初始时，令$vl[1…n]=ve[n]$。

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

活动$a_i$的最早开始时间e(i)

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

活动$a_i$的最迟开始时间l(i)

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

一个活动$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$是关键活动。

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

1)从源点出发，令ve(源点)=0，按拓扑有序求其余顶点的最早发生时间ve()。

2)从汇点出发，令v(汇点)= ve(汇点)，按逆拓扑有序求其余顶点的最迟发生时间vl()。3）根据各顶点的ve()值求所有弧的最早开始时间e()。

4)根据各顶点的vl(值求所有弧的最迟开始时间l()。

5）求AOE网中所有活动的差额d()，找出所有d()=0的活动构成关键路径。

图6.23所示为求解关键路径的过程,简单说明如下:

1）求ve():初始ve(1)=0，在拓扑排序输出顶点过程中，求得ve(2)= 3，ve(3)= 2，ve(4) =max {ve(2)+ 2, ve(3)+ 4} = max {5,6} =6, ve(5) = 6, ve(6) = max {ve(5)+ 1, ve(4)+2,ve(3)+3}= max {7,8,5} = 8。

如果这是一道选择题，根据上述求ve()的过程就已经能知道关键路径。

2)求v():初始vl(6)=8，在逆拓扑排序出栈过程中，求得vl(5)=7，vl(4)=6，vl(3)= min{vl(4)-4, vl(6)- 3} = min{2,5}=2，vl(2) = min{vl(5)- 3,vl(4)- 2} = min{4,4} =4，vl(1)必然为0而无须再求。

3）弧的最早开始时间e()等于该弧的起点的顶点的ve()，求得结果如下表所示。

4）弧的最迟开始时间 l(i)等于该弧的终点的顶点的vl()减去该弧持续的时间，求得结果如下表所示。

5）根据l(i)- e(i)=0的关键活动，得到的关键路径为$(v_1,v_3, v_4, v_6)$。

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

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

$\color{red}{\text{Q：}}$ ????还不能缩短到一定程度，工程上肯定不能这样解决问题的吧？？？？

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

手工求关键路径的方法

• 按照层次遍历的思想给边标序号，边的序号用字母表示
  • 把事件的最晚发生时间，标记在节点的旁边
• 建立两个二维数组

关键路径大话数据结构中的代码描述

etv(earliest time of vertex):顶点事件最早发生的时间点
ltv(latest time of vertex):顶点事件最晚发生的时间点，最晚需要开始的时间，超过此时间将会延误工期
ete(earliest time of edge):活动最早发生的时间点
lte(latest time of edge):活动最晚发生的时间点，不推迟工期的最晚开工时间

p309