上一篇【第07篇】算法基本功（上）：折半查找与高效排序 下一篇【第09篇】工欲善其事：开发环境与单元测试
摘要
折半查找和排序好懂，最小生成树听起来就像图论课上的冷门货，离搜索引擎八竿子打不着。其实不然。图结构在搜索里到处都是：网页之间的链接是图，词的共现关系也是图。本文用通俗比喻讲清最小生成树是什么，对比 Prim 和 Kruskal 两种贪心思路，顺带说说图怎么表示、怎么遍历，为后面文本挖掘和聚类埋个伏笔。
一、图和树：搜索里的隐形骨架
先建立直觉。什么是图？一堆点（顶点）加上点之间的连线（边）就是图。网页是点，超链接是边，整个互联网就是一张巨大的有向图。词是点，经常一起出现的词之间连一条边，这就是词的共现图。
树是图的一种特例：没有环、连通。而生成树是"用最少的边把图中所有点连起来"的那棵树。在无数种连法里，如果每条边有权重（比如距离、代价），总权重最小的那个，就叫最小生成树（MST）。
【图 → 生成树 → 最小生成树】
原始图(带权边) 最小生成树(连遍所有点, 总权重最小)
A──4──B A
/│ /│ /│
2 3 1 5 2 3
/ │ / │ / │
C──1┘ D──6┘ C D
\\ /
1┘
二、最小生成树是啥，用人话讲
打个比方。你要在几个城市之间铺光缆，任意两城之间都能铺，费用不同。目标是让所有城市互通，又总花费最低。这恰恰就是最小生成树问题：城市是点，可铺的光缆是带权边，求一棵连通全部城市、总权重最小的树。
在搜索里，它可以用来做聚类。把相似的项（网页、词、商品）看成点，相似度当成权重，最小生成树能把"长得像的一伙"自然地连在一起，再按权重阈值砍掉几条边，就得到若干簇。后面讲语义搜索、同义词发现时，这种图聚类思路会再出现。
三、Prim 和 Kruskal：两种贪心思路
求 MST 主要有两种经典算法，都是贪心，但角度不同。
Prim 算法从某一个点出发，每一步都选择"当前已连通部分"到"未连通部分"之间权重最小的边，把新点拉进来。像个不断长大的连通块，每次长一截最短的边。
【Prim：从一个点长成一棵树】
起点A → 选最小邻边(A-C:2) → 选(C-D:1) → 选(A-B:3)
已连: {A} → {A,C} → {A,C,D} → {A,C,D,B}
Kruskal 算法反过来，先把所有边按权重从小到大排序，然后依次往里加边，只要这条边不形成环就保留，直到连遍所有点。像个不断"接线"的过程，遇环就跳过。
【Kruskal：按权重从小到大接线】
边排序: (C-D:1)(A-C:2)(A-B:3)…
依次加: 加C-D ✓ → 加A-C ✓ → 加A-B ✓ → 成树, 跳过会成环的
两者复杂度不同，Prim 适合边多的稠密图，Kruskal 配合并查集适合边少的稀疏图。工程上选哪个，看数据长什么样。
四、最小生成树在搜索里能干嘛
再展开说几个落点，省得你觉得它只是习题。
文档聚类。把文档向量化后算相似度，建图求 MST，砍边成簇，可以用来做"相似文章分组"“话题发现”。
同义词/相关词挖掘。词共现图求 MST，能把语义相近的词聚成一团，辅助自动发现同义词，后面语义搜索篇会用到。
网页去重与站点结构分析。链接图上的连通分量分析，能识别镜像站、聚合页，辅助抓取调度。
【MST 的搜索落点】
文档/词 向量化 → 相似度建图 → 求MST → 砍边成簇
│
┌───────────────┼───────────────┐
▼ ▼ ▼
文档聚类 同义词挖掘 站点结构分析
五、图的表示与遍历
要用图，先得存图。两种主流存法：
邻接矩阵，用二维数组存点与点之间是否相连、权重多少。查两点关系快，但点一多（比如上亿网页），空间爆炸，基本用不了。
邻接表，每个点挂一个"邻居列表"。省空间，适合稀疏图（网页链接就是稀疏的，一个页通常只链几十个）。实际系统几乎都用邻接表。
【两种图表示】
邻接矩阵(稠密) 邻接表(稀疏, 更常用)
A B C D A → [B, C]
A 0 1 1 0 B → [A]
B 1 0 0 1 C → [A, D]
C 1 0 0 1 D → [B, C]
D 0 1 1 0
遍历图就两种基本套路：**广度优先（BFS）**一层层向外扩，适合"找最近的相关项"；**深度优先（DFS）**一条路走到黑再回头，爬虫顺着链接抓就是用 DFS 思想。前面讲爬虫时那套"取 URL、抓、抽链接、再入队"的循环，本质就是 BFS。
六、并查集：Kruskal 的发动机
Kruskal 算法里有个关键判断："加这条边会不会成环？"靠的就是并查集（Union-Find，也叫 Disjoint Set）。它维护若干互不相交的集合，支持两个操作：find（找某个点的根）和 union（合并两个点所在集合）。
// 并查集（带路径压缩 + 按秩合并）
int[] parent = new int[n];
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // 路径压缩
x = parent[x];
}
return x;
}
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false; // 同根，会成环，跳过
parent[ra] = rb;
return true; // 不同根，合并
}
加路径压缩后，单次操作接近 O(1)。Kruskal 每考虑一条边，就问 union 一下：返回 false 说明两点已连通，加这条边必成环，丢弃；返回 true 才保留。就这么简单，一棵最小生成树就建出来了。
给个具体例子感受数值。假设四个文档，两两相似度（边权）如下：A-B:2，A-C:3，C-D:1，A-D:5，B-D:4。按权重排序后依次尝试：加 A-B(2) 保留 → 加 A-C(3) 保留 → 加 C-D(1) 保留，此时四者全连通，后面 B-D(4)、A-D(5) 都因成环跳过。总权重 2+3+1=6，这就是 MST。
并查集本身也是搜索引擎里的小工具，比如做链接图的连通分量分析（哪些网页属于同一站点簇）、去重时的等价类归并。别看它小，处处能用上。至于 Prim 和 Kruskal 怎么选：边多的稠密图用 Prim（从点长树，避免排太多边），边少的稀疏图用 Kruskal（排序后接线，配并查集）。实际里文档/词共现图通常稀疏，Kruskal 更常见。
补一句：图算法在搜索里的渗透远比想象深。PageRank 这种网页排序经典，本质就是在链接图上做随机游走；社区发现（把图分成若干联系紧密的团）用在话题聚类和垃圾链接识别。最小生成树只是我们入门的一扇窗，后面讲文本挖掘和语义搜索，还会不断回到"图"这个视角。
七、图的算法不止 MST：PageRank 与社区发现
最小生成树只是图算法在搜索里的一小块。还有两个名字你一定听过，顺便串一下，省得后面见到陌生。
PageRank，搜索引擎排序的鼻祖之一。它把网页链接看成投票：被越多高质量页面指向的页面，越重要。算法本质是在链接图上做随机游走，迭代算每个节点的权重，直到收敛。Google 当年就是靠它起来的。我们现在写的迷你引擎用 TF 打分，但真要做网页搜索，PageRank 这类链接分析几乎是标配。
社区发现，把图划分成若干"内部联系紧密、外部稀疏"的团。用在话题聚类（同一话题的网页抱团）、垃圾链接识别（一堆互相指向的作弊站抱团）。最小生成树砍边其实也能做粗略聚类，但社区发现算法（比如 Louvain）更专业。
【图算法在搜索里的版图】
最小生成树 ──▶ 聚类、同义词、站点结构
PageRank ──▶ 网页重要性排序
社区发现 ──▶ 话题聚类、反作弊
BFS/DFS ──▶ 爬虫遍历、链接分析
你看，从爬虫的链接遍历，到索引的向量聚类，再到排序的链接分析，图这个视角贯穿始终。前面说"图和树是搜索里的隐形骨架"，到这你应该有点实感了。算法基本功就聊到这，下一篇我们收一收，搞定开发环境和测试，就要真动手了。
本篇小结
图和树是搜索里的隐形骨架：网页链接、词共现都是图。最小生成树用最少边连通所有点且总权重最小，通过"向量化→建图→求 MST→砍边成簇"能做文档聚类、同义词挖掘和站点分析。求 MST 有 Prim（从点长树）和 Kruskal（按权接线，配并查集）两种贪心。图用邻接表存储更省空间，遍历靠 BFS 和 DFS，后者正是爬虫的核心思想。
下一篇，我们收一收基础，聊聊动手前必须搞定的开发环境和单元测试。搜索引擎项目，测试尤其不能少。
上一篇【第07篇】算法基本功（上）：折半查找与高效排序 下一篇【第09篇】工欲善其事：开发环境与单元测试
