算法01-最小生成树prim算法

最小生成树prim算法
题源:代码随想录卡哥的题
链接:https://kamacoder.com/problempage.php?pid=1053
时间:2025-04-18
难度:4⭐
题目:

1. 题目描述:

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

不同岛屿之间,路途距离不同,国王希望你可以规划建公路的方案,如何可以以最短的总公路距离将所有岛屿联通起来。

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

输入描述:

第一行包含两个整数V和E,V代表顶点数,E代表边数。顶点编号是从1到V。例如:V=2,一个有两个顶点,分别是1和2。

接下来共有E行,每行三个整数v1,v2和val,v1和v2为边的起点和终点,val代表边的权值。

输出描述:

输出联通所有岛屿的最小路径总距离

输入示例:

7 11
1 2 1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1

输出示例:

6

2. 解题方法:

采用prim算法来求最小生成树的问题,使用贪心的思想,即在循环每一个顶点的过程中,寻找与当前生成树距离最近的顶点,然后将其加入进来,然后更新当前生成树到剩余顶点的最近距离。总共分为3个步骤:

  1. 寻找初始起点(这里随机即可,选择第1个)
  2. 然后判断剩余节点中与当前生成树距离最近的顶点,将其加入生成树;
  3. 更新第2步新增节点到最小生成树后,当前其他节点到最小生成树的距离。

3. 代码如下:

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);

    int v=scanner.nextInt();int e=scanner.nextInt();int[][] grid=new int[v+1][v+1];for(int i=0;i<=v;i++){Arrays.fill(grid[i],10001);}for(int i=0;i<e;i++){int a=scanner.nextInt();int b=scanner.nextInt();int c=scanner.nextInt();grid[a][b]=c;grid[b][a]=c;}int[] minDist=new int[v+1];Arrays.fill(minDist,10001);boolean[] inTree=new boolean[v+1];for(int i=1;i<v;i++){int cur=-1;int minVal=Integer.MAX_VALUE;for(int j=1;j<=v;j++){if(!inTree[j]&&minDist[j]<minVal){minVal=minDist[j];cur=j;}}inTree[cur]=true;for(int j=1;j<=v;j++){if(!inTree[j]&&grid[cur][j]<minDist[j]){minDist[j]=grid[cur][j];}}}int res=0;for(int i=2;i<=v;i++){res+=minDist[i];}System.out.println(res);}

}

4. 心得体会

算法真的好难呀,555~
有没有路过的大佬分享一下怎么学算法呀~

5. 碎碎念

东b管院本科生->东b计科水硕-> 一名热爱技术但菜菜的女生,持续前进中~
如果有技术上的问题分享,或者生活中的碎碎念,愿意多一个互联网搭子的话: dd19898852196(weiChat)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/107.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

利用deepseek+Mermaid画流程图

你是一个产品经理&#xff0c;请绘制一个流程图&#xff0c;要求生成符合Mermaid语法的代码&#xff0c;要求如下&#xff1a; 用户下载文件、上传文件、删除文件的流程过程符合安全规范细节具体到每一步要做什么 graph LRclassDef startend fill:#F5EBFF,stroke:#BE8FED,str…

stl 容器 – map

stl 容器 – map 1. map 和 multimap的使用文档 参考文档 参考文档点这里哟 &#x1f308; &#x1f618; 2. map 类的介绍 map的声明如下 template < class Key, // map::key_type class T, // map::mapped_type class Compare less<Key>, // map::key_…

计算机视觉cv2入门之车牌号码识别

前边我们已经讲解了使用cv2进行图像预处理与边缘检测等方面的知识&#xff0c;这里我们以车牌号码识别这一案例来实操一下。 大致思路 车牌号码识别的大致流程可以分为这三步&#xff1a;图像预处理-寻找车牌轮廓-车牌OCR识别 接下来我们按照这三步来进行讲解。 图像预处理 …

Spring Boot 3 + SpringDoc:打造接口文档

1、背景公司 新项目使用SpringBoot3.0以上构建&#xff0c;其中需要对外输出接口文档。接口文档一方面给到前端调试&#xff0c;另一方面给到测试使用。 2、SpringDoc 是什么&#xff1f; SpringDoc 是一个基于 Spring Boot 项目的库&#xff0c;能够自动根据项目中的配置、…

多路由器通过三层交换机互相通讯(单臂路由+静态路由+默认路由版),通过三层交换机让pc端相互通讯

多路由器通过三层交换机互相通讯&#xff08;单臂路由静态路由默认路由版&#xff09; 先实现各个小框框里能够互通 哇咔 交换机1&#xff08;二层交换机,可看配置单臂路由的文章) Switch>en Switch#conf t Switch(config)#int f0/1 Switch(config-if)#switchport access…

通过gird布局实现div的响应式分布排列

目标&#xff1a;实现对于固定宽度的div盒子在页面中自适应排布&#xff0c;并且最后一行的div盒子可以与前面的盒子对齐。 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" con…

AI Agent系列(九) -Data Agent(数据分析智能体)

AI Agent系列【九】 前言一、Data Agent场景二、Data Agent核心因素2.1 数据源2.2 大模型2.3 应用及可视化 三、Data Agent应用场景 前言 Data Agent就是在大模型基础上构建一个数据分析的智能体&#xff0c;是一种基于人工智能技术&#xff0c;特别是大模型技术的数据分析智…

AUTOSAR图解==>AUTOSAR_SWS_DefaultErrorTracer

AUTOSAR 默认错误追踪器(Default Error Tracer)详细分析 基于AUTOSAR 4.4.0规范的深入解析 目录 概述 DET模块的作用DET模块的定位 架构设计 模块架构接口设计 状态与行为 状态转换错误报告流程 API与数据结构 API概览数据类型定义 配置与扩展 模块配置回调机制 总结 1. 概述 …

Linux,redis群集模式,主从复制,读写分离

redis的群集模式 主从模式 &#xff08;单项复制&#xff0c;主复制到从&#xff09; 一主两从 一台主机上的一主两从 需要修改三个配置文件 主要端口不一样 redis-8001.conf redis-8002.conf redis-8003.conf 哨兵模式 分布式集群模式 redis 安装部署 1&#xff0c;下载…

前端面试题---GET跟POST的区别(Ajax)

GET 和 POST 是两种 HTTP 请求方式&#xff0c;它们在传输数据的方式和所需空间上有一些重要区别&#xff1a; ✅ 一句话概括&#xff1a; GET 数据放在 URL 中&#xff0c;受限较多&#xff1b;POST 数据放在请求体中&#xff0c;空间更大更安全。 &#x1f4e6; 1. 所需空间…

WPF 从Main()方法启动

1.去掉App.xaml StartupUri“MainWindow.xaml” 只会让App.g.cs 不生成这行代码&#xff0c;但是还是会生成的App.g.cs文件中生成Main方法 this.StartupUri new System.Uri("MainWindow.xaml", System.UriKind.Relative);默认的App.xaml的生成操作是 应用程序定义…

ocr-身份证正反面识别

在阿里云官网&#xff0c;申请一个token [阿里官方]身份证OCR文字识别_API专区_云市场-阿里云 (aliyun.com) 观察一下post请求body部分json字符串&#xff0c;我们根据这个创建一个java对象 先默认是人像面 public class IdentityBody {public String image;class configure…