标签归档:Kruskal

图—最小生成树 Prime 和 Kruskal 算法

图的最小生成树的算法,这个问题要解决的问题场景很简单,要给几个地方修建铁路把它们连接起来。

如下图,黑色加粗的边表示是最小生成树的边。
最小生成树

如果最理想的情况,可以假设我们知道任意一点到其他点的距离,也就是边的权重,整个图应该是连通的,那我们开始修路吧
其实这里有一个变形,我们在教科书中[……]阅读全文