系统讲解了图数据结构的基础知识，涵盖图的逻辑结构（顶点、边、分类）、存储结构（邻接矩阵、邻接表、十字链表等）及遍历算法（DFS、BFS）。此外还介绍了图的应用，包括生成树、最小生成树（Prim、Kruskal 算法）、最短路径（Dijkstra、Floyd 算法）以及拓扑排序和关键路径分析。内容包含理论定义、代码实现示例及复杂度分析，适合计算机专业学生及开发者学习参考。
本节，我们来深入学习图这种数据结构。
图的分类
图元素之间的关系
顶点的度
当有向图仅一个顶点的入度为 0，其余顶点的入度均为 1，此时是何形状
我们可以看到，这是一棵树结构的图，我们称这种结构为有向树
路径
子图 有两个图：原图 G=(V,E)，子图 G1=(V1,E1)，若满足：V1⊆V、E1⊆E，则称 G1 是 G 的子图
如下，有一个图结构及其部分子图：
联通子图：只要一个子图内部是连通的（即子图中任意两个顶点之间都存在路径），它就可以被称为原图的一个连通子图
联通分量
无向图的连通分量 对于一个无向图的连通子图，如果它已经包含了所有能相互到达的点和边，无法再加入原图中任何其他顶点而保持连通性，它就是极大连通子图；我们也称其为连通分量
联通分量和强连通分量的定义很相似，注意有向图的强连通性即可
生成树和生成森林
在后面，我们会学到网 (带权重的图结构)，其中一个重要的问题就是构造其的最小生成树，以后再来介绍
无向图的邻接矩阵
A.arcs[i][j] = {
1, 如果 ⟨i,j⟩∈E 或者 (i,j)∈E
0, 否则
}
举例 我们有下面这样的一个图结构：
[0 1 0 1 0]
[1 0 1 0 1]
[0 1 0 1 1]
[1 0 1 0 0]
[0 1 1 0 0]
无向图邻接矩阵的规律
有向图的邻接矩阵
举例 有这样的一个有向图：
[0 1 1 0]
[0 0 0 0]
[0 0 0 1]
[1 0 0 0]
有向图邻接矩阵的规律
网的邻接矩阵 与有向图类似，但是对于矩阵中填入的数据，我们填入的就不是 0 或 1 了，而是边所带有的权值
A.arcs[i][j] = {
Wij, 如果 ⟨i,j⟩∈E 或者 (i,j)∈E
∞, 否则
}
举例 有这样的一个网结构：
我们根据定义能获得它的邻接矩阵：
[∞ 5 7 ∞ ∞]
[∞ 4 ∞ ∞ ∞]
[8 ∞ ∞ ∞ 9]
[∞ ∞ 5 ∞ 6]
[∞ ∞ 5 ∞ ∞]
[3 ∞ ∞ 1 ∞]
#define MaxInt 10000 // 表示极大值，用于网结构中权值的赋值
#define MVNum 100; // 设置最大顶点数
typedef char VerTexType; // 设顶点的数据类型为字符型
typedef int ArcType; // 假设边的权值类型为整形
typedef struct {
VerTexType vexs[MVNum]; // 顶点表
ArcType arcs[MVNum][MVNum]; // 邻接矩阵
int vexnum, arcnum; // 图的当前点数和边数
} AMGraph;
算法思想
代码实现
Status CreateUDN(AMGraph &G){
cin >> G.vexnum >> G.arcnum; // 输入总顶点数和总边数
for(i = 0; i < G.vexnum; ++i){ // 依次出入顶点的信息
cin >> G.vex[i];
}
for(i = 0; i < G.vexnum; ++i){
for(j = 0; j < G.vexnum; ++j){
G.arcs[i][j] = MaxInt; // 初始化矩阵，将边关系的值设置为无限大
}
}
for(k = 0; k < G.arcnum; ++k){
cin >> v1 >> v2 >> w; // 输入一条边所依附的顶点以及其权值
i = LocateVex(G, v1);
j = LocateVex(G, v2); // 确定 v1、v2 在 G 中的位置
G.arcs[i][j] = w; // 将权值重置为 w
G.arcs[j][i] = G.arcs[i][j]; // 无向网两顶点之间的权值相等
}
return OK;
}
LocateVex 是图的顶点查找算法，根据顶点的值来查找顶点的位置，具体实现如下：int LocateVex(AmGraph G, VertexType u){
int i;
for(i = 0; i < G.vexnum; ++i){
if(u == G.vex[i]) return i; // 若顶点值相同，返回位置
}
return -1; // 否则，返回 -1
}
其他图结构的实现
优点
如图，对下面这个邻接矩阵，我们可以得出以下信息：
[0 1 0 1 0]
[1 0 1 0 1]
[0 1 0 1 1]
[1 0 1 0 0]
[0 1 1 0 0]
得到如下的无向图：
缺点
无向图的邻接表
举例 有如下的图结构：
用邻接表来进行存储，如下所示：
无向图邻接表的特点
有向图的邻接表
举例 有如下一个有向图：
我们能得到这样的一个邻接表：
有向图邻接表的特点
逆邻接表 为了解决找入度难的问题，我们设计出了逆邻接表。
对于上图的有向图结构，我们有这样的逆邻接表：
头结点的类型定义
typedef struct VNode{
VerTexType data; // 存储的结点信息
ArcNode* firstarc; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNmu];
表结点的类型定义
typedef struct ArcNode{
int adjvex; // 该边所指向的顶点的位置
struct ArcNode* nextarc; // 指向下一条边的指针
OtherInfo info; // 和边有关的信息
} ArcNode;
图的类型定义
typedef struct{
AdjList vertices; // 邻接表的数组
int vexnum, arcnum; // 图中的顶点数和边数
} ALGraph;
算法思想
代码实现
Status CreateUDG(ALGraph &G){
cin >> G.vexnum >> G.arcnum; // 输入图的顶点数和边数
for(int i = 0; i < G.vexnum; ++i){
cin >> G.vertices[i].data; // 输入个头结点的值
G.vertices[i].firstarc = NULL; // 将头结点的指针域置为空
}
for(int k = 0; k < G.arcnum; ++k){
cin >> v1 >> v2; // 驶入一条边依附的两个顶点
int i = LocateVex(G, v1); // 寻找顶点的位置
int j = LocateVex(G, v2);
p1 = new ArcNode; // 生成一个新的边结点 p1
p1->adjvex = j; // 邻接点的序号为 j
p1->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p1; // 将新结点 p1 插入顶点 vi 的边表头部
p2 = new ArcNode; // 生成一个对称新的边结点 p2
p2->adjvex = i; // 邻接点的序号为 i
p2->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p2; // 将新结点 p2 插入顶点 vj 的边表头部
}
return OK;
}
优点
缺点
链表中包含两种结点类型，顶点结点和弧结点
顶点结点，每个顶点信息包含：
弧结点，每条边同时连接两个顶点，并串入这两个顶点的出链表与入链表，包含：
typedef struct VNode {
char data; // 顶点数据
ArcBox* firstIn; // 指向以该顶点为终点的第一条边（入边）
ArcBox* firstOut; // 指向以该顶点为起点的第一条边（出边）
} VNode;
typedef struct ArcBox {
int tailVex; // 边的起点（尾）
int headVex; // 边的终点（头）
ArcBox* hLink; // 指向终点相同的下一条边（入边链）
ArcBox* tLink; // 指向起点相同的下一条边（出边链）
// 可扩展：边权值、标签等信息
} ArcBox;
举例 有这样的一个有向图：
我们根据十字链表的定义，可以得到如下的存储结构示意图：
可以看到：一个头顶点，顺着两个不同方向的链表，我们能很简单的计算出其出度和入度
邻接多重表的结构和十字链表类似，包含顶点结点和弧结点两种结点类型
顶点结点，每个头结点包括：
弧结点，每条边只创建一个结点，供其两个顶点共享，结构包括：
typedef struct VNode {
char data; // 顶点数据
EdgeNode* firstEdge; // 指向第一条边
} VNode;
typedef struct EdgeNode {
int ivex, jvex; // 边连接的两个顶点
struct EdgeNode* ilink; // 指向与 ivex 相连的下一条边
struct EdgeNode* jlink; // 指向与 jvex 相连的下一条边
int weight; // 可选：边的权值
} EdgeNode;
举例 有这样一个无向图，如下：
我们根据多重链表的定义，构建如下的多重链表：
i 被访问后，改为 1，防止被多次访问本节我们来介绍这两种遍历算法
图的深度优先遍历是一种类似于树的先序遍历的图遍历算法，其核心思想是：从某个顶点出发，尽可能'深'地搜索图中的顶点，直到无法继续，再回溯继续搜索未访问的顶点
算法思路
例：有如下这样一个图结构，求其深度遍历次序
解：根据算法设计，我们得到遍历顺序为： 1 -> 2 -> 4 -> 8 -> 5 -> 3 -> 6 -> 7 或 1 -> 2 -> 5 -> 8 -> 4 -> 3 -> 6 -> 7 或…
算法步骤
我们以顶点 0 为起点，对该图进行深度优先遍历（DFS），核心步骤如下：
举例 例： 有如下的一个无向图和其邻接矩阵：
[0 1 0 1 0]
[1 0 1 0 1]
[0 1 0 1 1]
[1 0 1 0 0]
[0 1 1 0 0]
算法流程：
遍历顺序： 1 -> 2 -> 3 -> 4 -> 5
我们能看到，由于邻接矩阵的唯一性，使用邻接矩阵进行深度遍历的结果也是唯一的
代码实现
void DFS(AMGraph G, int v){
cout << v;
visited[v] = true; // 从第 i 个顶点访问
for(int w = 0; w < G.vexnum; w++){ // 依次检查 v 所在的行
if((G.arcs[v][w] != 0) && (!visited[w])){ // w 是 v 的邻接矩阵，如果 w 未被访问，就对其递归调用 DFS
DFS(G, w);
}
}
}
算法步骤 我们将数组中第一个头结点（顶点结点）作为起点，进行深度遍历：
代码实现
void DFS(ALGraph G, int v) {
// 访问当前顶点，输出顶点信息
cout << G.vertices[v].data;
// 标记当前顶点为已访问
visited[v] = true;
// 获取当前顶点的第一个邻接点
ArcNode *p = G.vertices[v].firstarc;
// 遍历当前顶点的所有邻接点
while (p != NULL) {
// 如果邻接点未被访问，则递归调用 DFS 访问它
if (!visited[p->adjvex]) DFS(G, p->adjvex);
// 访问下一个邻接点
p = p->nextarc;
}
}
图的广度优先遍历是一种类似于树的层次遍历的图遍历算法，其核心思想是： 从某个起始顶点出发，首先访问其所有邻接点，然后再依次访问这些邻接点的邻接点，直到所有顶点都被访问为止
算法思路
例：有如下这样一个图结构，求广度遍历次序
解：根据算法，我们得到遍历顺序为： 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 或 1 -> 3 -> 6 -> 7 -> 2 -> 4-> 5 -> 8 或…
广度优先遍历（BFS）的核心思想是：按层次、一圈一圈地访问图中的顶点 先访问的顶点，其邻接点也应该先被访问，后访问的顶点则推迟处理——这就需要一个先进先出的结构来管理顶点的访问顺序，队列完美满足这个需求
算法步骤 以图的邻接矩阵为基础，从顶点 v 出发执行广度遍历：
举例 例： 有如下的一个无向图和其邻接矩阵：
[0 1 0 1 0]
[1 0 1 0 1]
[0 1 0 1 1]
[1 0 1 0 0]
[0 1 1 0 0]
算法流程：
最终遍历顺序： 1 -> 2 -> 4 -> 3 -> 5
代码实现
void BFS(AMGraph G, int v) {
cout << v; // 访问第 v 个顶点
visited[v] = true;
InitQueue(Q); // 初始化队列
EnQueue(Q, v); // 起始顶点入队
while (!QueueEmpty(Q)) {
DeQueue(Q, u); // 出队一个顶点 u
for (int w = 0; w < G.vexnum; w++) {
if (G.arcs[u][w] != 0 && !visited[w]) { // 若 u 和 w 相邻且 w 未访问
cout << w; // 访问 w
visited[w] = true;
EnQueue(Q, w); // w 入队，后续访问其邻接点
}
}
}
}
算法步骤 从某个起始顶点 v 出发，进行如下操作：
代码实现
void BFS(ALGraph G, int v){
cout << v; // 访问第 v 个顶点
visited[v] = true;
InitQueue(Q); // 初始化队列
EnQueue(Q, v); // 起始顶点入队
while(!QueueEmpty(Q)){
DeQueue(Q, u); // 出队一个顶点 u
// 访问顶点的邻接链表
for(int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)){
if(!visited[w]){ // 访问 w
cout << w;
visited[w] = true;
EnQueue(Q, w); // w 入队，后续访问其邻接点
}
}
}
}
int FirstAdjVex(ALGraph G, int u) {
if (G.vertices[u].firstarc != NULL) return G.vertices[u].firstarc->adjvex; // 返回第一个邻接点编号
else return -1;
}
int NextAdjVex(ALGraph G, int u, int w) {
ArcNode *p = G.vertices[u].firstarc;
while (p != NULL) {
if (p->adjvex == w && p->nextarc != NULL) return p->nextarc->adjvex; // 返回 w 的下一个邻接点编号
p = p->nextarc;
}
return -1;
}
和深度遍历一致：
在图的遍历中，如果图是非连通图（即图中存在多个不连通的子图或称连通分量），单次遍历不能遍历所有顶点；因此，我们需要对每一个未被访问的顶点都启动一次新的遍历
拿这样一个非连通图来举例：
它的邻接矩阵为：
[0 1 1 0 0]
[1 0 1 0 0]
[1 1 0 0 0]
[0 0 0 0 1]
[0 0 0 1 0]
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
DFS(i); // 从该未访问顶点开始一个新的 DFS
}
}
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
BFS(i); // 从该未访问顶点开始一个新的 BFS
}
}
生成树作为图的一个核心概念，广泛应用于网络连接、路径规划和最小代价设计等场景；本节我们学习图的生成树的性质与构造方法
前面我们介绍过图的生成树，即——对于一个无向连通图G=(V,E)，其生成树是包含图中所有顶点的一个极小连通子图
如下所示的图结构：
则它的几个生成树结构为：
下面我们学习图生成树的构造
算法思路
示例 有这样的一个无向图结构：
根据遍历方式的不同，我们能得到不同的最小生成树，如下图：
代码实现 我们以邻接表+DFS 算法为例：
void DFS_GenTree(ALGraph G, int v) {
visited[v] = true;
ArcNode *p = G.vertices[v].firstarc; // 从指定起始顶点开始遍历
while (p != NULL) {
int w = p->adjvex; // w 是 v 的第一个邻接点
if (!visited[w]) { // 输出生成树的边 (v, w)
cout << "(" << G.vertices[v].data << "," << G.vertices[w].data << ")" << endl;
DFS_GenTree(G, w); // 继续向下递归
}
p = p->nextarc; // 移动到下一个顶点
}
}
在图论中，生成树是连接图中所有顶点的无环子图；对于一个带权无向图（即网），可能存在多棵生成树，而其中边权总和最小的生成树称为最小生成树（Minimum Spanning Tree, MST），也叫最小代价树
最小生成树的应用：
构造最小生成树是解决这类实际问题的关键第一步，下面我们来介绍最小生成树的构造
构造最小生成树的算法有很多，但大多数都使用了 MST(Minumum Spanning Tree) 性质——设 N=(V,E) 是一个连通网，U 是顶点集 V 的一个非空子集；若 (u,v) 是一条就有最小权值的边，其中 u∈U,v∈V-U，则必然存在一棵包含边 (u,v) 的最小生成树
MST 性质解释：
下面介绍两个实现了 MST 性质最小生成树的构造算法——Prim 算法和 Kruskal 算法
算法思想
举例 如下图，有一个连通网结构：
构造过程：
| 步骤 | 已访问顶点集合 U | 已选边集合 TE | 候选边（U 与 V-U 之间的边） | 选择的最小边 | 新加入顶点 |
|---|---|---|---|---|---|
| 初始 | {1} | ∅ | (1,2), (1,3), (1,4) | - | - |
| 1 | {1} | ∅ | (1,2), (1,3), (1,4) | (1,3) | 3 |
| 2 | {1, 3} | {(1,3)} | (1,2), (1,4), (3,2), (3,4), (3,5), (3,6) | (3,6) | 6 |
| 3 | {1, 3, 6} | {(1,3), (3,6)} | (1,2), (1,4), (3,2), (3,4), (3,5), (6,4), (6,5) | (6,4) | 4 |
| 4 | {1, 3, 6, 4} | {(1,3), (3,6), (6,4)} | (1,2), (1,4), (3,2), (3,4), (3,5), (6,5) | (3,2) | 2 |
| 5 | {1, 3, 6, 4, 2} | {(1,3), (3,6), (6,4), (3,2)} | (1,2), (1,4), (2,5), (3,4), (3,5), (6,5) | (2,5) | 5 |
| 6 | {1, 3, 6, 4, 2, 5} | {(1,3), (3,6), (6,4), (3,2), (2,5)} | - | - | - |
算法思想
举例 如下图，有一个连通网结构：
构造过程：
| 属性 | Prim 算法 | Kruskal 算法 |
|---|---|---|
| 选择对象 | 每次选择顶点 | 每次选择边 |
| 时间复杂度 | O(n^2)，n 为顶点数 | O(e log e)，e 为边数 |
| 适用图类型 | 稠密图（边较多） | 稀疏图（边较少） |
| 算法思想 | 逐步扩展顶点集合 | 按权值排序边逐步合并连通分量 |
在日常生活中，我们驾车或者出行时，都会有交通路线选择的问题——甲地到乙地有多条路径，选择哪一条路最短？ 于是我们引出了最短路径的概念，通过将路线问题抽象为有向带权图，我们就能借助图算法来系统地解决路径选择难题
常见最短路径问题 我们能把现实路径问题抽象成以下数学模型：
最短路径主要有两类问题：
两点之间最短路径 有如下的网结构：
求从 v1 到 v7 的路径及路径长度：
| 路径 | 路径长度 |
|---|---|
| v1、v2、v5、v7 | 20 |
| v1、v4、v2、v5、v7 | 14 |
| v1、v2、v7 | 23 |
| v1、v4、v2、v7 | 17 |
| v1、v4、v6、v7 | 26 |
| 由上表我们可知： | |
| v1、v4、v2、v5、v7 是最短路径，为 14 |
从某点到其他各点的最短路径 有如下的网结构：
从 v0 点到其他各点的最短路径为：
| v0 到各顶点最短路径 | 路径长度 |
|---|---|
| 到 v1：v0-v1 | 13 |
| 到 v2：v0-v2 | 8 |
| 到 v3：v0-v2-v3 | 13 |
| 到 v4：v0-v2-v3-v4 | 19 |
| 到 v5：v0-v2-v3-v4-v5 | 21 |
| 到 v6：v0-v1-v6 | 20 |
最短路径算法
下面来介绍这两种算法
Dijkstra 算法通过贪心策略逐步扩展最短路径，最终求出从源点 v0 到所有顶点的最短路径
算法思路
举例 有如下的网结构，求从 V0 到其他各顶点的最短路径：
算法步骤如下：
| 终点 | 从 v₀ 到各终点的最短路径及长度 | |||||
|---|---|---|---|---|---|---|
| 执行次数 | i=1 | i=2 | i=3 | i=4 | i=5 | i=6 |
| v₁ | 13 | |||||
| v₂ | 8 | |||||
| v₃ | ∞ | |||||
| v₄ | 30 | |||||
| v₅ | ∞ | |||||
| v₆ | 32 | |||||
| vⱼ | v₂ | |||||
| 最短距离 | 8 | |||||
| 这时，我们看到距离最短的顶点为 V2，我们将 V2 加入 S 集合，将 V2 作为中间结点来更新最短路径 |
| 终点 | 从 v₀ 到各终点的最短路径及长度 | |||||
|---|---|---|---|---|---|---|
| 执行次数 | i=1 | i=2 | i=3 | i=4 | i=5 | i=6 |
| v₁ | 13 | 13 | ||||
| v₂ | 8 | \ | ||||
| v₃ | ∞ | 13 | ||||
| v₄ | 30 | 30 | ||||
| v₅ | ∞ | ∞ | ||||
| v₆ | 32 | 32 | ||||
| vⱼ | v₂ | v₁ | ||||
| 距离 | 8 | 13 | ||||
| 重复上面的操作，将 V3 加入 S 集合，并将 V3 作为中间节点继续更新最短路径 |
| 终点 | 从 v₀ 到各终点的最短路径及长度 | |||||
|---|---|---|---|---|---|---|
| 执行次数 | i=1 | i=2 | i=3 | i=4 | i=5 | i=6 |
| v₁ | 13 | 13 | \ | \ | \ | \ |
| v₂ | 8 | \ | \ | \ | \ | \ |
| v₃ | ∞ | 13 | 13 | \ | \ | \ |
| v₄ | 30 | 30 | 30 | 19 | \ | \ |
| v₅ | ∞ | ∞ | 22 | 22 | 21 | 21 |
| v₆ | 32 | 32 | 20 | 20 | 20 | \ |
| vⱼ | v₂ | v₁ | v₃ | v₄ | v₆ | v₅ |
| 距离 | 8 | 13 | 13 | 19 | 20 | 21 |
算法思路
举例 有如下的图结构，求每个点到其余各点的最短路径：
算法步骤如下：
[A A A]
[B B B]
[C C C]
其值为：
[0 4 11]
[6 0 2]
[3 ∞ 0]
如：
[A A A]
[B B B]
[C A C]
其值为：
[0 4 11]
[6 0 2]
[3 ∞→7 0]
[A A A]
[B B B]
[C A C]
其值为：
[0 4 11→6]
[6 0 2]
[3 7 0]
[A A A]
[B B B]
[C A C]
其值为：
[0 4 6]
[6→5 0 2]
[3 7 0]
[0 4 6]
[5 0 2]
[3 7 0]
有向无环图（DAG）是一种有向图，但其中不存在从某个顶点出发沿有向边能回到自身的路径（即不包含环路） 通俗理解：图中所有边都有方向，且沿着方向走不会形成闭环
有向无环图的特性
由于其特性，我们常常使用它来描述一个工程或者系统的进行过程，一个工程可以分为若干个子工程，只要完成了子工程，就可以导致整个工程的完成
AOV 网 用一个有向图来表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网（Activity On Vertex network）
AOE 网 用一个有向图来表示一个工程的各子工程及其相互制约的关系，其中以弧表示活动，顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称AOE网（Activity On Edge network）
AOV 网被用于拓扑排序，而 AOE 网被用于关键路径，下面来分别介绍两种网络
AOV 网的特点
如何判断 AOV 网中是否有回路呢？ 我们可以使用拓扑序来解决这个问题
拓扑排序的概念 在 AOV 网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若 AOV 网中有弧<i,j>存在，则在这个序列中，i 一定在 j 前面，具有这种性质的线性序列叫做拓扑有序序列，相应的拓扑有序排列算法叫做拓扑排序
拓扑排序思路
有如下的一个有向无环图结构：
算法实现步骤：
需要注意的是：拓扑序列并不是唯一的，取决于网结构和选取顶点的顺序，但是所有的拓扑序列中，一个顶点的前驱一定出现在该顶点之前
拓扑排序的应用 回到之前的问题：如何判断 AOV 网中是否有回路呢？
通过拓扑排序算法，我们可以看到：
所以，对于一个有向图，若其所有顶点都在拓扑有序序列中，则该 AOV 网中必定不存在环，也就是有向无环图
如上图所示，对于这样一个网结构的拓扑有序序列中，必然不会出现 3、5、8 这三个顶点
例如：有如下的活动表：
| 活动 | 耗费时间 | 前置任务 |
|---|---|---|
| A | 30 | 无 |
| B | 60 | A |
| C | 45 | A |
| D | 60 | B |
| E | 69 | B |
| F | 30 | DE |
| G | 15 | C |
我们可以得到如下的 AOE 网：
关键路径的相关概念 对于 AOE 网，我们主要关心两个问题：
由此，我们引出了两个关键概念：
关键路径的描述量 为了确定关键路径，我们需要定义几个描述量：
对于时间余量为零的活动，即 l(i)-e(i)==0 的活动，我们称其为关键路径上的活动，也就是关键活动，由多个关键活动组成的路径，就是关键路径。
怎么找寻关键活动呢？
关键路径的计算
如上图所示：我们设活动 ai 用<j,k>表示，其持续时间记为 wj,k，则有：
{
e(i) = ve(j)
l(i) = vl(k) - wj,k
}
可以看到，关键路径的计算的关键在于计算事件最早发生事件和最迟发生事件 如何求出 ve(j) 和 vl(k)——即某事件最早发生时间和最晚发生时间呢？
某事件最早发生时间
ve(k) = max_{j ∈ pred(k)} [ve(j) + wj,k]
即：某事件 k 的最早发生时间 = 所有前驱事件 j 的最早发生时间 + 活动 <j, k> 的耗时的最大值
某事件最迟发生时间
vl(j) = min_{k ∈ succ(j)} [vl(k) - wj,k]
即：某事件 j 的最迟开始时间 = 所有后继事件 k 的最迟开始时间 - 活动 <j, k> 的耗时的最小值
举例 如下图的 AOE 网结构，求它的：
关键活动
计算步骤：
| 顶点 | ve | vl |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 6 | 6 |
| 3 | 4 | 6 |
| 4 | 5 | 8 |
| 5 | 7 | 7 |
| 6 | 7 | 10 |
| 7 | 16 | 16 |
| 8 | 14 | 14 |
| 9 | 18 | 18 |
| 活动 | e | l | l-e |
|---|---|---|---|
| a1 | 0 | 0 | 0 |
| a2 | 0 | 2 | 2 |
| a3 | 0 | 3 | 3 |
| a4 | 6 | 6 | 0 |
| a5 | 4 | 6 | 2 |
| a6 | 5 | 8 | 3 |
| a7 | 7 | 7 | 0 |
| a8 | 7 | 7 | 0 |
| a9 | 7 | 10 | 3 |
| a10 | 16 | 16 | 0 |
| a11 | 14 | 14 | 0 |
关键路径总结
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online