数据结构核心章节：图的定义、存储与遍历算法

考点：画邻接矩阵、判断是否连通

2. 邻接表法（Adjacency List）

• 每个顶点对应一个链表，存储其所有邻接顶点
• 适合稀疏图

优点：

• 存储空间节省，O(n+e)
• 遍历邻接顶点高效

缺点：

• 判断两个顶点是否直接相连需遍历链表

存储结构：

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 是以邻接表存储的图类型

考点：画邻接表、理解头结点与边结点

3. 十字链表（用于有向图）

• 结合邻接表和逆邻接表，每个边结点有两个指针
• 便于查找某顶点的出边和入边

存储结构

弧结点（Arc Node）

弧结点用于表示一条有向边（弧），每个弧对应一个 headvex 和 tailvex 的关系。

总结：tlink 实现了出边链表（从某顶点出发的所有边），hlink 实现了入边链表（指向某顶点的所有边）。这种双重链接结构使得可以快速访问某顶点的出边和入边。

顶点结点（Vertex Node）

顶点结点用于表示图中的每一个顶点。

总结：firstout → 从该顶点出发的所有边（出度），firstin → 指向该顶点的所有边（入度）。

示例图

注：主要用途是支持有向图的边操作，近年未考。

4. 邻接多重表（用于无向图）

• 一条边用两个边结点表示，共享同一记录
• 便于删除边（如网络拓扑）

存储结构

边结点（Edge Node）

关键理解：一条边 (u, v) 被存为一个结点，它通过 ilink 接入 u 的边链表，同时通过 jlink 接入 v 的边链表。因此，删除一条边只需修改两个指针，而不用像邻接表那样删两次。

顶点结点（Vertex Node）——每个顶点一个

举例：顶点 A firstedge 指向任意一条包含 A 的边（如 A—B）。通过该边的 ilink 或 jlink（取决于 A 是 ivex 还是 jvex），可继续找到 A 的其他邻边。

示例图

注：仅适用于无向图，考研较少考。

存储方式对比表

考研重点：邻接矩阵 vs 邻接表 的优缺点对比（必考选择题）

三、图的遍历（核心考点）

图的遍历是后续算法的基础，必须掌握！

1. 深度优先遍历（DFS）

• 类似树的前序遍历，使用栈或递归实现
• 从某个顶点出发，尽可能深地访问子节点

特点：

• 可用于求解连通分量、拓扑排序、判断环

算法步骤：

1. 标记当前顶点已访问
2. 依次访问其未访问的邻接顶点（递归）
3. 回溯

考点：手写 DFS 序列、判断是否连通

2. 广度优先遍历（BFS）

• 使用队列，逐层扩展
• 从起点开始，先访问距离为 1 的顶点，再访问距离为 2 的……

特点：

• 可用于求最短路径（无权图）、层次遍历

算法步骤：

1. 将起点入队
2. 出队一个顶点，访问其所有未访问邻接顶点并入队
3. 重复直到队空

考点：手写 BFS 序列、求最短路径（无权图）

DFS vs BFS 对比

考研重点：会手写 DFS/BFS 遍历序列（给图后填空）

四、图的相关应用（重中之重！）

1. 最小生成树（MST）

在连通无向图中，选出 n-1 条边，使所有顶点连通且总权重最小。

两种经典算法：

区别：Prim：适合稠密图（顶点多）；Kruskal：适合稀疏图（边少）。

考点：比较两者的区别、手写 Prim/Kruskal 步骤

2. 最短路径

Dijkstra 算法（单源最短路径）

• 从起点出发，每次选择距离最小的未访问顶点
• 适用于非负权图

注意：不适用于负权边！

Floyd 算法（多源最短路径）

• 动态规划思想，枚举中间点
• 求任意两点间最短路径

时间复杂度：O(n^3)，适合小规模图

最短路径算法对比表

考点：Dijkstra 与 Floyd 的应用场景对比、手写 Dijkstra 步骤

3. 拓扑排序（AOV 网）

AOV 网（Activity On Vertex）：顶点表示活动，边表示依赖关系

拓扑排序规则：

1. 找入度为 0 的顶点
2. 删除该顶点及其出边
3. 重复直到无顶点可删

排序过程

应用：

• 课程安排、任务调度

考点：判断是否有环、手写拓扑序列

4. 关键路径（AOE 网）

AOE 网（Activity On Edge）：边表示活动，顶点表示事件

核心概念：

• 关键路径：从起点到终点的最长路径
• 关键活动：在关键路径上的活动
• 最早发生时间（ve）：顶点最早能发生的时刻
• 最迟发生时间（vl）：顶点最晚不能超过的时刻

求解步骤：

1. 求 ve（正向 DP）
2. 求 vl（反向 DP）
3. 求每个活动的最早开始时间（e）和最迟开始时间（l）
4. 若 e == l，则为关键活动

考点：求关键路径、判断关键活动

五、高频考点总结

图相关算法时间复杂度对比

六、一句话口诀（背下来！）

'图存邻接表，遍历看 DFS/BFS；最小生成树 用 Prim/Kruskal，最短路径 Dijkstra 和 Floyd；拓扑排 AOV，关键路 AOE！'