10.3 最小生成树

最小生成树（MST）用最少的边连接所有节点，且总权重最小。在金融中，MST 用于提取股票相关性网络的核心结构，发现行业集群和系统性风险传播的主干通道。

---

Kruskal 算法

算法简述

Kruskal 算法求加权无向图的最小生成树（MST）：

1. 将所有边按权重从小到大排序
2. 从最小边开始，逐条加入，若加入后不形成环则保留
3. 直到加入 $|V| - 1$ 条边

时间复杂度：$\mathcal{O}(E \log E)$（主要是排序开销）

关键技巧

并查集（Union-Find / Disjoint Set，一种高效管理"元素属于哪个集合"的数据结构，支持两个核心操作：① Find 查找元素所属集合的根；② Union 合并两个集合。Kruskal 算法用并查集来快速判断加入一条边是否会形成环——如果一条边的两个端点已经在同一集合中，说明它们已经被之前加入的边连通了，再加入这条边就会形成环）——每次检查边的两个端点是否属于同一集合，若是则这条边会形成环。

---

手算实例：Kruskal 算法（5 节点图）

使用与前两节相同的 5 节点加权无向图。

边排序

排序	边	权重
1	(2,4)	1
2	(3,4)	1
3	(1,2)	2
4	(1,4)	3
5	(1,3)	4
6	(4,5)	5

执行过程

步骤	考虑边	权重	成环？	操作	当前 MST 边数	已选边集
1	(2,4)	1	否	加入	1
2	(3,4)	1	否	加入	2
3	(1,2)	2	否	加入	3
4	(1,4)	3	是（1-2-4-1 成环）	跳过	3	同上
5	(1,3)	4	是（2-4-3-1-2 成环）	跳过	3	同上
6	(4,5)	5	否	加入	4

结束：已加入 $|V| - 1 = 4$ 条边，MST 构建完成。

MST 总权重：$1 + 1 + 2 + 5 = 9$

 (1)────(2)
      2  |
         |
        1|
         |
 (3)────(4)──(5)
     1     5

---

Prim 算法

算法简述

Prim 算法从单个节点开始，逐步生长 MST：

1. 从任意节点开始，标记为已访问
2. 在所有连接已访问和未访问节点的边中，选择权重最小的
3. 将这条边和对应的新节点加入 MST
4. 重复 2-3 直到所有节点加入

时间复杂度：$\mathcal{O}(E \log V)$（使用优先队列）

Kruskal vs Prim

特性	Kruskal	Prim
策略	边驱动（加边）	节点驱动（生长）
适用场景	边数较少的稀疏图	边数较多的稠密图
数据结构	并查集	优先队列
是否依赖起始点	否	是

---

Python 示例

import networkx as nx

# 构建加权无向图
G = nx.Graph()
edges = [
    (1, 2, 2),
    (1, 3, 4),
    (1, 4, 3),
    (2, 4, 1),
    (3, 4, 1),
    (4, 5, 5)
]
G.add_weighted_edges_from(edges)

# Kruskal 最小生成树
mst = nx.minimum_spanning_tree(G, algorithm='kruskal')
print("最小生成树边集:")
total_weight = 0
for u, v, data in mst.edges(data=True):
    w = data['weight']
    total_weight += w
    print(f"  ({u}, {v}), 权重 = {w}")
print(f"MST 总权重 = {total_weight}")

# --- 输出 ---
# 最小生成树边集:
#   (1, 2), 权重 = 2
#   (2, 4), 权重 = 1
#   (3, 4), 权重 = 1
#   (4, 5), 权重 = 5
# MST 总权重 = 9

---

Quant Link：股票相关性网络的 MST

最小生成树用于构建金融网络的主干——在银行间网络中找到最重要的资金流动通道，排除次要连接。

股票相关性网络

在股票相关性网络中，MST 用于提取市场的核心层级结构：

1. 计算股票间的相关系数矩阵 $\rho_{ij}$
2. 转换为距离度量：$d_{ij} = \sqrt{2(1 - \rho_{ij})}$
3. 以距离为边权构建完全图
4. 求 MST 得到最显著的层级聚类关系

应用价值

应用	描述
行业聚类	MST 自动按行业板块聚类，验证行业分类的合理性
核心-边缘结构	找出市场中的核心股票（MST 中连接多个集群的节点）
危机检测	危机期间 MST 结构显著变化（"变短"或"星形化"）
组合优化	基于 MST 的聚类信息构建分散化投资组合
\n> 下一步：继续学习 10.4 网络中心性