本文系统讲解图（Graph）数据结构的基础知识，包括顶点与边的定义、度与连通性等术语。详细对比了邻接矩阵、邻接表、十字链表及邻接多重表四种存储结构的优缺点与实现代码。重点阐述了深度优先搜索（DFS）和广度优先搜索（BFS）的遍历原理及应用。此外，还涵盖了最小生成树（Prim、Kruskal）、单源及多源最短路径（Dijkstra、Floyd）、拓扑排序（AOV）及关键路径（AOE）等核心算法，适用于计算机专业考研复习及算法学习。
图（Graph） 是由 顶点（Vertex）集合 V 和 组成的一种非线性数据结构。
| 术语 | 说明 |
|---|---|
| 度 | 顶点的边数；有向图中分为入度和出度 |
| 路径 | 从一个顶点到另一个顶点的顶点序列 |
| 连通图 | 任意两点间都有路径（无向图） |
| 强连通图 | 任意两点间都有双向路径（有向图） |
考点：判断图的类型、计算度数、找路径长度
matrix[i][j] = 1 表示存在边，否则为 0（或无穷大表示无边）
#define MaxVertexNum 100 // 顶点数目的最大值
typedef char VertexType; // 顶点对应的数据类型
typedef int EdgeType; // 边对应的数据类型
typedef struct {
VertexType vex[MaxVertexNum]; // 顶点表
EdgeType edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵，边表
int vexnum, arcnum; // 图当前的顶点数和边数
} MGraph;
考点：画邻接矩阵、判断是否连通
typedef char VertexType; // 顶点对应的数据类型
#define MaxVertexNum 100 // 顶点数目的最大值
typedef struct ArcNode { // 边表结点
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;
typedef struct VNode {
VertexType data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该结点的弧的结点
} VNode, AdjList[MaxVertexNum];
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的顶点数和弧数
} ALGraph; // ALGraph 是以邻接表存储的图类型
考点：画邻接表、理解头结点与边结点
弧结点用于表示一条有向边（弧），每个弧对应一个 headvex 和 tailvex 的关系。
| 域名 | 含义 |
|---|---|
| tailvex | 表示该弧的尾顶点编号（即起点），指向这条边从哪个顶点出发。 |
| headvex | 表示该弧的头顶点编号（即终点），指向这条边指向哪个顶点。 |
| hlink | 指向以同一头顶点（即 headvex 相同）的下一个弧结点，构成'逆邻接表'：所有指向某个顶点的边连在一起。 |
| tlink | 指向以同一尾顶点（即 tailvex 相同）的下一个弧结点，构成'邻接表'：所有从某个顶点发出的边连在一起。 |
| (info) | 可选字段，用于存储边的附加信息，如权重、长度等，在无权图中可省略。 |
总结：
tlink实现了出边链表（从某顶点出发的所有边），hlink实现了入边链表（指向某顶点的所有边）。这种双重链接结构使得可以快速访问某顶点的出边和入边。
顶点结点用于表示图中的每一个顶点。
| 域名 | 含义 |
|---|---|
| data | 存储该顶点的数据信息，如顶点名称、值等，例如：城市名、任务名等。 |
| firstin | 指向以该顶点为头顶点的第一个弧结点（即指向它的第一条边），即该顶点的入边链表头指针。 |
| firstout | 指向以该顶点为尾顶点的第一个弧结点（即从它发出的第一条边），即该顶点的出边链表头指针。 |
总结：
firstout→ 从该顶点出发的所有边（出度），firstin→ 指向该顶点的所有边（入度）。
注：主要用途是支持有向图的边操作，近年未考。
| 域名 | 含义 |
|---|---|
| ivex | 该边连接的第一个顶点的编号 |
| jvex | 该边连接的第二个顶点的编号 |
| ilink | 指向另一个与 ivex 相连的边（即从 ivex 出发的下一条边） |
| jlink | 指向另一个与 jvex 相连的边（即从 jvex 出发的下一条边） |
| (info) | 可选字段，存储边的附加信息（如权重） |
关键理解：一条边
(u, v)被存为一个结点，它通过ilink接入 u 的边链表，同时通过jlink接入 v 的边链表。因此，删除一条边只需修改两个指针，而不用像邻接表那样删两次。
| 域名 | 含义 |
|---|---|
| data | 存储顶点的数据（如名称、编号） |
| firstedge | 指向第一条与该顶点相连的边（即该顶点的边链表头指针） |
举例：顶点 A
firstedge指向任意一条包含 A 的边（如 A—B）。通过该边的ilink或jlink（取决于 A 是 ivex 还是 jvex），可继续找到 A 的其他邻边。
注：仅适用于无向图，考研较少考。
考研重点：邻接矩阵 vs 邻接表 的优缺点对比（必考选择题）
图的遍历是后续算法的基础，必须掌握！
考点：手写 DFS 序列、判断是否连通
考点：手写 BFS 序列、求最短路径（无权图）
| 项目 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈 / 递归 | 队列 |
| 是否保证最短路径 | 否 | 是（无权图） |
| 时间复杂度 | O(n+e) | O(n+e) |
| 空间复杂度 | O(n) | O(n) |
| 适用场景 | 连通性、环检测 | 最短路径、层次遍历 |
考研重点：会手写 DFS/BFS 遍历序列（给图后填空）
在连通无向图中，选出 n-1 条边，使所有顶点连通且总权重最小。
| 算法 | 思想 | 时间复杂度 |
|---|---|---|
| Prim 算法 | 从一个顶点开始，逐步加入最近的顶点 | O(n^2) 或 O(elog₂n) |
| Kruskal 算法 | 按边权从小到大选边，避免成环 | O(elog₂e) |
区别：Prim：适合稠密图（顶点多）；Kruskal：适合稀疏图（边少）。
考点：比较两者的区别、手写 Prim/Kruskal 步骤
注意：不适用于负权边！
时间复杂度：O(n^3)，适合小规模图
考点：Dijkstra 与 Floyd 的应用场景对比、手写 Dijkstra 步骤
AOV 网（Activity On Vertex）：顶点表示活动，边表示依赖关系
考点：判断是否有环、手写拓扑序列
AOE 网（Activity On Edge）：边表示活动，顶点表示事件
考点：求关键路径、判断关键活动
| 题型 | 考点 |
|---|---|
| 选择题 | - 图的存储方式对比 - DFS/BFS 的特点 - MST 算法适用场景 |
| 填空题 | - 写出 DFS/BFS 遍历序列 - 求最小生成树边数 |
| 简答题 | - 解释 DFS 与 BFS 的区别 - 说明 Dijkstra 为何不能处理负权边 |
| 算法题 | - 手写 Prim/Kruskal 步骤 - 实现拓扑排序 - 求关键路径 |
图相关算法时间复杂度对比
'图存邻接表，遍历看 DFS/BFS；最小生成树 用 Prim/Kruskal，最短路径 Dijkstra 和 Floyd；拓扑排 AOV，关键路 AOE！'
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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