最小生成树（Minimum Spanning Tree, MST）

这玩意儿听起来挺唬人，但其实思想特别朴素。想象一下，现在有几个村庄，你要负责修路把它们都连起来，并且想花最少的钱。每条备选的路都有一个造价。你怎么设计这个路网，才能保证所有村庄都能互相到达，并且总造价最低？ 这就是最小生成树。给你一张带权重的无向图，找一棵能连接所有顶点的树，并且这棵树所有边的权重之和最小。 扯远了，拉回来。搞定这个问题，有两个经典的“骚操作”，一个叫Kruskal，一个叫Prim。这两个都是贪心算法，但贪心的角度不太一样。今天咱们把这俩都盘明白了。 准备工作：图怎么表示？ 在撸...