首页 > 其他分享 >图的最小生成树

图的最小生成树

时间:2024-11-06 21:32:46浏览次数:3  
标签:vector int 最小 len 生成 ++ points 节点

连接所有点的最小费用

Kruskal(并查集)

数据结构

并查集储存区分节点状态:未访问 or 已访问
边集:根据权重排序

算法思想

每次把权重最小的边的节点标记已访问(加入集合)

//并查集
class joinSet{
private:
    vector<int> f, rank;
    int n;
public:
    joinSet(int _n){
        n = _n;
        f.resize(n);
        for(int i = 0; i < n; i++){
            f[i] = i;
        }
        rank.resize(n, 1);
    }
    //查找
    int find(int x){
        return x == f[x] ? x : f[x] = find(f[x]);
    }
    //加入新元素
    bool join(int x, int y){
        int fx = find(x), fy = find(y);

        if (fx == fy) return false;
        //按秩优化
        if(rank[fx] > rank[fy]){
            swap(fx, fy);
        }
        rank[fy] += rank[fx];
        //元素加入
        f[fx] = fy;
        return true;
    }
};
//边
struct Edge{
    int len, x, y;
    Edge(int len, int x, int y):len(len), x(x), y(y){}
};

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        //距离函数
        function<int(int, int)> dis = [&](int x, int y) -> int{
            return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
        };
        
        //边读入
        int n = points.size();
        vector<Edge> edges;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                edges.emplace_back(dis(i, j), i, j);
            }
        }

        //根据权重排序
        sort(edges.begin(), edges.end(), [&](Edge a, Edge b)->int{return a.len < b.len;});

        //根据权重逐条边加入
        int ans = 0, count = 1;
        joinSet js(n);
        for(auto& [len, x, y] : edges){
            if(js.join(x, y)){
                ans += len;
                count++;

                if(count == n){
                    break;
                }
            }
        }
        return ans;
    }
};  

Prim算法

数据结构

1.两个容器VlowerCost

V根据下标标识一个节点是否已经被访问。

lowerCost记录未访问节点集已访问节点集的最近节点距离。这个地方有弯,他记录的是节点集节点集之间最近距离(在不同情境中“最近距离”的概念不同),只有遇到更小距离才会对应更新。

算法思想

每次循环将未访问节点集中的一个最近节点加入已访问节点集

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int ans = 0;
        //建距离图
        int n = points.size();
        vector<vector<int>> grid(n, vector<int>(n));
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                int distance = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                grid[i][j] = grid[j][i] =  distance;           
            }
        }
        //两个容器
        vector<int> lowerCost(n);
        vector<int> visited(n);

        //初始化,0加入Vnew
        visited[0] = 1;
        for(int i = 0; i < n; i++){
            if(i == 0)  continue;
            lowerCost[i] = grid[0][i];
        }
        //Prim算法
        for(int _ = 1; _ < n; _++){
            int minIndx = -1;
            int minVal = INT_MAX;
            //找V最近点
            for(int j = 0; j < n; j++){
                if(visited[j] == 0 && lowerCost[j] < minVal){
                    minIndx = j;
                    minVal = lowerCost[j];
                }
            }
            ans += minVal;
            visited[minIndx] = 1;

            //更新V与Vnew的最小距离容器
            for(int i = 0; i < n; i++){
                if(visited[i] == 0 && grid[i][minIndx] < lowerCost[i]){
                    lowerCost[i] = grid[i][minIndx];
                }
            }
        }

        return ans;
    }
};  

标签:vector,int,最小,len,生成,++,points,节点
From: https://www.cnblogs.com/LuvLetter-whx/p/18530667

相关文章

  • 代码随想录算法训练营第十八天|leetcode530.二叉搜索树的最小绝对差、leetcode501.二
    1leetcode530.二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)文章链接:代码随想录视频链接:你对二叉搜索树了解的还不够!|LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili思路:定义一个极大值作为结果,然后在中序遍历过程中进行比较出结果1.1自己的......
  • Python学习笔记-生成器的应用与原理
    生成器是Python中一种特殊的迭代工具,通过延迟计算的方式来逐步生成序列中的元素。这种特性使得生成器在处理大数据、无限序列或需要惰性求值的场景中十分有效。生成器的核心思想是通过yield语句逐步返回值,暂停并保留当前状态,直到下次调用继续执行,从而节省内存并优化性能......
  • AIGC:人工智能生成内容的未来
    文章目录一、AIGC的定义与背景1.1AIGC的起源与发展1.2AIGC的核心技术二、AIGC的核心技术解析2.1生成对抗网络(GANs)2.2变分自编码器(VAEs)2.3自然语言处理(NLP)与文本生成三、AIGC的应用场景四、AIGC的挑战与未来趋势总结:引言随着人工智能技术的飞速发展,尤其是在......
  • 0基础学Python——类的单例模式、反射函数、记录类的创建个数、迭代器、生成器及生成
    0基础学Python——类的单例模式、反射函数、记录类的创建个数、迭代器、生成器及生成器练习类的单例模式定义代码演示反射函数代码演示记录类的创建个数迭代器定义特点生成器定义特点写法生成器练习生成器生成1-无穷的数字生成器生成无穷个素数类的单例模式定义......
  • TPAMI 2024 | NICEST:用于鲁棒场景图生成的噪声标签修正与训练
    题目:NICEST:NoisyLabelCorrectionandTrainingforRobustSceneGraphGenerationNICEST:用于鲁棒场景图生成的噪声标签修正与训练作者:LinLi;JunXiao;HanrongShi;HanwangZhang;YiYang;WeiLiu;LongChen摘要几乎所有现有的场景图生成(SGG)模型都忽视......
  • AI-Prompt、RAG、微调还是重新训练?选择正确的生成式AI的使用方法
    生成式人工智能正在快速发展,许多人正在尝试使用这项技术来解决他们的业务问题。一般情况下有4种常见的使用方法:PromptEngineeringRetrievalAugmentedGeneration(RAG检索增强生成)微调从头开始训练基础模型(FM)本文将试图根据一些常见的可量化指标,为选择正确的生......
  • 2025 - 全网最牛的生物信息学分析 - 一键式生成DIFF_GSEA_WGCNA_GO_KEGG_DO
    2025-全网最牛的生物信息学分析-一键式生成DIFF_GSEA_WGCNA_GO_KEGG_DO先给你炫一下图直接上代码setwd("/Users/wangyang/Desktop/BCBM/02DIFF_GSEA_WGCNA")#引用包library(ggplot2)library(limma)library(pheatmap)library(ggsci)library(dplyr)lappl......
  • 如何使用程序生成一个复杂的2D迷宫游戏地图
    相关:ISolvedTheWorld'sHardestMaze(withCode)本文不做过多的内容介绍,本文主要是分享上面的这个视频内容,该内容介绍了一些自动生成复杂2D迷宫的算法,当然本文不对此做过多介绍,这里可以当作是一个内容收藏的功能,因为曾经有段时间自己想去写这么一个迷宫生成的算法,后来发现......
  • 零基础学习Spring AI Java AI使用向量数据库postgresql 检索增强生成 RAG
    零基础学习SpringAIJavaAI使用向量数据库postgresql检索增强生成RAG向量数据库是一种特殊类型的数据库,在人工智能应用中发挥着至关重要的作用。在向量数据库中,查询与传统的关系数据库不同。它们不是进行精确匹配,而是执行相似性搜索。当给定一个向量作为查询时,向量数......
  • 代码随想录算法训练营第十四天|leetcode226. 翻转二叉树、leetcode101.对称二叉树、le
    1leetcode226.翻转二叉树题目链接:226.翻转二叉树-力扣(LeetCode)文章链接:代码随想录视频链接:听说一位巨佬面Google被拒了,因为没写出翻转二叉树|LeetCode:226.翻转二叉树哔哩哔哩bilibili自己的思路:之前想过就是使用层序遍历的方法来做这一道题目,后来感觉有一些行不通,就......