💡 博主前言：本文整理自个人的 408 计算机考研复习笔记。本书写特点是拒绝死记硬背，用最直观的大白话提炼算法的核心直觉。笔记中针对高频考点进行了梳理，并对邻接矩阵幂次原理、Prim 与 Dijkstra 算法的“集合思想”进行了深度扩展与全流程图解。希望能帮到一起备考的伙伴们！
文章目录
-
- 📌 一、 图的基本概念与核心性质
-
- 1. 基础定义与边数关系
- 2. 路径与环
- 3. 子图与连通性
- 💾 二、 图的存储结构与底层原理
-
- 1. 邻接矩阵（Adjacency Matrix）
-
- 🔍 【高频探究】邻接矩阵幂次
A
k
[
i
]
[
j
]
A^k[i][j]
Ak[i][j] 的物理意义与原理
- 🔍 【高频探究】邻接矩阵幂次
- 2. 邻接表（Adjacency List）
- 3. 其他高效存储结构（408常考选填题）
- 🎯 三、 图的遍历算法直觉（大白话总结）
-
- 1. DFS（深度优先搜索）
- 2. BFS（广度优先搜索）
- 🛠️ 四、 图的核心算法：基于“集合思想”的深度对决
-
- 📝 【红字突破】Dijkstra 与 Prim “集合思想”的同台对比例题
-
- 1. 实例场景设定
- 2. 第一步（Prim 与 Dijkstra 决策相同）
- 3. 第二步（分歧产生的命运转折点！）
-
- 🌳 方案 A：Prim 算法（目标：连通全图，怎么省钱怎么来）
- 🛣️ 方案 B：Dijkstra 算法（目标：每个人回老家
V
0
V_0
V0 的车费最便宜）
- 💡 核心总结
📌 一、 图的基本概念与核心性质
1. 基础定义与边数关系
-
弧头与弧尾（有向边）：有向边表示为
⟨
v
1
,
v
2
⟩
\\langle v_1, v_2 \\rangle
⟨v1,v2⟩，有向边的终点叫弧头（Arrowhead），起点叫弧尾（Arrowtail）。
-
示例：对于有向边
v
1
→
v
2
v_1 \\to v_2
v1→v2，
v
2
v_2
v2 是弧头，
v
1
v_1
v1 是弧尾。
-
顶点的度、入度与出度：
-
无向图：顶点的度数之和等于边数的 2 倍，即
∑
D
(
v
)
=
2
e
\\sum D(v) = 2e
∑D(v)=2e。
-
有向图：
-
总入度 = 总出度 = 边数
e
e
e，即
∑
I
D
(
v
)
=
∑
O
D
(
v
)
=
e
\\sum ID(v) = \\sum OD(v) = e
∑ID(v)=∑OD(v)=e。
-
有向图中顶点的度数之和为入度与出度之和，即
∑
D
(
v
)
=
2
×
入度
=
2
×
出度
=
2
e
\\sum D(v) = 2 \\times \\text{入度} = 2 \\times \\text{出度} = 2e
∑D(v)=2×入度=2×出度=2e。
-
完全图的边数上限公式：
-
无向完全图：
n
n
n 个顶点，任意两点间都有一条边
⇒
\\Rightarrow
⇒ 边数
e
=
n
(
n
−
1
)
2
e = \\frac{n(n-1)}{2}
e=2n(n−1)。
-
有向完全图：
n
n
n 个顶点，任意两点间都有方向相反的两条有向边
⇒
\\Rightarrow
⇒ 边数
e
=
n
(
n
−
1
)
e = n(n-1)
e=n(n−1)。
2. 路径与环
- 路径：顶点序列
v
1
,
v
2
,
v
3
…
v_1, v_2, v_3 \\dots
v1,v2,v3… 构成的序列。若序列长度为 2，则包含 2 条边。 - 回路（环）：起点和终点是同一个顶点的路径。
3. 子图与连通性
-
子图：顶点集和边集分别是父图的顶点集和边集的子集的图。(形象记忆：树苗是整棵大树的子图)。
-
连通图（无向图）：图中任意两个顶点之间都是连通的（即存在路径）。
-
极大连通子图（连通分量）：无向图中的非连通图，其极大的连通子部分。若任意添加一个顶点都会导致图变成非连通，则该子图为极大连通子图。
-
极小连通子图（生成树）：包含图中全部
n
n
n 个顶点和
n
−
1
n-1
n−1 条边的极小连通子图。
-
🔥 核心直觉：若少一条边，则图不再连通；若多一条边，则图中必产生环。
-
生成森林：由多个连通分量的生成树组成的非连通图。
-
强连通图（有向图）：有向图中任意两个顶点都存在双向路径（路径中可以包含中转顶点）。
-
强连通分量：有向图中的极大强连通子图。
💾 二、 图的存储结构与底层原理
1. 邻接矩阵（Adjacency Matrix）
-
存储方式：
-
顶点数组：v[n]（Vertex 顶点集）
-
边数组：e[n][n]（Edges 边集，二维数组）
-
特点：适用于稠密图，空间利用率高。
-
对称性：无向图的邻接矩阵都是对称矩阵，满足
A
=
A
T
A = A^T
A=AT，在实际工程中可以采用压缩存储（只存上三角或下三角）来节省空间。
🔍 【高频探究】邻接矩阵幂次
A
k
[
i
]
[
j
]
A^k[i][j]
Ak[i][j] 的物理意义与原理
❓ 思考红字：若邻接矩阵为
A
A
A，那么
e
d
g
e
s
k
[
i
]
[
j
]
edges^k[i][j]
edgesk[i][j] 表示从顶点
i
i
i 到顶点
j
j
j 之间长度为
k
k
k 的路径条数。它的底层数学原理是什么？
原理剖析：我们以
k
=
2
k=2
k=2 时的矩阵乘法公式展开：
A
2
[
i
]
[
j
]
=
∑
m
=
1
n
A
[
i
]
[
m
]
×
A
[
m
]
[
j
]
A^2[i][j] = \\sum_{m=1}^{n} A[i][m] \\times A[m][j]
A2[i][j]=m=1∑nA[i][m]×A[m][j]
-
A
[
i
]
[
m
]
=
1
A[i][m] = 1
A[i][m]=1 表示存在边i
→
m
i \\to m
i→m； -
A
[
m
]
[
j
]
=
1
A[m][j] = 1
A[m][j]=1 表示存在边m
→
j
m \\to j
m→j； - 只有当
A
[
i
]
[
m
]
×
A
[
m
]
[
j
]
=
1
A[i][m] \\times A[m][j] = 1
A[i][m]×A[m][j]=1 时，才说明存在一条通过中转点m
m
m 的路径i
→
m
→
j
i \\to m \\to j
i→m→j，其长度恰好为 2。 - 通过
∑
\\sum
∑ 对所有可能的中转点m
m
m 进行求和，得到的便是从i
i
i 到j
j
j 长度为 2 的路径总条数。以此类推，通过数学归纳法可证明A
k
[
i
]
[
j
]
A^k[i][j]
Ak[i][j] 即为长度为k
k
k 的路径条数。
2. 邻接表（Adjacency List）
-
空间复杂度：
-
有向图：
O
(
n
+
e
)
O(n+e)
O(n+e)
-
无向图：
O
(
n
+
2
e
)
O(n+2e)
O(n+2e) （因为每条无向边在表中被记录了两次）
-
🔥 出度/入度查询方法总结：
-
顶点的出度极其容易获取，就是该顶点挂载的单链表中边结点的个数。
-
顶点的入度则较为麻烦，需要遍历整个邻接表的所有链表才能统计出来。
3. 其他高效存储结构（408常考选填题）
- 十字链表：用于优化有向图，能同时在常数或极短时间内获取出度和入度。
- 邻接多重表：用于优化无向图，方便对边进行标记、删除等操作。
🎯 三、 图的遍历算法直觉（大白话总结）
对于图的深度优先（DFS）与广度优先（BFS）遍历，可以用两句极简的“算法直觉”来概括本质：
1. DFS（深度优先搜索）
- 🔥 方法总结：“只要不成环，一直找邻居
⟶
\\longrightarrow
⟶” - 算法直觉：这是一种“一条路走到黑”的贪心回溯思想。利用了栈（Stack）或递归的特性，只要当前顶点的邻居节点没有被访问过（不成环），就立刻深入访问邻居的邻居，直到撞到南墙再回溯。
2. BFS（广度优先搜索）
- 🔥 方法总结：“逐层遍历 🎯”
- 算法直觉：以初始起点为核心，像水波纹一样一层一层向外扩散。利用了队列（Queue）的特性，先访问当前节点的所有直接邻居（第一层），再依次访问邻居的邻居（第二层）。
🛠️ 四、 图的核心算法：基于“集合思想”的深度对决
在考研中，Prim算法、Kruskal算法与Dijkstra算法是手算模拟和算法理解的重中之重。下面先给出精炼总结，随后展开详细的例题对比。
-
🔥 Prim（普里姆）算法：从初始顶点出发，逐个寻找离“这一集合”（集合初始只有起点）最近的点，且把这一点合并进集合，直到所有点都归并到集合。
-
特质：加点法，时间复杂度与边数无关，适合稠密图。
-
🔥 Kruskal（克鲁斯卡尔）算法：从最短边搭起，每一步连接当下最短的边（不允许成环），直到所有点都被连通。
-
特质：加边法，通常采用并查集判环，适合稀疏图。
-
🔥 Dijkstra（迪杰斯特拉）算法：与 Prim 一样，基于“集合”的思想。
-
特质：单源最短路径算法。
📝 【红字突破】Dijkstra 与 Prim “集合思想”的同台对比例题
虽然 Prim 和 Dijkstra 都在执行“将红点（未加入集合）变为蓝点（已加入集合）”的操作，且都用到了贪心策略，但它们的更新代价（Distance）的逻辑有着本质的区别。
1. 实例场景设定
假设图中有三个顶点：
V
0
V_0
V0（源点/起点）、
V
1
V_1
V1、
V
2
V_2
V2。 各边权重如下：
-
V
0
→
V
1
V_0 \\to V_1
V0→V1 = 2 -
V
0
→
V
2
V_0 \\to V_2
V0→V2 = 10 -
V
1
→
V
2
V_1 \\to V_2
V1→V2 = 3
我们将已选入的顶点划入集合
S
S
S，未选入的划入集合
V
−
S
V-S
V−S。初始状态下，
S
=
{
V
0
}
S = \\{V_0\\}
S={V0}。
2. 第一步（Prim 与 Dijkstra 决策相同）
- 此时未加入集合的点中，离
V
0
V_0
V0 最近的是V
1
V_1
V1（距离为 2）。 - 将
V
1
V_1
V1 收入集合，此时已选集合S
=
{
V
0
,
V
1
}
S = \\{V_0, V_1\\}
S={V0,V1}。
3. 第二步（分歧产生的命运转折点！）
现在我们需要决定如何将最后一个点
V
2
V_2
V2 纳入麾下。这时候两个算法在“计算距离”时展现出了完全不同的脑回路：
🌳 方案 A：Prim 算法（目标：连通全图，怎么省钱怎么来）
-
计算逻辑：
V
2
V_2
V2 距离整个已选集合
S
{
V
0
,
V
1
}
S \\{V_0, V_1\\}
S{V0,V1} 这个整体的最短单条边是谁？
-
看
V
0
→
V
2
V_0 \\to V_2
V0→V2 边权是 10；
-
看
V
1
→
V
2
V_1 \\to V_2
V1→V2 边权是 3。
-
做出决策：通过
V
1
V_1
V1 连过去明显更省边权！所以 Prim 认为
V
2
V_2
V2 当前的候选距离是 3。
-
最终结果：选择边
(
V
1
,
V
2
)
(V_1, V_2)
(V1,V2)，最小生成树（MST）的总权重 =
2
+
3
=
5
2 + 3 = 5
2+3=5。
🛣️ 方案 B：Dijkstra 算法（目标：每个人回老家
V
0
V_0
V0 的车费最便宜）
-
计算逻辑：
V
2
V_2
V2 跨过集合后，回到“源点
V
0
V_0
V0”的总累加路径长度是多少？
-
直达路线
V
0
→
V
2
V_0 \\to V_2
V0→V2：总长 10；
-
中转路线
V
0
→
V
1
→
V
2
V_0 \\to V_1 \\to V_2
V0→V1→V2：总长 =
(
V
0
→
V
1
)
+
(
V
1
→
V
2
)
=
2
+
3
=
5
(V_0 \\to V_1) + (V_1 \\to V_2) = 2 + 3 = 5
(V0→V1)+(V1→V2)=2+3=5。
-
做出决策：走中转路线总里程更短！Dijkstra 执行松弛操作（Relaxation）：
D
[
V
2
]
=
min
(
10
,
2
+
3
)
=
5
D[V_2] = \\min(10, 2+3) = 5
D[V2]=min(10,2+3)=5。Dijkstra 认为
V
2
V_2
V2 的最短路径值是 5。
-
最终结果：求得
V
0
V_0
V0 到
V
2
V_2
V2 的最短路径长度为 5。
💡 核心总结
- Prim 算法：每次向外探摸时，只关心红点到已选集合边界的单条最省边长（局部最优连通）。
- Dijkstra 算法：每次向外探摸时，关心的是红点越过边界后，一路走回源点的总累加里程（全局最优路径）。
通过这种大白话的模型构建，无论是面对 408 考研中的选择题模拟，还是大题的手算，都能做到数感清晰，准确率百分之百！
![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
