图论---最小生成树问题

        在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。解决最小生成树问题一般有两种算法：Kruskal算法和Prim算法。

Kruskal算法

原理：基本思想是从小到大加入边，是个贪心算法。我们将图中的每个边按照权重大小进行排序，每次从边集中取出权重最小且两个顶点都不在同一个集合的边加入生成树中。注意：如果这两个顶点都在同一集合内，说明已经通过其他边相连，因此如果将这个边添加到生成树中，那么就会形成环。这样反复做，直到选出n-1条边。时间复杂度为O(m*logm)

算法过程：此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。 具体过程如下所示： 步骤1：先对图中所有的边按照权值进行排序 步骤2：如果当前这条边的两个顶点不在一个集合里面，那么就用并查集的Union函数把他们合并在一个集合里面(也就是把他们放在最小生成树里面)，如果在一个并查集里面，我们就舍弃这条边，不需要这条边。 步骤3：一直执行步骤2，知道当边数等于n-1（n为节点个数），那就说明这n个顶点就连合并在一个集合里面了；如果边数不等于顶点数目减去1，那么说明这些边就不连通，即无法构成最小生成树。

代码框架：

int n, m; // n是点数，m是边数 
int p[n + 1]; // 并查集的父节点数组 
struct Edge{ // 存储边  
    int a, b, w; 
    bool operator< (const Edge &W)const { 
        return w < W.w; 
    } 
}edges[m]; 
​
int find(int x){ // 并查集核心操作 
     return p[x] == x ? x : p[x] = find(p[x]);
}
void init(){ // 初始化并查集 
    for(int i = 1; i <= n; i++){
        p[i] = i;
    }
}
int kruskal() {
    sort(edges, edges + m); 
    init();
    int res = 0, cnt = 0; 
    for (int i = 0; i < m; i++) { // 从m条边选择n-1条边
        int a = edges[i].a, b = edges[i].b, w = edges[i].w; 
        a = find(a), b = find(b); 
        if (a != b)  { // 如果两个连通块不连通，则将这两个连通块合并
            p[a] = b; 
            res += w; 
            cnt++; 
        } 
    }
    if (cnt < n - 1) return INF; 
    return res; 
}

Prim算法

原理：基本思想是从一个结点开始，不断加点。因此该算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。时间复杂度为O(n * n + m)。

算法过程：

1. 用两个集合A{}，B{}分别表示找到的点集，和未找到的点集；

2. 我们以A中的点为起点a，在B中找一个点为终点b，这两个点构成的边（a，b）的权值是其余边中最小的

3. 重复上述步骤#2，直至B中的点集为空，A中的点集为满

代码框架：

int n; // 节点个数
vector> g(n, vector(n)); // 邻接矩阵，存储所有边
vector dis(n); // 存储其他节点到当前最小生成树的距离
vector v(n); // 存储每个节点是否加入到最小生成树中
​
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){
    const int inf = 0x3f3f3f3f;
    memset(dis, 0x3f, sizeof dis);
    int res = 0;
    for(int i = 0; i < n; i++){
        int p = -1;
        for(int j = 0; j < n; j++){
            if(!v[j] && (p == -1 || dis[j] < dis[p])){
                p = j;
            }
        }
        if(i && dis[p] == inf){ // dis[p] = inf说明找到的节点与最小生成树不连通，但是当i = 0说明是第一个节点，不考虑连通
            return inf;
        }
        if(i){
            res += dis[p];
        }
        v[p] = true;
        for(int j = 0; j < n; j++){
            dis[j] = min(dis[j], g[p][j]); // 与Dijkstra算法的区别
        }
    }
    return res;
}
​

题单

1584. 连接所有点的最小费用 - 力扣（LeetCode）