代码随想录算法训练day63---图论系列7《prim算法&kruskal算法》

代码随想录算法训练

—day63

前言

今天是算法营的第63天，希望自己能够坚持下来！
今天继续图论part！今日任务：
● prim算法
●kruskal算法

一、53. 寻宝—prim算法

卡码网题目链接
文章讲解

思路：
本题是最小生成树的模板题，最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。
图中有n个节点，那么一定可以用n-1条边将所有节点连接到一起。
如何选择这n-1条边就是最小生成树算法的任务所在。

prim算法核心就是三步，

1. 第一步，选距离生成树最近节点
2. 第二步，最近节点加入生成树
3. 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

prim算法一共需要三个数组，一个用来存放节点，一个用来存放非生成树节点到生成树节点的距离，还有一个用来记录已经在生成树中的节点。
vector<vector> grid，vector minDist，vector isInTree

代码流程：
遍历n-1条边，遍历所有节点->根据minDist数组找到最近的节点，将节点加入生成树（标记isInTree为true）->更新minDist 最后minDist的就是到达所有节点的最小距离，累加得出结果（第一个节点不需要，只需要n-1条边）

时间复杂度:O（n2） （两个for循环）

代码如下：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
 
int main() {
    int v, e;
    int x, y, k;
    cin >> v >> e;
     
    //填一个默认最大值，题目描述val最大为10000
    vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));
     
    while (e--) {
        cin >> x >> y >> k;
        //因为是双向图，所以两个方向都要填上
        grid[x][y] = k;
        grid[y][x] = k;
    }
     
    //所有节点到最小生成树的最小距离
    vector<int> minDist(v + 1, 10001);
     
    //记录这个节点是否在树里
    vector<bool> isInTree(v + 1, false);
     
    //n个节点，只需要循环n-1次，建立n-1条边
    for (int i = 1; i < v; i++) {
        //1.选距离生成树最近节点
        int cur = -1; //记录找到最近的节点
        int minVal = INT_MAX;
        for (int j = 1; j <= v; j++) { //遍历顶点，1-v，顶点编号从1开始
            //非生成树节点并且距离比最小值小
            if (!isInTree[j] && minDist[j] < minVal) {
                minVal = minDist[j];
                cur = j;
            }
        }
        //2.将最近节点cur加入生成树
        isInTree[cur] = true;
         
        //3.更新minDist数组
        //只需关心新加入的cur与剩余非生成树节点的距离是否比原来的小
        for (int j = 1; j <= v; j++) {
            //非生成树节点，并且新加入的cur到该节点的距离比之前记录的小
            if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                minDist[j] = grid[cur][j];
            }
        }
    }
     
    int result = 0;
    //不计第一个顶点，因为统计的是边的权值，v个节点有v-1条边
    for (int i = 2; i <= v; i++) {
        result += minDist[i];
    }
     
    cout << result << endl;  
}

打印出来最小生成树的每条边

其实就是记录两个节点就可以，两个节点连成一条边。
使用一维数组就可以记录。parent[节点编号] = 节点编号，这样就把一条边记录下来了。（当然如果节点编号非常大，可以考虑使用map）
使用一维数组记录是有向边，不过我们这里不需要记录方向，所以只关注两条边是连接的就行。
parent数组初始化代码：

vector<int> parent(v + 1, -1);

在prim三部曲中的第三步，更新parent数组，代码如下：

for (int j = 1; j <= v; j++) {
    if (!isInTree[j] && grid[cur][j] < minDist[j]) {
        minDist[j] = grid[cur][j];
        parent[j] = cur; // 记录最小生成树的边 （注意数组指向的顺序很重要）
    }
}

这里需要注意是parent[j] = cur;不是parent[cur] = j；
因为对于cur这个节点，是可以通向多条边的，那么就是多个j对应同一个cur。

以下是完整代码：

#include<iostream>
#include<vector>
#include <climits>

using namespace std;
int main() {
    int v, e;
    int x, y, k;
    cin >> v >> e;
    vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));
    while (e--) {
        cin >> x >> y >> k;
        grid[x][y] = k;
        grid[y][x] = k;
    }

    vector<int> minDist(v + 1, 10001);
    vector<bool> isInTree(v + 1, false);

    //加上初始化
    vector<int> parent(v + 1, -1);

    for (int i = 1; i < v; i++) {
        int cur = -1;
        int minVal = INT_MAX;
        for (int j = 1; j <= v; j++) {
            if (!isInTree[j] &&  minDist[j] < minVal) {
                minVal = minDist[j];
                cur = j;
            }
        }

        isInTree[cur] = true;
        for (int j = 1; j <= v; j++) {
            if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                minDist[j] = grid[cur][j];

                parent[j] = cur; // 记录边
            }
        }
    }
    // 输出 最小生成树边的链接情况
    for (int i = 1; i <= v; i++) {
        cout << i << "->" << parent[i] << endl;
    }
}

代码输出：

1->-1
2->1
3->1
4->3
5->4
6->2
7->5 

二、53. 寻宝—kruskal算法

卡码网题目链接
文章讲解

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
kruscal的思路：
1.将边按权值从小到大排序
2.将权值最小，且不构成环的边加入到集合中（使用并查集）

代码如下：

#include<iostream>
#include<vector>
#include <algorithm>
 
using namespace std;
 
int n = 10001;
vector<int> father(n + 1, 0);
 
struct Edge {
    int l, r, val;
};
 
void init() {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}
 
int find(int u) {
    return u == father[u]? u: father[u] = find(father[u]);
}
 
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
     
    return u == v;
}
 
void join(int u, int v) {
    u = find(u);
    v = find(v);
     
    if (u == v) return;
    father[v] = u;
}
 
int main() {
    int v, e;
    int v1, v2, val;
    vector<Edge> edges; //存放边
    int result_val = 0;
     
    cin >> v >> e;
    while(e--) {
        cin >> v1 >> v2 >> val;
        edges.push_back({v1, v2, val});
    }
     
    //执行Kruskal算法
    //按边的权值对边进行从小到大排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.val < b.val;
    });
     
    //并查集初始化
    init();
     
    //从头开始遍历边
    for (Edge edge : edges) {
        //并查集，搜出两个节点的祖先
        int x = find(edge.l);
        int y = find(edge.r);
         
        //如果祖先不同，则不在同一个集合（不成环）
        if (x != y) {
            result_val += edge.val; //这条边可以作为生成树的边
            join(x, y);
        }
    }
    cout << result_val << endl;
    return 0;
  
}

打印出来最小生成树的每条边

因为 Kruskal 本来就是直接操作边，只需要找到 在哪里把生成树的边保存下来就可以了。
当判断两个节点不在同一个集合的时候，这两个节点的边就加入到最小生成树， 所以添加边的操作在这里：

vector<Edge> result; // 存储最小生成树的边
// 如果祖先不同，则不在同一个集合
if (x != y) {
    result.push_back(edge); // 记录最小生成树的边
    result_val += edge.val; // 这条边可以作为生成树的边
    join(x, y); // 两个节点加入到同一个集合
}

总结

• prim算法 ：
  1.需要三个数组，一个存放节点和权值vector<vector> grid，一个存放非生成树节点到生成树的最小距离vectorminDist，一个存放节点是否成为生成树节点vectorisInTree。
  2.循环n-1次，遍历节点，找到是非生成树节点并且距离最小，加入到生成树节点中（isInTree标记为true）
  3.遍历节点，更新minDist

• kruskal算法：
  1.自定义结构体，Edge（v1,v2,val）,用vectoredges存放边
  2.遍历每条边，分别找到边的两个节点的根，判断如果不构成环也就是不同根（使用并查集），则两节点加入到集合（这条边加入到生成树中了），同时累加权值

Kruskal 与 prim 的关键区别在于，prim维护的是节点的集合，而 Kruskal 维护的是边的集合。 如果 一个图中，节点多，但边相对较少，那么使用Kruskal 更优。

Prim 算法 时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。
Kruskal算法 时间复杂度 为 nlogn，其中n 为边的数量，适用稀疏图。

明天继续加油！