首页 > 编程语言 >图论篇--代码随想录算法训练营第五十七天打卡| 最小生成树问题

图论篇--代码随想录算法训练营第五十七天打卡| 最小生成树问题

时间:2024-09-12 18:50:42浏览次数:13  
标签:val int father 随想录 生成 find 第五十七 打卡 节点

题目链接:53. 寻宝(第七期模拟笔试)

题目描述:

在世界的某个区域,有一些分散的神秘岛屿,每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路,方便运输。

不同岛屿之间,路途距离不同,国王希望你可以规划建公路的方案,如何可以以最短的总公路距离将 所有岛屿联通起来(注意:这是一个无向图)。 

给定一张地图,其中包括了所有的岛屿,以及它们之间的距离。以最小化公路建设长度,确保可以链接到所有岛屿。

解题思路:

1、prim算法

prim 算法是维护节点的集合

三部曲:

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

minDist数组 用来记录 每一个节点距离最小生成树的最近距离

代码

#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-1次,建立 n - 1条边,就可以把n个节点的图连在一起
    for (int i = 1; i < v; i++) {

        // 1、prim三部曲,第一步:选距离生成树最近节点
        int cur = -1; // 选中哪个节点 加入最小生成树
        int minVal = INT_MAX;
        for (int j = 1; j <= v; j++) { // 1 - v,顶点编号,这里下标从1开始
            //  选取最小生成树节点的条件:
            //  (1)不在最小生成树里
            //  (2)距离最小生成树最近的节点
            if (!isInTree[j] &&  minDist[j] < minVal) {
                minVal = minDist[j];
                cur = j;
            }
        }
        // 2、prim三部曲,第二步:最近节点(cur)加入生成树
        isInTree[cur] = true;

        // 3、prim三部曲,第三步:更新非生成树节点到生成树的距离(即更新minDist数组)
        // cur节点加入之后, 最小生成树加入了新的节点,那么所有节点到 最小生成树的距离(即minDist数组)需要更新一下
        // 由于cur节点是新加入到最小生成树,那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢
        for (int j = 1; j <= v; j++) {
            // 更新的条件:
            // (1)节点是 非生成树里的节点
            // (2)与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小
            // 很多录友看到自己 就想不明白什么意思,其实就是 cur 是新加入 最小生成树的节点,那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入,需要更新一下数据了
            if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                minDist[j] = grid[cur][j];
            }
        }
    }
    // 统计结果
    int result = 0;
    for (int i = 2; i <= v; i++) { // 不计第一个顶点,因为统计的是边的权值,v个节点有 v-1条边
        result += minDist[i];
    }
    cout << result << endl;

}

2、kruskal算法

Kruskal 是维护边的集合

kruscal的思路:

  • 边的权值排序,因为要优先选最小的边加入到生成树里
  • 遍历排序后的边
    • 如果边首尾的两个节点在同一个集合,说明如果连上这条边图中会出现环
    • 如果边首尾的两个节点不在同一个集合,加入到最小生成树,并把两个节点加入同一个集合

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// l,r为 边两边的节点,val为边的数值
struct Edge {
    int l, r, val;
};

// 节点数量
int n = 10001;
// 并查集标记节点关系的数组
vector<int> father(n, -1); // 节点编号是从1开始的,n要大一些

// 并查集初始化
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]); // 路径压缩
}

// 并查集的加入集合
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找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;
}

标签:val,int,father,随想录,生成,find,第五十七,打卡,节点
From: https://blog.csdn.net/m0_67804957/article/details/142183311

相关文章

  • 代码随想录训练营day44|1143.最长公共子序列,1035.不相交的线, 53. 最大子序和,392.判
    1143.最长公共子序列这题并不要求连续子序列的要求是可以删除某些元素,但不能改变顺序。顺着上题的思路,这题也应该设立一个二维数组vector<vector<int>>dp(text1.size(),vector<int>(text2.size(),0));dp[i][j]表示的是以text1[i]为结尾的字符串和以text2[j]为结尾的......
  • 代码随想录算法训练营Day1
    目录704.二分查找 27.移除元素977.有序数组的平方 704.二分查找 分类:左闭右闭、左闭右开Tips:1.循环条件:左闭右闭:左索引<=右索引左闭右开:左索引<右索引2.循环操作:处理元素>目标值:左闭右闭:右索引=折半索引-1左闭右开:右索引=折半索引classSolution{......
  • 代码随想录训练营day41|121. 买卖股票的最佳时机,122.买卖股票的最佳时机II,123.买卖股
    121.买卖股票的最佳时机这题和贪心中的买股票很想,但这里不用考虑局部问题,因为只用买一张卖一张。我想可以用一个数组dp来记录买入价格和卖出价格。然后遍历数组草我感觉我写的想贪心。动态规划dp[i][0]表示第i天不持股的最大收益,dp[i][1]表示第i天持股的最大收益。dp......
  • 【代码随想录Day13】二叉树Part01
    理论基础文章讲解:代码随想录二叉树节点的定义:publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val......
  • 代码随想录算法 - 二叉树
    题目1226.翻转二叉树给你一棵二叉树的根节点root,翻转这棵二叉树,并返回其根节点。示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]提示:树中节点数目范围在[0,100]内-100<=Node.val......
  • 代码随想录day 56 || 图论6
    Prim算法应用场景是主要是找到一个无向连通图的最小生成树,即连接所有节点且权重总和最小的树//prim三部曲//1,找到距离当前最小树最近节点//2,节点入树//3,更新mindist//更新树funcupdateMinDist(edges[][]int,nodeint){ for_,edge:=rangeedges{ ifed......
  • 代码随想录训练营第28天|利润分解
    122.买卖股票的最佳时机IIclassSolution{public:intmaxProfit(vector<int>&prices){intsum=0,day_profit;for(inti=1;i<prices.size();i++){day_profit=prices[i]-prices[i-1];if(day_profit>0)......
  • 代码随想录day 10-栈和队列2
    题目1150.逆波兰表达式求值给你一个字符串数组tokens,表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意:有效的算符为'+'、'-'、'*'和'/'。每个操作数(运算对象)都可以是一个整数或者另一个表达式。两个整数之间的除......
  • 代码随想录训练营第25天|set去重
    491.非递减子序列classSolution{public:vector<vector<int>>result;vector<int>path;voiddfs(vector<int>&nums,intstartIdx){if(startIdx==nums.size()){return;}unordered_set&......
  • 代码随想录训练营第24天|回溯过程收集
    93.复原IP地址classSolution{public:vector<vector<string>>result;vector<string>path;boolcheck(string&sub){if(sub.length()>1&&sub[0]=='0')returnfalse;try{......