Prim

Prim's algorithm

可以使用堆优化，类似Dijkstra，但是使用堆优化，效率未必提高。

对于完全图的情况：

不使用堆优化，时间复杂度为$O(n^2)$；

使用堆优化，时间复杂度为$O(n^2 \log n)$。

所以说对于以邻接矩阵输入的图，没必要去用Kruskal。

参考代码（Luogu P1265）：

#include <bits/stdc++.h>
using namespace std;
int n;
double x[5020], y[5020];
double d[5020];
bool v[5020];
double ans;
double dist(int i, int j) {
    // 返回点i和点j之间的距离。
    return hypot(x[i] - x[j], y[i] - y[j]);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    for (int i = 1; i < n; i++) {
        d[i] = 1e30;
    }
    // 除了0号点，每个点距离都初始化为无穷大。
    for (int i = 0; i < n; i++) {
        int mini = -1;
        double mind = 1e30;
        for (int j = 0; j < n; j++) {
            if (!v[j]) {
                if (mind > d[j]) {
                    mind = d[j];
                    mini = j;
                }
            }
        }
        // 每次找到未被标记的点中，距离最近的点。
        ans += mind;
        v[mini] = true;
        // 选择连向这个点的边，并标记这个点已被选择。
        for (int j = 0; j < n; j++) {
            if (!v[j]) {
                d[j] = min(d[j], dist(j, mini));
                // 更新剩余所有点的距离。
            }
        }
    }
    cout << fixed << setprecision(2) << ans << endl;
    return 0;
}

$O(n^2)$

n is the number of vertices.

The edge with minimum weight in a cut must be in MST.

2 arrays
visited, whether we have chosen this vertex.
distance, the minimum distance from this vertex to a chosen vertex.

do n times
find the vertex min_i with minimum distance, it is not chosen. n * O(n) -> n * O(log n)
ans += d[min_i]
v[min_i]
for each edge starting from min_i to j, the length dist(min_i, j) O(m) -> O(m log m)
d[j] = min(d[j], dist(min_i, j))

If the graph is a complete graph, we will use prim's algorithm.

Prim：只对完全图使用
时间复杂度O(n^2)
但是不能输入n^2个数字，只能输入n个，所以距离是通过某种方式算出来的

需要2个数组
v数组，标记数组，表示每个点是否已经被选择
d数组，距离数组，表示每个点到已经选择的集合的距离的最小值是多少

v数组初始化0，表示都没有被选择
d数组初始化无穷大，因为没已经选择的集合
d中初的起点始化为0，保证第一个选择的是起点

做n轮 // 每个点恰好被选1次
找到d数组中，未被标记的位置中的最小值d[min_i]，还需要记录最小值的位置min_i
ans += 最小值d[min_i]
标记最小值的位置min_i为选择 v[min_i] = true
枚举从min_i出发的所有的边(min_i, j, dist(min_i, j))，
如果j没有被标记过
更新d[j] = min(d[j], dist(min_i, j))
// 根据需要，考虑是否需要记录是谁更新的j

ans = 0 + 最小生成树上(n-1)个边权
d数组中存的是0和最小生成树上(n-1)个边权

Luogu P1265
Prim最小生成树（完全图，邻接矩阵）

Luogu P2872
Prim最小生成树（完全图，邻接矩阵）但是需要考虑权值为0的边

Luogu P2212
Prim最小生成树（完全图，邻接矩阵）如果边权小于c，那么返回$+\infty$

Luogu P1546
最小生成树（邻接矩阵） 推荐Prim，也可以Kruskal