加权图
在我们进入最小生成树(MST)之前,先来了解什么是加权图:
- 加权图是一种图模型,我们为每条边关联权重(或代价)。也就是说,对于每条边 e,它都有一个与之关联的数值标签,记为 w(e)。
我们将研究用于解决加权图三类通用问题的算法:
- MST
- 最短路径
- 网络流
最小生成树
- MST 的输入:一个加权连通图 𝐺 = (𝑉, 𝐸),由顶点(或节点)𝑉 和边 𝐸 组成,并带有边权重。
- 输出:𝐺 的一棵最小生成树(MST)𝑇 = (𝑉, 𝐸𝑇)。也就是说,𝑇 是 𝐺 的一个连通生成子图(𝐸𝑇 ⊆ 𝐸),使得 𝑇 无环,且 𝑇 的总权重最小。
MST 的实际应用包括:
-
聚类分析。
-
最大瓶颈路径。
-
实时人脸验证。
-
用于纠错的 LDPC 码。
-
基于 Rényi 熵的图像配准。
-
在卫星和航空影像中寻找道路网络。
-
减少蛋白质氨基酸测序中的数据存储。
-
对湍流流体流动中粒子相互作用的局部性进行建模。
-
用于以太网桥接的自动配置协议,以避免网络中出现环路。
-
NP 难问题的近似算法(例如 TSP、Steiner 树)。
-
网络设计(通信、电力、水力、计算机、道路)。
如何在图 G 中找到 MST?
嗯,有两种方法可以做到:
- 你可以使用暴力法创建所有可能的生成树,并找出最轻的 W(G),但这种方法不可行,因为暴力法的大 O 复杂度可能会变得非常夸张。
- 我们可以改用贪心算法,比如 Prim 或 Kruskal 算法。
Prim 算法:
- 用单个选定的顶点初始化树。
- 通过找到尚未加入树中的最轻相邻边并将其连接到树上来扩展树;重复此过程,直到所有顶点都在树中。
Kruskal 算法:
- 初始化一个由所有节点组成的森林
- 选择一条(未被选中的)最小权重边,如果它连接森林中两棵不同的树,则选择它,否则丢弃它;重复此过程。
(未完待续……)