想象这样一个场景，一个国家要在国内铺设铁路，目标是以最低的成本将几个重要的城市连通起来，确保所有城市都能互相抵达。而如何铺设这些铁路呢？这就是最小代价生成树(MST)的问题。

这类问题的解决有两个著名的贪心算法── Prim 算法和 Kruskal 算法。

基于边的贪心策略：Kruskal 算法

一个很容易想到的思路，就是我们不断的取权重最小的边，将各个节点连起来，如果新加入的边会使已有的图形成回路，那就跳过。

这就好比将每个节点看成一个岛屿，通过不断合并小岛，最终便可以形成一个新的大陆。而这类合并的操作，我们完全可以通过 并查集 的思路取实现。

Algorithm: Kruskal_MST(graph)
Input: A graph stored in adj
Output: a edge array mst which forms the MST

Fn Kruskal_MST(G)
    init an array visited with all set the FALSE
    init an empty array mst
    Sort all edges in E in non-decreasing order of weights
    init DSU structrue // 初始化并查集结构

    for each edge (u, v) in sorted E:
        if(find(u) != find(v)): // 如果u, v 属于不同的集合，也即它们合并后不会形成环
            mst.append((u,v))
            union(u,v)          // 将u,v所在两个集合合并
        endif

        if(mst.size() == |V| - 1):
            break               // 包含 |V| - 1 条边后说明MST已生成
        endif

    return mst

基于点的贪心策略：Prim 算法

和 Kruskal 算法相异却殊途同归的一种思路是选取最近的点，这就是Prim算法。

我们可以先随机选取一个起点形成一个集合，然后检查他的所有邻居，将距离最近的点不断纳入其中。然后继续寻找和集合中的点距离最近的点，继续纳入，循环往复，知道所有点都在其中。

它就好比是从一个起点开始，不断向阻力最小的方向扩张自己的区域，因而总是能够将最近的点加入其中。

为了方便的找出这个最小权重边，我们使用优先级队列来存储临时节点。

Algorithm Prim_MST(graph)
Input: A graph stored in adj
Output: An array mst which stores the edges forming MST

Fn Prim_MST(G)
    init a priority queue Q
    init an array visted with all set to FALSE
    init an empty min_edge with all set to IFINITY // min_edge[v]代表到达v点的最小权重边的权重
    init an empty array mst

    pick an arbitrary vertex s // 随机选取一个起点
    min_edge[s] = 0
    Q.enqueue({0,s,null}) // {weight,vertex,parent_edge},队列会更具weight值自动排序
    while(Q is not empty):
        {w, u, edge} = Q.dequeue() // 由于是优先级队列，我们总是可以获得min_edge最小的节点

        if(visited[u]==TRUE):
            continue
        endif

        mark visted[u] = TRUE

        if(edge != null):
            mst.append(edge)  // 处理该点时，指向自己的最小权重边已经确定
        endif

        for each vertex v in G.adj[u]:
            if(weight(u,v)<min_edge[v]):
                min_edge[v]=weight(u,v)
                Q.enqueue({min_edge[v],v,(u,v)})
            endif
        endfor
    endwhile

    return mst

算法比较

两种算法都能够找出正确的MST,但是由于寻找思路不同，面对不同的图，算法效率也不同。

Prim 算法适合稠密图（边数远大于节点数），因为它主要操作顶点；Kruskal算法适合系数图，因为它效率的瓶颈主要在与对边排序，并查集操作在时间工程中技术是常数级的，并且算法本身更易于实现。