数据结构——图

知识框架

图的基本概念 P207

【课件】6.1.1图的基本概念.pdf

常见考点

无向图

对于 n 个顶点的无向图 G

1. 所有顶点的
2. 若 G 是连通图，

1. 则最少有 n-1 条边（树），此时构成一棵树
2. 若 ，则一定有回路

3. 若G是非连通图，则最多可能有 条边
4. 无向完全图共有 条边

有向图

对于 n 个顶点的有向图 G

1. 所有顶点的
2. 所有顶点的
3. 若 G 是强连通图，则最少有 n 条边（形成一条回路）
4. 有向完全图共有 条边

图的定义

:::tips

图 _G _由 顶点集 _V _和 边集_E _组成

• 记为 $ G = (V, E) $ - 其中 $ V(G) $ 表示图 _G _中顶点的有限非空集 - $ E(G) $ 表示图 _G _中顶点之间的关系（边）集合
• 若 $ V = \{v_1, v_2, … , v_n\} $ ，则用 $ |V | $ 表示图 _G _中 顶点的个数，也称 图 _G _的阶
• $ E = {(u, v) | u\in V, v \in V} $ ，用 $ |E| $ 表示图 G 中 边的条数。

:::

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

连通分量和强连通分量

:::tips
王道书：课后题

P210

12、13、14

:::

:::tips
连通分量：无向图中的极大连通子图

:::

:::tips
强连通分量：有向图中的极大强连通子图

:::

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

:::

图的存储及基本操作

【课件】6.2.1邻接矩阵法.pdf

【课件】6.2.2邻接表法.pdf

【课件】6.2.3+6.2.4十字链表、邻接多重表.pdf

【课件】6.2.5图的基本操作.pdf

邻接矩阵法

:::info

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

:::

基本概念和代码

:::info

1. 空间复杂度：$ O(|V|^2) $——**只和顶点数相关**，和实际的边数无关
2. 适合用于**存储稠密图**
3. 无向图的邻接矩阵是**对称矩阵**，可以**压缩存储**（只存储上三角区/下三角区）

:::

#define MaxVertexNum 100 // 顶点数目的最大值

typedef char VertexType; //顶点对应的数据类型
typedef int EdgeType;    // 边对应的数据类型
typedef struct {
    VertexType vex[MaxVertexNum];               // 顶点表
    EdgeType edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵，边表
    int vexnum, arcnum;                          // 图当前的顶点数和边数
} MGraph;

:::tips

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

:::

无向图 第 i 个结点的度 = 第 i 行（或第 i 列）的非零元素个数

有向图

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

---

矩阵值为无穷：表示两点之间无边

回顾：对称矩阵的压缩存储

邻接矩阵法的性质

:::info

设图 _G _的邻接矩阵为 _**A**_（矩阵元素为 0/1），

• 则 Aⁿ 的元素 $ A^n[i][j] $ 等于由顶点 i 到顶点 j 的长度为 n__ 的路径的数目

:::

邻接表法

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 vecnum, arcnum;     // 图的顶点数和弧数
} ALGraph;                  // ALGraph 是以邻接表存储的图类型

十字链表 —- 有向图

:::info

1. 空间复杂度：O(|V|+|E|)
2. 如何找到指定顶点的所有**出边**？——顺着绿色线路找
3. 如何找到指定顶点的所有**入边**？——顺着橙色线路找

注意：十字链表只用于存储**有向图** :::  ## 邻接多重表 --- 无向图 :::info 1. **空间复杂度**：O(|V|+|E|) 2. **删除边、删除节点**等操作很方便 注意：邻接多重表只适 用于存储**无向图** :::  ## 图的基本操作 :::tips 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 _的第一个邻接点， 1. 若有则返回顶点号。 2. 若 _x _没有邻接点或图中不存在 _x _，则返回 -1 8. NextNeighbor(G,x,y)：假设图 _G _中顶点 _y _是顶点 _x _的一个邻接点， 1. 返回除 _y _之外顶点 _x _的下一 个邻接点的顶点号， 2. 若 _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_

:::

图的遍历

【课件】6.3.1图的广度优先遍历.pdf

【课件】6.3.2图的深度优先遍历.pdf

广度优先搜索

代码及分析

⼴度优先遍历（Breadth-First-Search, BFS）要点

1. 找到与⼀个顶点相邻的所有顶点
2. 标记哪些顶点被访问过: bool visited[MAXSIZE]
3. 需要⼀个辅助队列

1. FirstNeighbor(G, x)：求图 G 中顶点 x 的第⼀个邻接点，

• 若有则返回顶点号。
• 若 x 没有邻接点或图中不存在 x，则返回 -1。

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

:::tips 同⼀个图的邻接矩阵表示⽅式唯⼀，因此⼴度优先遍历序列唯⼀ 同⼀个图邻接表表示⽅式不唯⼀，因此⼴度优先遍历序列不唯⼀ :::

void BFS(ALGraph G, int i) {
    queue<int> queue;
    visit(G, i);
    visited[i] = true;
    queue.push(i);
    while(!queue.empty()) {
        int v = queue.front();
        queue.pop();
        for(int p = FirstNeighbor(G, v); p != -1; p = NextNeighbor(G, v, p)) {
            if(!visited[p]) {
                visit(G, p);
                visited[p] = true;
                queue.push(p);
            }
        }
    }
}
void BFSTraverse(ALGraph G) {
    for(int i = 1; i <= G.vecnum; i++) {
        visited[i] = false;
    }
    
    for(int i = 1; i <= G.vecnum; i++) {
        if(!visited[i]) {
            BFS(G, i);
        }
    }
}

 邻接矩阵存储的图： 1. 访问 |V| 个顶点需要O(|V|)的时间 2. 查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点 3. 时间复杂度= $ O(|V|^2) $ 邻接表存储的图： 1. 访问 |V| 个顶点需要O(|V|)的时间 2. 查找各个顶点的邻接点共需要O(|E|)的时间， 3. 时间复杂度= $ O(|V|+|E|) $ ### 广度优先生成树和森林   ## 深度优先搜索  ### 代码及分析

深度优先遍历（Deapth-First-Search, DFS）要点

类似于树的先根遍历

但需要标记哪些顶点被访问过: bool visited[MAXSIZE]

:::tips 同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀ 同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀ :::

void DFS(ALGraph G, int i) {
    visit(G, i);
    visited[i] = true;
    for(int p = FirstNeighbor(G, i); p != -1; p = NextNeighbor(G, i, p)) {
        if(!visited[p]) {
            DFS(G, p);
        }
    }
}

void DFSTraverse(ALGraph G) {
    for(int i = 1; i <= G.vecnum; i++) {
        visited[i] = false;
    }
    for(int i = 1; i < G.vecnum; i++) {
        if(!visited[i]) {
            DFS(G, i);
        }
    }
}

 邻接矩阵存储的图： 1. 访问 |V| 个顶点需要 O(|V|) 的时间 2. 查找每个顶点的邻接点都需要 O(|V|) 的时间，而总共有 |V| 个顶点 3. 时间复杂度= $ O(|V|^2) $ 邻接表存储的图： 1. 访问 |V| 个顶点需要 O(|V|) 的时间 2. 查找各个顶点的邻接点共需要 O(|E|) 的时间， 3. 时间复杂度= $ O(|V|+|E|) $ ### 深度优先生成树 :::tips 同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀，深度优先⽣成树也唯⼀ 同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀，深度优先⽣成树也不唯⼀ ::: ### 图的遍历与图的连通性 对无向图进行 BFS/DFS遍历 + 调用 BFS/DFS函数的次数 = 连通分量数 + 对于连通图，只需调用 1次 BFS/DFS 对有向图进⾏BFS/DFS遍历 + 调⽤BFS/DFS函数的次数要具体问题具体分析 - 若起始顶点到其他各顶点都有路径 - 则只需调⽤1次 BFS/DFS 函数 + 对于强连通图，从任⼀结点出发都只需调⽤1次 BFS/DFS # 图的应用 [【课件】6.4.1最小生成树.pdf](https://www.yuque.com/attachments/yuque/0/2024/pdf/40548704/1710746603420-46914ed0-03da-4e9c-84e2-5136ae0437ab.pdf) [【课件】6.4.2_1最短路径问题_BFS算法.pdf](https://www.yuque.com/attachments/yuque/0/2024/pdf/40548704/1710746760168-f8fe6d55-3919-4cf9-9f7b-28ced19a23a0.pdf) [【课件】6.4.2_2最短路径问题_Dijkstra算法.pdf](https://www.yuque.com/attachments/yuque/0/2024/pdf/40548704/1710746770314-d9bbea61-c085-4350-9448-81183be2167b.pdf) [【课件】6.4.2_3最短路径问题_Floyd算法.pdf](https://www.yuque.com/attachments/yuque/0/2024/pdf/40548704/1710746785935-c0b0d70c-ee6b-4508-926d-50c1f453ca23.pdf) [【课件】6.4.3有向无环图描述表达式.pdf](https://www.yuque.com/attachments/yuque/0/2024/pdf/40548704/1710746798508-0cc1c092-c2cb-49d7-bebc-63fb45a436c9.pdf) [【课件】6.4.4拓扑排序.pdf](https://www.yuque.com/attachments/yuque/0/2024/pdf/40548704/1710746810594-f84c0a24-69e9-4162-8497-1e32141b0920.pdf) [【课件】6.4.5关键路径.pdf](https://www.yuque.com/attachments/yuque/0/2024/pdf/40548704/1710746828508-b6527e96-24a5-44ff-bc5d-9d2237e46cd6.pdf) ## 最小生成树  ### 基本概念

🍓生成树的概念

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

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

🥝最小生成树（MST）

对于⼀个带权连通无向图 G = (V, E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。

• 设 R 为 G 的所有生成树的集合，若 T 为 R 中边的权值之和最小的生成树，
• 则 T 称为 G 的最小生成树（Minimum-Spanning-Tree, MST）。

 🍅最小生成树的性质 :::tips 1. **最小生成树**可能有多个，但边的权值之和总是唯一且最小的 2. $ 最小生成树的边数 = 顶点数-1 $ 。 1. 砍掉一条则不连通，增加一条边则会出现回路 3. 如果一个连通图本身就是一棵树，则其最小生成树就是它本身 4. 只有连通图才有生成树，非连通图只有生成森林 ::: ### Prime 算法（加边加点法）

🍏Prim 算法（普里姆）

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

:::info **时间复杂度：**$ O(|V|^2) $ + 适合边稠密图 :::

🍎实现思想

从 V₀ 开始，总共需要 n-1 轮处理

1. 每一轮处理：循环遍历所有个结点，找到 lowCost 最低的，且还没加入树的顶点。
2. 再次循环遍历，更新还没加入的各个顶点的 lowCost 值

 ### Kruskal 算法（加边法）

🍊Kruskal 算法（克鲁斯卡尔）

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

通常用堆来存放边的集合（小根堆）

• 每次取堆顶元素，并重新构造小根堆（）
• 判断边的两个顶点是否是同一集合，使用并查集判断（可视为常数级）

最坏情况需要遍历完所有边

• 因此总的时间复杂度如下

:::info 🍇**时间复杂度：**$ O(|E|*log|E|) $ + 适合边稀疏图 :::  ## 最短路径  ### BFS 求单源最短路径 :::tips BFS 算法求单源最短路径只适⽤于**无权图**，或**所有边的权值都相同的图** ::: 

int d[MaxVertexNum]; 	 //记录路径长度
int path[MaxVertexNum];  // 记录最短路径从哪个顶点过来
void BFS_Min_Distance(ALGraph G, int u) {
    queue<int> queue;
    for(int i = 1; i <= MaxVertexNum; i++) {
        d[i] = 0x3f3f3f3f;
        path[i] = -1;
        visited[i] = false;
    }
    d[u] = 0;
    visited[u] = true;
    queue.push(u);
    while(!queue.empty()) {
        u = queue.front();
        queue.pop();
        for(int p = FirstNeighbor(G, u); p >= 0; p = NextNeighbor(G, u, p)) {
            if(!visited[p]) {		// p为u的尚未访问的邻接顶点
                visited[p] = true;
                queue.push(p);
                d[p] = d[u] + 1;	// 路径长度加 1
                path[p] = u;		// 最短路径应从u到w
            } // if
        } // while
    }
}
// 打印输出从x到y的最短路径
void PrintXToY(int x, int y) {
    printf("%d-->%d最短长度为:%d\n", x, y, d[y]);
    int arr[MaxVertexNum];
    int count = 0;
    for(int i = y; i >= 0; i = path[i]) {
        arr[count++] = i;
    } 
    for(int i = count - 1; i >= 0; i--) {
        printf("%d, ", arr[i]);
    }
    puts("");
}

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

Dijkstra 算法步骤

初始化：

• 若从 V0 开始，令 final[0] = true; dist[0] = 1; path[0] = -1
• 其余顶点 final[k] = false; dist[k] = arcs[0][k]; path[k] = (arcs[0][k] == ∞) ? -1 : 0

n-1 轮处理：

1. 循环遍历所有顶点，

1. 找到还没确定最短路径
2. 且 dist 最小的顶点 Vi，令 final[i] = true

2. 并检查所有邻接自 Vi 的顶点

1. 对于邻接自 Vi 的顶点 Vj，若 final[j] = false 且 dist[i] + arc[i][j] < dist[j]
2. 则令 dist[j] = dist[i] + arc[i][j] path[j] = i

3. 其中 arcs[i][j] 表示 Vi 到 Vj 的弧的权值

:::info 时间复杂度：$ O(n^2) $即 $ O(|V|^2) $ 结论：Dijkstra 算法不适用于有负权值的带权图 注：也可用 Dijkstra 算法求所有顶点间的最短路径，重复 |V| 次即可，总的时间复杂度也是 $ O(|V|^3) $ :::

bool final[MaxVertexNum];   // 标记各顶点是否已找到最短路径
int dist[MaxVertexNum];     // 最短路径长度
int path[MaxVertexNum];     // 路径上的前驱
void Dijkstra(ALGraph G, int u) {
    for(int i = 1; i <= G.vecnum; i++) {
        final[i] = false;
        dist[i] = 0x3f3f3f3f;
        path[i] = -1;
    }
    final[u] = true;
    dist[u] = 0;
    dist[0] = 0x3f3f3f3f;
    for(ArcNode *p = FirstNeighbor(G, u); p; p = NextNeighbor(G, u, p->adjvex)) {   // 初始化
        dist[p->adjvex] = p->weight;
        path[p->adjvex] =  u;
    }
    int count = 0;
    while(++count < G.vecnum) { // 循环 n-1 次
        int minV = 0;   // 记录本轮dist中最小的值的下标对应的结点下标
        for(int i = 1; i <= G.vecnum; i++) {
            if(!final[i] && dist[minV] > dist[i]) {
                minV = i;
            }
        }
        final[minV] = true;
        // 遍历所有邻接自minV的顶点
        for(ArcNode *p = FirstNeighbor(G, minV); p; p = NextNeighbor(G, minV, p->adjvex)) { 
            if(!final[p->adjvex]) {
                if(dist[p->adjvex] > dist[minV] + p->weight) {  // 加入minV结点后，更新dist和path数组
                    dist[p->adjvex] = dist[minV] + p->weight;   
                    path[p->adjvex] = minV;
                }
            }
        }
    }
}

void PrintXToY(int path[], int dist[], int x, int y) {
    printf("%d-->%d最短长度为:%d\n", x, y, dist[y]);
    int arr[MaxVertexNum];
    int count = 0;
    for(int i = y; i >= 0; i = path[i]) {
        arr[count++] = i;
    } 
    for(int i = count - 1; i >= 0; i--) {
        printf("%d, ", arr[i]);
    }
    puts("");
}

### Floyd 算法求各顶点之间的最短路径问题 :::info **Floyd 算法** + 可以解决带负权值的图 + 但不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径 :::

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

使用动态规划思想，将问题的求解分为多个阶段

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

1. 初始：不允许在其他顶点中转，最短路径是?
2. 若允许在V₀中转，最短路径是?
3. 若允许在Vo、V₁中转，最短路径是?
4. 若允许在Vo、V₁、V₂中转，最短路径是?
5. ……
6. n-1: 若允许在Vo、V₁、V₂……Vn-1中转，最短路径是?

int A[MaxVertexNum][MaxVertexNum];
int path[MaxVertexNum][MaxVertexNum];
void Floyd(MGraph G) {
    for(int i = 1; i <= G.vexnum; i++) {
        for(int j = 1; j <= G.vexnum; j++) { // 初始化A和path矩阵
            path[i][j] = -1;
            A[i][j] = G.edge[i][j];
        }
    }
    for(int k = 1; k <= G.vexnum; k++) { 			// 考虑以 Vk 作为中转点
        for(int i = 1; i <= G.vexnum; i++) {		// 遍历整个矩阵，i为行号，j为列号
            for(int j = 1; j <= G.vexnum; j++) {
                if(A[i][k] + A[k][j] < A[i][j]) {	// 以 Vk 为中转点的路径更短
                    A[i][j] = A[i][k] + A[k][j];	// 更新最短路径长度
                    path[i][j] = k;					// 中转点
                }
            }
        }
    }
}

  ## 有向无环图描述表达式

有向无环图（DAG）：

若一个有向图中不存在环，则称为有向无环图，简称DAG图(Directed Acyclic Graph)

解题方法

1. Step 1: 把各个操作数不重复地排成一排
2. Step 2: 标出各个运算符的生效顺序(先后顺序有点出入无所谓)
3. Step 3: 按顺序加入运算符，注意“分层”
4. Step 4: 从底向上逐层检查同层的运算符是否可以合体

:::info 注：标出不同的运算符生效顺序，会得到不同的 DAG 图 :::  ## 拓扑排序  :::info ::: ### AOV 网

AOV网 (Activity On Vertex Network,用顶点表示活动的网)

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

 ### 拓扑排序

拓扑排序：

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

1. 每个顶点出现且只出现一次。
2. 若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径

或定义为：

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

---

实现思路

1. 从AOV网中选择⼀个没有前驱的顶点并输出。
2. 从网中删除该顶点和所有以它为起点的有向边。
3. 重复 ① 和 ② 直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止。

说明有回路

:::info 时间复杂度：$ O(|V|+|E|) $ + 每个顶点需要处理一次 + 每条边需要处理一次 若采用邻接矩阵，则需 $ O(|V|^2) $ :::

int print[MaxVertexNum];
bool TopoLogicSort(ALGraph G) {
    int indegree[MaxVertexNum];
    stack<int> stack;
    for(int i = 1; i <= G.vexnum; i++) {
        indegree[i] = 0;
    }
	// 初始化indegree
    for(int i = 1; i <= G.vexnum; i++) {    
        for(int p = FirstNeighbor(G, i); p > 0; p = NextNeighbor(G, i, p)) {
            indegree[p]++;
        }
    }
	// 初始化stack，压入所有入度为0的结点
    for(int i = 1; i <= G.vexnum; i++) {    
        if(indegree[i] == 0) {
            stack.push(i);
        }
    }
	
    int count = 1;
    while(!stack.empty()) {
        // 栈顶元素出栈，并访问它
        int u = stack.top();
        stack.pop();
        visit(G, u);
        print[count++] = u;     // 记录结点拓扑序列
        // 遍历u的邻接表，让每个边表结点的下标对应的入度数组减 1
        for(int p = FirstNeighbor(G, u); p > 0 && indegree[p] != 0; p = NextNeighbor(G, u, p)) {
            indegree[p]--;
            if(indegree[p] == 0) {
                stack.push(p);  // 结点入度为0，入栈
            }
        }
    }
    if(count <= G.vexnum) {
        return false;       // 有回路
    } else 
        return true;
}

 ### 逆拓扑排序（DFS）

逆拓扑排序

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

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

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

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

:::info 对于逆拓扑排序，可以模仿拓扑排序 + 只是把入度判断变为出度判断 + 可使用邻接矩阵 + 或者使用逆邻接表 :::

bool visited[MaxVertexNum];
void DFS(ALGraph G, int u) {
    visited[u] = true;
    for(int p = FirstNeighbor(G, u); p > 0; p = NextNeighbor(G, u, p)) {
        if(!visited[p]) {
            DFS(G, p);
        }
    }
    printf("%d, ", u);
}
void DFSRTopoLogicSort(ALGraph G) {
    for(int i = 1; i <= G.vexnum; i++) {
        visited[i] = false;
    }
    for(int i = 1; i <= G.vexnum; i++) {
        if(!visited[i]) {
            DFS(G, i);
        }
    }
}

## 关键路径   ### AOE 网

AOE 网(Activity On Edge NetWork)

在带权有向图中，

• 以顶点表示事件，
• 以有向边表示活动，
• 以边上的权值表示完成该活动的开销(如完成活动所需的时间),
• 称之为用边表示活动的网络，简称 AOE 网(Activity On Edge NetWork)

:::info 🍎_AOE_ 网具有以下两个性质： 1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始； 2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。 3. 另外，有些活动是可以并行进行的 ::: :::color1 🍏开始顶点（源点） + 在AOE 网中仅有⼀个入度为 0 的顶点，称为开始顶点（源点）， + 它表示整个工程的开始； 🍑结束顶点（汇点） + 也仅有⼀个出度为0的顶点，称为结束顶点（汇点）， + 它表示整个工程的结束了。  ::: --- ### 关键路径和关键活动 :::danger 🍅关键路径 + 从源点到汇点的有向路径可能有多条， + 所有路径中，具有最大路径长度的路径称为关键路径， 🥝关键活动 + 而把关键路径上的活动称为关键活动  1. 完成整个工程的最短时间就是关键路径的长度， 2. 若关键活动不能按时完成，则整个工程的完成时间就会延长 :::

缩短工期的相关分析

1. 若关键活动耗时增加，则整个工程的工期将增长缩短关键活动的时间，
2. 可以缩短整个工程的工期

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

3. 可能有多条关键路径，

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

:::info
🍊事件 _**<font style="color:rgb(255,147,0);">vk</font>**_ 的最早发⽣时间 _**<font style="color:rgb(255,147,0);">ve</font>**_**<font style="color:rgb(255,147,0);">(</font>**_**<font style="color:rgb(255,147,0);">k</font>**_**<font style="color:rgb(255,147,0);">)</font>**——决定了所有从_**<font style="color:rgb(0,0,0);">vk</font>**_开始的活动能够开工的最早时间

🍅活动 _**<font style="color:rgb(190,0,0);">ai </font>**_的最早开始时间 _**<font style="color:rgb(190,0,0);">e</font>**_**<font style="color:rgb(190,0,0);">(</font>**_**<font style="color:rgb(190,0,0);">i</font>**_**<font style="color:rgb(190,0,0);">)</font>**——指该活动弧的起点所表示的事件的最早发生时间

:::

:::color1
🍇事件_**<font style="color:rgb(112,47,159);">vk</font>**_的最迟发生时间_**<font style="color:rgb(112,47,159);">vl</font>**_**<font style="color:rgb(112,47,159);">(</font>**_**<font style="color:rgb(112,47,159);">k</font>**_**<font style="color:rgb(112,47,159);">)</font>**——它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。

🍏活动_**<font style="color:rgb(1,113,0);">ai</font>**_的最迟开始时间_**<font style="color:rgb(1,113,0);">l</font>**_**<font style="color:rgb(1,113,0);">(</font>**_**<font style="color:rgb(1,113,0);">i</font>**_**<font style="color:rgb(1,113,0);">)</font>**——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。

:::

:::color3
🍎活动_**<font style="color:rgb(190,0,0);">ai</font>**_的最早开始时间_**<font style="color:rgb(190,0,0);">e</font>**_**<font style="color:rgb(190,0,0);">(</font>**_**<font style="color:rgb(190,0,0);">i</font>**_**<font style="color:rgb(190,0,0);">)</font>**——指该活动弧的起点所表示的事件的最早发生时间

🍏活动_**<font style="color:rgb(1,113,0);">ai</font>**_的最迟开始时间_**<font style="color:rgb(1,113,0);">l</font>**_**<font style="color:rgb(1,113,0);">(</font>**_**<font style="color:rgb(1,113,0);">i</font>**_**<font style="color:rgb(1,113,0);">)</font>**——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。

🌰活动_**<font style="color:rgb(0,0,0);">ai</font>**_的时间余量_**<font style="color:rgb(190,0,0);">d</font>**_**<font style="color:rgb(190,0,0);">(</font>**_**<font style="color:rgb(190,0,0);">i</font>**_**<font style="color:rgb(190,0,0);">)=</font>**_**<font style="color:rgb(190,0,0);">l</font>**_**<font style="color:rgb(190,0,0);">(</font>**_**<font style="color:rgb(190,0,0);">i</font>**_**<font style="color:rgb(190,0,0);">)-</font>**_**<font style="color:rgb(190,0,0);">e</font>**_**<font style="color:rgb(190,0,0);">(</font>**_**<font style="color:rgb(190,0,0);">i</font>**_**<font style="color:rgb(190,0,0);">)</font>**，

• 表示在不增加完成整个工程所需总时间的情况下，活动`_ai_`可以拖延的时间
• 若⼀个活动的时间余量为零，则说明该活动必须要如期完成，
• _<font style="color:rgb(0,0,0);">d</font>_<font style="color:rgb(0,0,0);">(</font>_<font style="color:rgb(0,0,0);">i</font>_<font style="color:rgb(0,0,0);">)=0</font>即_<font style="color:rgb(0,0,0);">l</font>_<font style="color:rgb(0,0,0);">(</font>_<font style="color:rgb(0,0,0);">i</font>_<font style="color:rgb(0,0,0);">) = </font>_<font style="color:rgb(0,0,0);">e</font>_<font style="color:rgb(0,0,0);">(</font>_<font style="color:rgb(0,0,0);">i</font>_<font style="color:rgb(0,0,0);">)</font>的活动_<font style="color:rgb(0,0,0);">ai</font>_是关键活动
• 由关键活动组成的路径就是关键路径

:::

求关键路径的步骤

:::tips

1. 求所有事件的最早发生时间 <font style="color:rgb(0,0,0);">ve() </font>
2. 求所有事件的最迟发生时间 <font style="color:rgb(0,0,0);">vl() </font>
3. 求所有活动的最早发生时间 <font style="color:rgb(0,0,0);">e() </font>
4. 求所有活动的最迟发生时间 <font style="color:rgb(0,0,0);">l() </font>
5. 求所有活动的时间余量<font style="color:rgb(0,0,0);">d()</font>
   1. d(i)=0的活动就是关键活动,
   2. 由关键活动可得关键路径

:::

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

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

• ve(源点) = 0
• , vj为vk 的任意前驱

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

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

• vl(汇点) = ve(汇点)
• , vj为vk的任意后继

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

若边<vk, vj>表示活动ai，

• 则有e(i) = ve(k)

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

若边<vk, vj>表⽰活动ai，

• 则有

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

•