Prim算法

时间复杂度：

  • O(n^2 + m)

具体实现：

  • 邻接矩阵存边的权值
  • 距离初始化为正无穷
  • 每次选择当前集合终和外界所连边的权值最小的点
  • 将该边所连的点扩展，并用刚扩展的点更新其他点到当前集合的权值

算法证明：

  • 证明思路与kruskal算法类似。
    • 如何证明这条边一定可以被选？
    • 假设不选当前边，最终得到了一棵树。然后将这条边加上，那么必然会形成一个环，在这个环上，一定可以找出一条长度不小于当前边的边，那么把当前边替换上去，结果一定不会变差。
  • 证明结论：当前与外界直接相连的权值最小的一条边，这条边一定可以出现在最优解中。
  • 证明过程如下：
    • 反证法：假设选择最小生成树的某一个状态集合x扩展某一个边x1(最小)时没有选择该边，选择了另一个边x2(非最小)，从而形成了一个生成树。
    • 证明：已知集合x可扩展多个边x1, x2……x’等(权值升序排列)，选择了x2边扩展。若将x1边加入扩展了x2边而最终形成的生成树中，则必定会形成一个环，且该环上一定包含x’这条边，因为x1为扩展出来的权值最小的边，x’等其他边时扩展出来的非权值第一小边，则将x’去掉，x1加上，形成的还是一个生成树，且该生成树的总权值小于原来的生成树。如此，得证。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 0; j < n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;
        res += dist[t];
        for (int j = 0; j < n; j ++ )
            dist[j] = min(dist[j], g[t][j]);
    }
    
    return res;
}