了解最小生成树 (MST)

假设我们正在设计新的办公园区，园区内有多栋相互连接的大楼。如果我们通过考虑每栋楼之间的互联来解决这个问题，将需要大量的电缆。但是，如果我们能以某种方式通过共同的连接方式将所有建筑连接起来，即每栋建筑与其他每栋建筑之间只需一条连接线，那么这种解决方案将减少冗余和成本。如果我们把建筑物看作顶点，把建筑物之间的连接看作边，我们就可以用这种方法构建一个图。我们要解决的问题也称为最小生成树或 MST。请看下图。我们有 10 个顶点和 21 条边。但是，我们可以只用 9 条边（暗线）连接所有 10 个顶点。这样，我们的成本或距离就会降到最低：