首页 > 编程语言 >最小生成树之 Prim 算法学习笔记

最小生成树之 Prim 算法学习笔记

时间:2024-09-14 17:47:25浏览次数:11  
标签:Prim int 复杂度 笔记 ee 算法 edges nodes dis

最小生成树之 Prim 算法学习笔记

emm...在一通瞎搞奋战之后,prim被我收入囊中!

\(prim\) 的思路其实非常简单,和 \(dij\) 有一丝相似之处,可能会搞混

设最小生成树上的集合为 \(S\),所有点一开始到 \(S\) 的距离都是 \(+ \infty\)

从任意一个点开始,将其放入 \(S\) ,然后更新与这个点相邻的点到 \(S\) 的距离

再找到不在 \(S\) 中的且离 \(S\) 距离最小的点\(^{(注释1)}\),将其放入 \(S\) 然后更新与这个点相邻的点到 \(S\) 的距离

不断重复上一步直至所有的点都在 \(S\) 之中,最小生成树就这么建好了

注释1:

对于这一步有两种实现方式:

法一:直接暴力遍历所有的点 复杂度 \(O(n)\)

这样实现的话总复杂度为 \(O(n^2+m)\)

法二:用优先队列堆对结构来找 复杂度 \(O(log\ m)\)

这样的总复杂度为 \(O((n+m) \ log \ n)\)

当边数m很大时,法二的复杂度还不如暴力的法一

所以 当图为稀疏图时用法二 当图为稠密图时用法一

细节见代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge
{
    int f,t;
    int w;
};
edge edges[1000000];
struct node
{
    bool done;
    int dis=1000000000;
    vector<int > to;
};
node nodes[100000];
int ans;
priority_queue<pair<int,int> ,vector<pair<int,int> > ,greater<pair<int,int> > > q;

int prim()
{
    q.push({0,1});
    pair<int ,int > now_;
    int the_bian,the_dis,to_;
    int tot_dis=0,had_chosen=0;
    while(!q.empty())
    {
        now_=q.top();
        q.pop();

        the_bian=now_.second;
        the_dis=now_.first;
        if(nodes[the_bian].done==0)//如果不在S中
        {
            nodes[the_bian].done=1;
            tot_dis+=the_dis;
            had_chosen++;
        
            for(int yy=0;yy<nodes[the_bian].to.size();yy++)//遍历所有出边
            {
                to_=edges[nodes[the_bian].to[yy]].t;
                if(nodes[to_].done==0)
                {
                    if(edges[nodes[the_bian].to[yy]].w<nodes[to_].dis)//如果距离比之前的进,则更新,入队
                    {
                        nodes[to_].dis=edges[nodes[the_bian].to[yy]].w;//更新距离
                        q.push({nodes[to_].dis,to_});//入队
                    }
                }
            }
        }
        else
        {
            continue;
        }
    }  
    if(had_chosen<n)
    {
        return -99999;
    }  
    else
    {
        return tot_dis;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int a,b,c;
    for(int ee=1;ee<=m;ee++)
    {
        cin>>a>>b>>c;//建边
        edges[ee].f=a;
        edges[ee].t=b;
        edges[ee].w=c;
        edges[ee+m].f=b;
        edges[ee+m].t=a;
        edges[ee+m].w=c;
        nodes[a].to.push_back(ee);
        nodes[b].to.push_back(ee+m);
    }
    ans=prim();
    if(ans==-99999)
    {
        cout<<"orz";
    }
    else
    {
        cout<<ans;
    }


    return 0;
}
//prim

标签:Prim,int,复杂度,笔记,ee,算法,edges,nodes,dis
From: https://www.cnblogs.com/sea-and-sky/p/18414455

相关文章

  • self-play RL学习笔记
    让AI用随机的路径尝试新的任务,如果效果超预期,那就更新神经网络的权重,使得AI记住多使用这个成功的事件,再开始下一次的尝试。——llyaSutskever这两天炸裂朋友圈的OpenAI草莓大模型o1和此前代码能力大幅升级的Claude3.5,业内都猜测经过了自博弈强化学习(self-playRL)。1......
  • cpp primer plus 第七章
    7.1函数基本知识7.1.1定义函数函数分为两类:有返回值与无返回值的函数。对于有返回值的函数,必须使用返回语句,将值返回给调用函数。若函数包含多条返回语句,则函数在执行第一条返回语句后结束。7.1.2函数原型声明函数如果在main函数后方,则在前面声明函数(复制函数定义中的......
  • 深度学习YOLO人员抽烟AI检测算法在智慧安防领域的创新应用
    随着人工智能技术的飞速发展,计算机视觉和深度学习算法在各个领域的应用日益广泛。其中,人员抽烟AI检测算法以其高效、精准的特点,成为公共场所、工厂、学校等场景中的得力助手。本文将介绍TSINGSEE青犀AI智能分析网关V4人员抽烟检测算法的基本原理、实现步骤以及其在多个实际场景......
  • 3ds Max 2018 进阶快捷键操作笔记
    1.视图与界面控制Alt+W:切换当前视口最大化。工作时常需要在多个视口之间切换,该快捷键帮助快速专注于某一视口细节。F3:切换线框模式与实体模式。方便随时观察模型的结构和表面,特别是在检查复杂几何形状时非常有用。F4:显示网格边缘。在实体模式下显示线框,常用于优化模型的......
  • 火焰检测算法、明烟明火检测、烟火检测算法
    烟火检测算法主要用于火灾早期预警系统中,能够在火灾初期阶段及时发现烟雾或火焰,从而快速响应并采取行动,以减少火灾带来的损失。以下是对烟火检测算法的应用场景及优势的详细介绍。烟火检测算法广泛应用于多种场景中,以下是一些典型的应用实例:1.公共安全监控-楼宇监控:在办公楼、......
  • 精准识别,高效管理:工服识别AI检测算法在多场景中的应用优势
    随着人工智能技术的快速发展,其在各个行业的应用也日益广泛。特别是在工业生产和安全监管领域,工服识别AI检测算法凭借其高效、精准的特点,成为提升生产效率、保障工作人员安全的重要手段。本文将详细介绍TSINGSEE青犀AI智能分析网关V4工服识别算法的基本原理、技术实现以及其在多个......
  • 人员抽烟AI检测算法在智慧安防领域的创新应用,助力监控智能化
    随着人工智能技术的飞速发展,计算机视觉和深度学习算法在各个领域的应用日益广泛。其中,人员抽烟AI检测算法以其高效、精准的特点,成为公共场所、工厂、学校等场景中的得力助手。本文将介绍TSINGSEE青犀AI智能分析网关V4人员抽烟检测算法的基本原理、实现步骤以及其在多个实际场景中......
  • 天梯赛(常用STL函数)+ 常见算法
    0.(森森美图)判断一个点x3,y3在一条直线(由x1,y1和x2,y2组成)的哪一边若(y2-y3)/(x2-x3)-(y1-y3)/(x1-x3)>0逆时针方向否则顺时针方向1.vectorvector<node>ve;//定义ve.insert(ve.begin()+i,k);//中间插入ve.insert(ve.begin()+i,num,key);ve.erase(ve.begin()+i);//删......
  • 《垃圾回收的算法与实现》-算法-摘抄
    本文是书籍《垃圾回收的算法与实现》的摘抄,不涉及算法源码及步骤讲解模块。预备对象由头(header)和域(field)构成。头:对象中保存对象本身信息的部分,主要含有以下信息:对象的大小和种类。域:对象使用者在对象中可访问的部分,数据类型有指针、非指针;指针是指向内存空间中某块区域的值;非......
  • 数据结构与算法-求数的最小深度是多少?
    给定一颗二叉树的头节点head求以head为头的树中,最小深度是多少?publicclassMinHeight{publicstaticclassTreeNode{publicintval;publicTreeNodeleft;publicTreeNoderight;publicTreeNode(intx){val=x;......