博主前言：本文为 408 计算机考研数据结构科目中**图（Graph）与查找（Searching）**的核心笔记规范化整理。内容完全保留原始笔记的珍贵结论与秒杀方法，并进行标准的 Markdown 排版与多维度的深度补充，直击统考选择题与大题的核心考点。建议收藏作为冲刺阶段的提分宝典！
文章目录
-
- 一、 图论核心概念与三大算法对比
-
- 1.1 核心算法基本属性
- 1.2 核心概念辨析（回路补遗）
- 二、 考研必背：图论高频核心补充结论
- 三、 三大核心查找算法性能深度解析（ASL与Mid取值）
-
- 3.1 顺序查找 (Sequential Search)
- 3.2 折半查找 (Binary Search)
- 3.3 分块查找 (Block Search)
- 四、 折半查找判定树特有性质（选择题秒杀神器）
-
- 4.1 判定树的高度
- 4.2 子树结点数的均衡规律（核心方法总结）
一、 图论核心概念与三大算法对比
1.1 核心算法基本属性
在 408 统考中，图的最短路径与拓扑排序是高频常考题型。以下是对笔记中核心算法的结构化梳理：
| Dijkstra 算法 | 贪心算法 (Greedy) |
思想类似于广度优先遍历 (BFS) | 求解单源最短路径。
可以理解为：计算自
v
i
(
i
=
1
,
2
,
3…
)
v_i (i=1,2,3…)
vi(i=1,2,3…) 在单条路状态下的可达点的最短路径。 |
O
(
n
2
)
O(n^2)
O(n2)
(注：邻接矩阵实现) | | Floyd 算法 | 动态规划 (Dynamic Programming) | 求解任意一对顶点之间的最短路径。 |
O
(
n
3
)
O(n^3)
O(n3) | | 拓扑排序 (Topological Sort) | 依次消除入度为 0 的顶点 | 适用于有向无环图 (DAG)，用于检测依赖关系与回路。 |
O
(
n
+
e
)
O(n+e)
O(n+e)
(邻接表) |
1.2 核心概念辨析（回路补遗）
- 核心结论：回路不是简单路径。
- 规范拓展：在数据结构的标准定义中，简单路径是指路径序列中顶点不重复出现。而回路（环）的起点和终点是同一个顶点，因此必然存在重复顶点，故回路不属于简单路径。
二、 考研必背：图论高频核心补充结论
以下 7 条结论是统考选择题中“说法正确的有几项”这类题型的绝佳秒杀工具，务必熟练背诵：
📌 ① 拓扑排序与图无对应的数量关系
- 深度解析：一个拓扑序列可能对应多种不同的图结构；反之，若图中有特定的拓扑序列数量，也无法唯一确定图的拓扑形态。拓扑序列不唯一。
📌 ② 构造最小生成树时，负权值不对结果产生影响
- 深度解析：无论是 Prim 算法还是 Kruskal 算法，其核心逻辑是比较边权的大小关系。只要图中没有负权回路（无向图通常不考虑单边的负权圈），边权为负数并不影响最小生成树（MST）的生成。
📌 ③ 同一张有向无环图的原拓扑序列与逆拓扑序列数量一定相同
- 深度解析：这是由图的对称性决定的。将有向无环图（DAG）中的所有边全部反向，原图的拓扑序列在反向图中恰好对应其逆拓扑序列，两者的排列组合数量完美一一对应。
📌 ④ 无向图中边的权值各不相同，则其最小生成树唯一
- 深度解析：这是统考常考的充要条件。若无向网的所有边权值均不相等，则该图的最小生成树（MST）是唯一的。
📌 ⑤ Prim 和 Kruskal 算法构造出的最小生成树集合相同，但是具体到某一条树边不一定相同
- 深度解析：当图的最小生成树不唯一时（即存在相同权值的边），两种算法得到的最终 MST 集合是相同的（总权值相同）。但在执行过程中，由于 Prim 属于“点扩展”，Kruskal 属于“边扩展”，其加边的顺序或最终选取的某条特定边可能存在差异。
📌 ⑥ Dijkstra 算法求解含有回路的图的最短路径问题，但权值不能为负边
- 深度解析：Dijkstra 算法完全可以处理含有回路（环）的图。但是，它绝不能处理包含负权边的图（因为贪心策略在负权图下无法保证局部最优即全局最优，会导致已确定的最短路径点被错误更新）。
📌 ⑦ Prim 和 Kruskal 的时间复杂度分别是
O
(
n
2
)
O(n^2)
O(n2) 和
O
(
e
log
2
e
)
O(e \\log_2 e)
O(elog2e)
- 点收敛与边收敛：
- Prim 算法：复杂度与边数无关，适用于稠密图。
- Kruskal 算法：复杂度与边数密切相关，适用于稀疏图。
三、 三大核心查找算法性能深度解析（ASL与Mid取值）
平均查找长度（ASL）是衡量查找算法时间性能的核心指标，公式必须做到闭眼能写：
3.1 顺序查找 (Sequential Search)
- 查找成功时的平均查找长度：
A
S
L
成功
=
n
+
1
2
ASL_{\\text{成功}} = \\frac{n+1}{2}
ASL成功=2n+1
- 查找失败时的平均查找长度：
A
S
L
失败
=
n
ASL_{\\text{失败}} = n
ASL失败=n
3.2 折半查找 (Binary Search)
- Mid 值的定位规则： 根据笔记标注，当处理索引和划分时，Mid 值的取法为：
m
i
d
=
⌈
l
o
w
+
h
i
g
h
2
⌉
（向上取整）
mid = \\lceil \\frac{low + high}{2} \\rceil \\quad \\text{（向上取整）}
mid=⌈2low+high⌉（向上取整）
- 注：标准的 408 统考中默认通常采用向下取整
⌊
(
l
o
w
+
h
i
g
h
)
/
2
⌋
\\lfloor (low+high)/2 \\rfloor
⌊(low+high)/2⌋，如果个人笔记或特定题目明确指定为向上取整，则判定树的左右子树形态将发生左右对调。
3.3 分块查找 (Block Search)
分块查找（又称索引顺序查找）将性能折中。若将长度为
n
n
n 的表均匀分成
b
b
b 个块，每块含有
s
s
s 个记录（即
n
=
b
×
s
n = b \\times s
n=b×s）。
- 平均查找长度公式（索引表与块内均采用顺序查找）：
A
S
L
=
b
+
1
2
+
s
+
1
2
=
b
+
s
2
+
1
ASL = \\frac{b+1}{2} + \\frac{s+1}{2} = \\frac{b+s}{2} + 1
ASL=2b+1+2s+1=2b+s+1
- 方法总结：第一项
b
+
1
2
\\frac{b+1}{2}
2b+1 为在索引表中确定所在块的平均查找长度；第二项s
+
1
2
\\frac{s+1}{2}
2s+1 为在确定的块内进行顺序查找的平均查找长度。两段查找无缝拼接。
四、 折半查找判定树特有性质（选择题秒杀神器）
折半查找的逻辑可以用一棵二叉树（判定树）形象表示，其形态具有极其严密的离散数学特征。
4.1 判定树的高度
- 对于含有
n
n
n 个成功结点的折半查找判定树，其高度h
h
h（不含失败结点/外部结点）为：
h
=
⌊
log
2
n
⌋
+
1
h = \\lfloor \\log_2 n \\rfloor + 1
h=⌊log2n⌋+1
- 该高度与完全二叉树的高度公式完全一致。
4.2 子树结点数的均衡规律（核心方法总结）
- 核心规律：折半查找树在任意一棵子树时，其左子树结点数都比右子树多个或一致（具体取决于 Mid 的取整方向）。
- 秒杀应用：
- 当题目给出特定的
n
n
n 并要求识别正确的判定树时，无须完整画出整棵树。 - 检查任意一个局部根节点：若 Mid 采用向下取整，则对于任意子树，当前根节点的左子树结点数必然等于右子树结点数，或者比右子树结点数少 1 个。
- 若个人笔记总结基于向上取整，则规律对调：其左子树结点数都比右子树多一个或一致。
- 牢记这一数量特征，可以在选择题中直接排除错误的树形选项！
