6.1 图的基本概念

• 有向图/无向图：边是否有方向。
• 完全图：无向 n(n−1)/2 条边，有向 n(n−1) 条弧。
• 度/入度/出度：无向图度 = 边数 ×2；有向图入度之和 = 出度之和 = 边数。
• 连通/强连通：无向图任意两点可达为连通；有向图任意两点互相可达为强连通。
• 子图/生成子图：后者顶点集不变。

6.2 图的存储结构

邻接矩阵

用 n×n 矩阵 A 存储，A[i][j]=1 表示有 i→j 的边（无权）或权重（带权图）。无向图矩阵对称。

• 适合稠密图；空间 O(n²)
• 查边 O(1)；查邻接点 O(n)

邻接表

为每个顶点建立单链表，存储其邻接点。

• 适合稀疏图；空间 O(n+e)
• 查邻接点高效；查特定边需遍历链表
• 有向图可用十字链表；无向图可用邻接多重表

图的存储结构动画演示

对比邻接矩阵与邻接表两种存储方式。邻接矩阵用 n*n 数组适合稠密图, 邻接表用链表适合稀疏图。顶点 A-E, 边: A-B, A-C, B-D, B-E, C-D, D-E (无向图)。

6.3 图的遍历

从某顶点出发访问所有顶点且仅一次。

• BFS 广度优先搜索：借助队列，逐层访问。可求无权图最短路径、连通分量。
• DFS 深度优先搜索：借助栈/递归，深入到底再回溯。判断回路、拓扑排序。

6.4 最小生成树 MST

连通无向图的生成树包含全部顶点的极小连通子图。权值之和最小的生成树为最小生成树。

Prim 算法

从任一顶点开始，每次选与当前生成树距离最近的顶点加入。适合稠密图。O(n²)。

Kruskal 算法

将边按权值排序，依次选不构成回路的最小边。适合稀疏图。O(e log e)。

6.5 最短路径

Dijkstra 算法

求单源最短路径（非负权）。维护距离集合，每次选最近顶点扩展，松弛其邻接点。

• 时间复杂度 O(n²)（邻接矩阵）/ O((n+e)log n)（堆优化）
• 不能处理负权边

Floyd 算法

求每对顶点间最短路径。动态规划，d[i][j]=min(d[i][j], d[i][k]+d[k][j])。时间 O(n³)，可处理负权但不能有负回路。

6.6 拓扑排序与关键路径

拓扑排序：选入度为 0 的顶点输出并删除，重复。若输出全部顶点则无环。时间 O(n+e)。

AOE 网 / 关键路径：顶点表示事件，边表示活动与权值（耗时）。关键路径是从源点到汇点的最长路径，决定工程最短工期。

6.6.3 关键路径（AOE 网）

AOE 网：顶点表示事件，有向边表示活动，边权表示活动持续时间。关键路径：从源点到汇点路径长度最长的路径，决定最短工期。

• Ve[i]：事件 i 的最早发生时间（正向拓扑）：Ve[源]=0；Ve[j] = max{Ve[i] + w(i,j)}。
• Vl[i]：事件 i 的最迟发生时间（反向逆拓扑）：Vl[汇]=Ve[汇]；Vl[i] = min{Vl[j] − w(i,j)}。
• e[k]：活动 a_k= 的最早开始：e = Ve[i]。
• l[k]：活动 a_k= 的最迟开始：l = Vl[j] − w。
• 关键活动：e = l（无时间余量）。由所有关键活动组成的路径即关键路径。