系统架构设计师【补充知识】: 应用数学 (核心总结)

一、 图论之最小生成树

(1)定义: 在连通的带权图的所有生成树中，权值和最小的那棵生成树(包含图中所有顶点的树)，称作最小生成树。
(2)针对问题: 带权图的最短路径问题。
(3)最小生成树的解法有普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法，我们常用克鲁斯卡尔算法。

【案例1】

1. 某小区有七栋楼房1~7，如下图所示，各楼房之间可修水管路线的长度(单位:百 米)已标记在连线旁。为修建连通各个楼房的水管，该小区内部水管的总长度至少为( )百米。
   
   A.20
   B.21
   C.24
   D.27

解析:
采用最小生成树的克鲁斯卡尔算法。
找出所有长度为 2 的边，试图将它们连接，有13、46，检验后没有形成闭环，可行。
找出所有长度为 3 的边，试图将它们连接，有17、36，检验后没有形成闭环，可行。
找出所有长度为 4 的边，试图将它们连接。有12和26。如果全部连接则形