最小生成树（一）——Prim算法

858. Prim算法求最小生成树

image.png

稠密图是用朴素Prim算法
稀疏图是用Kruskal算法

image.png

朴素版的Prim算法和Dijkstra算法很像。
第一步，将距离矩阵dist初始化为正无穷

让所有点到集合的距离都变成+正无穷 ，所以一开始大家的距离都是+正无穷

第二步，迭代n次(因为要加入n个点进去)

(Dijkstra算法是迭代n - 1次，因为D算法一开始就选中了1个点，只剩下了n - 1个点。Prim算法一开始什么点都没选，所以是迭代n次)

第三步，首先找到集合外距离集合最近的点，然后用这个点t（也就是刚刚选中到集合的点）更新其他点到集合的距离（Dijkstra算法中，是更新其他点到起点的距离）。

这个集合中就是已经是最短距离的节点的集合。

第四步，把t加入到集合当中去（st[t] = true）。

边的正负都没关系

集合S：当前已经在连通块当中的所有点

image.png

绿色的就是最小生成树（选中的点和点之间的边就是最小生成树的边）

image.png

算法流程：

一共n次迭代(n = 4)：

1. 第一次迭代，将节点1放入最小生成树中。注意，这个时候，dist[1]还没有被更新。但是dist[2], dist[3], dist[4]已经被更新了（因为这里相当于默认选择第1个点先放入集合中）。dist[i]表示第i个节点到最小生成树这个集合的距离。
2. 第二次迭代。dist[1]被更新了。。
3. 每一次迭代，都是试图将每一个节点放入最小生成树的集合中。将节点放入集合的标准是，这个点还不在集合中，且这个点到集合的距离最短，这个最短距离的点t，一开始找的可能不是最短的，所以要判断dist[t] > dist[j]; t = j。先将权重最小的边放进去。这点跟Kru算法很像。
4. 因为每一次迭代，我们的最小生成树都更新了，所以要更新其他还不在最小生成树中的节点到最小生成树这个集合的最短距离。
5. 例如，一开始只有1是最小生成树中的点，2和1的距离是2，但是如果把3加进去后，2和3的距离是1，那么dist[2]就应该会被更新成1。
6. 所以外面的for循环表示迭代每一个节点，试图将每一个节点加入到最小生成树中。里面的for循环则是因为最小生成树的集合一直在变，所以每个集合外的点到它的距离就一定要更新。(是原先的距离短，还是新加入的节点和集合外的节点的边权更短)。

// 这道题是一个稠密图（用邻接矩阵来存比较nice）

// 这个图里面是有重边的，有重边的情况一定是留下长度最短的那条边（所以可以一开始把所有点与点之间的距离初始化为正无穷）

// 所有点都不连通的时候，就不存在生成树

// 每次for()循环中，先找最小值t，更新其他点，然后把t加入到集合中（Prim）

// 每次for()循环中，先找最小值t，然后把t加入到集合中，更新其他点（Dijkstra）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int dist[N];
int g[N][N];
bool st[N];


int prim()
{
    int res = 0;

    memset(dist, 0x3f, sizeof dist);

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        

      //  这个for循环的目的——当前集合外的所有点当中，距离集合最小的点
      // !st[j] 表明是集合外，t = -1表明现在还没有找到任何一个点，
      // 或者t到集合的距离大于j到集合的距离，这样，就更新`t = j`
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        //  走完上面这个for循环后，t存储的就是当前距离集合最小的点
        if (i && dist[t] == INF) return INF;  // 如果走过一圈迭代，
                                              // 但是所有点都是INF，说明不连通
        if (i) res += dist[t];
      
        //  用t这个点更新其他点到集合的距离
        // 放到这个位置也是为了处理自环，假如自环的权重是-10
        // 那么这句话放在 res += dist 上面，就会让res错误，所以先累加res，再更新即可
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);  

        st[t] = true;
    }

    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);

    cin >> n >> m;
    while (m --)
    {
        int a, b, w;
        cin >> a >> b >> w;

        g[a][b] = g[b][a] = min(w, g[a][b]);  // 取min是处理重边
    }

    int res = prim();

    if (res == INF) puts("impossible");
    else cout << res << endl;

    return 0;
}