加权图

在我们进入最小生成树(MST)之前,先来了解什么是加权图:

  • 加权图是一种图模型,我们为每条边关联权重(或代价)。也就是说,对于每条边 e,它都有一个与之关联的数值标签,记为 w(e)。

我们将研究用于解决加权图三类通用问题的算法:

  1. MST
  2. 最短路径
  3. 网络流

最小生成树

  • MST 的输入:一个加权连通图 𝐺 = (𝑉, 𝐸),由顶点(或节点)𝑉 和边 𝐸 组成,并带有边权重。
  • 输出:𝐺 的一棵最小生成树(MST)𝑇 = (𝑉, 𝐸𝑇)。也就是说,𝑇 是 𝐺 的一个连通生成子图(𝐸𝑇 ⊆ 𝐸),使得 𝑇 无环,且 𝑇 的总权重最小。

MST 的实际应用包括:

  1. 聚类分析。

  2. 最大瓶颈路径。

  3. 实时人脸验证。

  4. 用于纠错的 LDPC 码。

  5. 基于 Rényi 熵的图像配准。

  6. 在卫星和航空影像中寻找道路网络。

  7. 减少蛋白质氨基酸测序中的数据存储。

  8. 对湍流流体流动中粒子相互作用的局部性进行建模。

  9. 用于以太网桥接的自动配置协议,以避免网络中出现环路。

  10. NP 难问题的近似算法(例如 TSP、Steiner 树)。

  11. 网络设计(通信、电力、水力、计算机、道路)。

    延伸阅读:http://www.ics.uci.edu/~eppstein/gina/mst.html

如何在图 G 中找到 MST?

嗯,有两种方法可以做到:

  1. 你可以使用暴力法创建所有可能的生成树,并找出最轻的 W(G),但这种方法不可行,因为暴力法的大 O 复杂度可能会变得非常夸张。
  2. 我们可以改用贪心算法,比如 Prim 或 Kruskal 算法。

Prim 算法:

  • 用单个选定的顶点初始化树。
  • 通过找到尚未加入树中的最轻相邻边并将其连接到树上来扩展树;重复此过程,直到所有顶点都在树中。

Kruskal 算法:

  • 初始化一个由所有节点组成的森林
  • 选择一条(未被选中的)最小权重边,如果它连接森林中两棵不同的树,则选择它,否则丢弃它;重复此过程。

(未完待续……)