一、图的基本概念
1. 图的定义
- 图 G = (V, E)，V是顶点集合，E是边（或弧）的集合。
- 无向图：边没有方向，(v, w) 与 (w, v) 相同。
- 有向图：弧有方向，<v, w> 表示从 v 指向 w。
2. 度、入度、出度
- 无向图：顶点v的度是与v相关联的边数。所有顶点度数之和 = 2 × 边数。
- 有向图：
- 入度：以v为终点的弧数。
- 出度：以v为起点的弧数。
- 所有顶点入度之和 = 所有顶点出度之和 = 弧数。
3. 图的逻辑关系
- 图结构中元素之间存在多对多关系（任意两个顶点之间都可能存在边）。
二、图的存储方式
1. 邻接矩阵
- n个顶点的图用 n×n 矩阵表示。
- 有向图中，第 i 行第 j 列为1表示 <vᵢ, vⱼ> 存在。
2. 邻接表
- 每个顶点维护一个链表，存放其邻接点（有向图中存放出边终点）。
- 邻接表的顶点表 + 边表，总存储量与 n+e 相关。
3. 存储方式对遍历序列的影响
- 遍历序列不唯一的因素：
- 开始遍历的顶点不同（起点不同）。
- 存储结构不同（邻接矩阵按序号顺序访问，邻接表按链表顺序）。
- 邻接表中邻接点的顺序不同（链表中结点排列顺序影响访问顺序）。
- 因此导致遍历序列不唯一的因素是以上所有。
三、拓扑排序
1. 基本概念
- 用顶点表示活动，弧表示活动间优先关系的有向无环图，称为AOV网。
- 拓扑序列：满足若存在弧 <vᵢ, vⱼ>，则 vᵢ 在序列中出现在 vⱼ 之前的线性序列。
- 拓扑排序只能用于有向无环图（DAG）。
2. 拓扑排序算法（通用方法）
- 计算每个顶点的入度。
- 选择入度为0的顶点输出，并将其从图中删除（其邻接点入度减1）。
- 重复第2步，直到所有顶点输出或不存在入度为0的顶点（有环）。
算法复杂度：
- 采用邻接表存储：O(n + e)（n为顶点数，e为边数）。
- 采用邻接矩阵：O(n²)。
3. 拓扑序列举例
给定有向图边集：E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}
- 入度为0：V1（输出）
- 删除V1的弧，更新入度：V2(0), V3(0), V4(0) —— 均可输出。
- 此时有多种合法序列，需逐个检查选项。正确序列需满足每条弧的先后关系。
- 选项A：V1,V3,V4,V6,V2,V5,V7 —— V6出现在V2之前，但V6无到V2的路径，合法；但检查弧<V2,V5>，V2在V5前，合法；然而<V3,V6>，V3在V6前合法。最终V7合法。为何A错？因为<V4,V6>要求V4在V6前，满足；但< V3,V5>要求V3在V5前满足。但<V2,V5>满足。可能的错误是：若先输出V6，其邻接点V7入度未清零，必须等V5也输出后V7才能入度为零。在A序列中V7出现在V5后，合法。实际上需要验证：输出V1后，V2,V3,V4入度均为0；A中选了V3,V4,V6后，V5入度仍需V2（未输出），所以V6输出后不能输出V2？实际上V2入度已是0，可以输出。序列A中V6之后是V2，可以。但正确选项D是V1,V3,V2,V6,V4,V5,V7。说明A中V4和V6的顺序有误：V4入度为0，V6入度在V3,V4输出后变为0。A中V4在V6之前，这是对的。那为何D对？需要画图。根据给出的正确答案D，拓扑序列是 V1,V3,V2,V6,V4,V5,V7，可验证：V1输出后入度0的有V2,V3,V4；输出V3后V6入度减为1（依赖V4）；输出V2后V5入度减为1（依赖V3已出？实际上V5依赖V2和V3，都满足后入度0，但V5此时入度已为0？先不管）。总之，正确序列需严格模拟。
通用技巧：逐个检验选项中各弧的先后关系是否满足。
四、最短路径
1. 单源最短路径——Dijkstra算法
- 求从指定源点到其他各顶点的最短路径。
- 限制：弧上权值必须非负，不能为负权。如果存在负权，算法可能失效（不是在实际应用中无意义，而是无法正确处理）。
- 算法复杂度（用邻接矩阵）：O(n²)。
- 若求每对不同顶点之间的最短路径，可对每个顶点运行一次Dijkstra，复杂度 O(n³)。
2. 每对顶点最短路径——Floyd算法
- 基于动态规划，可处理负权边，但不能有负权回路（权和为负的回路），否则最短路径无下界。
- 时间复杂度：O(n³)。
3. 权值相等时的单源最短路径
- 当所有边权值相等时，BFS（广度优先搜索）即可解决单源最短路径问题。
- BFS按层扩展，首次访问即最短路径。
五、AOE网与关键路径
1. 基本概念
- AOE网：用边表示活动的有权有向无环图，顶点表示事件，弧表示活动，权值表示活动持续时间。
- 源点：入度为0的顶点（工程开始）。
- 汇点：出度为0的顶点（工程结束）。
- 关键路径：从源点到汇点的最长路径长度，决定工程总工期。
- 关键活动：关键路径上的活动，若推迟则整个工期推迟。
2. 关键路径的相关概念
- 事件的最早发生时间 ve(i)：从源点到该事件的最长路径长度。
- 事件的最迟发生时间 vl(i)：不推迟工期的前提下，事件最迟发生时间。
- 活动的最早开始时间 e(k)：等于该活动的起点事件 ve(i)。
- 活动的最迟开始时间 l(k)：等于终点事件 vl(j) - 活动持续时间。
- 关键活动：e(k) = l(k) 的活动。
3. 关键路径的性质与易错点
- 求关键路径以拓扑排序为基础（先计算ve，再逆拓扑计算vl）。
- 一个事件的最早开始时间 = 以该事件为尾的弧的活动最早开始时间（因为这些活动必须等事件发生后才能开始）。
- 一个事件的最迟开始时间 ≠ 以该事件为尾的弧的活动最迟开始时间。事件最迟开始时间是以该事件为头的弧的活动最迟结束时间减去相关活动时间推导的。错误说法：事件的最迟开始时间等于以该事件为尾的弧的活动最迟开始时间。
- 关键活动提前完成不一定缩短工期：只有所有关键活动同时提前或关键路径改变时才能提前。某些关键活动提前若仍在关键路径上会提前，但说“任何一个关键活动提前完成，那么整个工程将会提前完成”是错误的，因为提前完成某关键活动，它可能不再是关键路径上的瓶颈，或者存在多条关键路径，其他路径仍限制工期。
- 所有关键活动提前完成，整个工程才会提前完成。
- 关键活动一定位于关键路径上。
六、知识点速记卡
| 知识点 | 要点 |
|---|---|
| 无向图度数与边 | 所有顶点度数之和 = 2×边数 |
| 有向图入度与出度 | 入度总和 = 出度总和 = 弧数 |
| 拓扑排序时间复杂度 | 邻接表 O(n+e)，邻接矩阵 O(n²) |
| Dijkstra算法 | 单源最短路径，权值非负，O(n²) |
| Floyd算法 | 多源最短路径，可负权但无负环，O(n³) |
| 权值相等最短路径 | BFS即可解 |
| 关键路径 | 源点到汇点最长路径，基于拓扑排序 |
| 关键活动提前 | 单个关键活动提前不一定缩短工期；所有关键活动提前才一定提前 |
| 事件最早时间 | 等于以该事件为尾的活动最早开始时间 |
| 事件最迟时间 | 不等于以该事件为尾的活动最迟开始时间（这是错误说法） |
七、常见解题方法
1. 拓扑序列验证法
- 列出所有弧，逐一检查候选序列中每个弧的起点是否在终点之前。
- 可模拟删除入度0顶点过程。
2. 关键路径计算法
- 先拓扑排序求ve，再逆序求vl，计算e和l，找e=l的活动。
3. Dijkstra正确性条件
- 看到“权为负”就排除Dijkstra。
4. Floyd算法可负权
- 但不能有负权回路。