【代码随想录Day55】图论Part07
prim 算法精讲
题目链接/文章讲解:代码随想录
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取顶点数和边数int vertexCount = scanner.nextInt();int edgeCount = scanner.nextInt();// 初始化邻接矩阵,所有值初始化为一个大值,表示无穷大int[][] adjacencyMatrix = new int[vertexCount + 1][vertexCount + 1];for (int i = 0; i <= vertexCount; i++) {Arrays.fill(adjacencyMatrix[i], Integer.MAX_VALUE);}// 读取边的信息并填充邻接矩阵for (int i = 0; i < edgeCount; i++) {int startVertex = scanner.nextInt();int endVertex = scanner.nextInt();int weight = scanner.nextInt();adjacencyMatrix[startVertex][endVertex] = weight;adjacencyMatrix[endVertex][startVertex] = weight; // 无向图}// 距离数组,记录每个节点到生成树的最小距离int[] minimumDistances = new int[vertexCount + 1];Arrays.fill(minimumDistances, Integer.MAX_VALUE);// 记录节点是否在生成树中boolean[] isInMST = new boolean[vertexCount + 1];// Prim算法主循环minimumDistances[1] = 0; // 从第一个节点开始for (int i = 1; i < vertexCount; i++) {int closestVertex = -1;int smallestDistance = Integer.MAX_VALUE;// 选择距离生成树最近的节点for (int j = 1; j <= vertexCount; j++) {if (!isInMST[j] && minimumDistances[j] < smallestDistance) {smallestDistance = minimumDistances[j];closestVertex = j;}}// 将最近的节点加入生成树isInMST[closestVertex] = true;// 更新非生成树节点到生成树的距离for (int j = 1; j <= vertexCount; j++) {if (!isInMST[j] && adjacencyMatrix[closestVertex][j] < minimumDistances[j]) {minimumDistances[j] = adjacencyMatrix[closestVertex][j];}}}// 统计生成树的总权重int totalWeight = 0;for (int i = 2; i <= vertexCount; i++) {totalWeight += minimumDistances[i];}// 输出结果System.out.println(totalWeight);scanner.close();}
}
kruskal 算法精讲
题目链接/文章讲解:代码随想录
import java.util.*;class Edge {int vertex1, vertex2, weight;// Edge构造函数,初始化边的两个顶点和权重Edge(int vertex1, int vertex2, int weight) {this.vertex1 = vertex1;this.vertex2 = vertex2;this.weight = weight;}
}public class Main {private static final int MAX_NODES = 10001; // 最大节点数private static int[] parent = new int[MAX_NODES]; // 存储每个节点的父节点// 初始化并查集public static void initializeUnionFind() {for (int i = 0; i < MAX_NODES; i++) {parent[i] = i; // 每个节点的父节点初始化为自身}}// 查找操作,寻找节点的根节点public static int find(int node) {if (node == parent[node]) {return node; // 如果节点是根节点,直接返回}// 路径压缩,优化查找效率return parent[node] = find(parent[node]);}// 合并两个集合public static void union(int node1, int node2) {int root1 = find(node1);int root2 = find(node2);if (root1 != root2) {parent[root2] = root1; // 将一个集合的根节点指向另一个集合的根节点}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int vertexCount = scanner.nextInt(); // 顶点数量int edgeCount = scanner.nextInt(); // 边的数量List<Edge> edgeList = new ArrayList<>(); // 存储所有边int totalWeight = 0; // 最小生成树的权重总和// 读取边的信息for (int i = 0; i < edgeCount; i++) {int vertex1 = scanner.nextInt();int vertex2 = scanner.nextInt();int weight = scanner.nextInt();edgeList.add(new Edge(vertex1, vertex2, weight)); // 添加边到边列表}// 按照边的权重进行排序edgeList.sort(Comparator.comparingInt(edge -> edge.weight));// 初始化并查集initializeUnionFind();// 遍历所有边,执行Kruskal算法for (Edge edge : edgeList) {int root1 = find(edge.vertex1);int root2 = find(edge.vertex2);// 如果两个顶点的根节点不同,说明它们不在同一个集合if (root1 != root2) {totalWeight += edge.weight; // 加入当前边的权重union(root1, root2); // 合并两个集合}}// 输出最小生成树的权重总和System.out.println(totalWeight);scanner.close(); // 关闭扫描器}
}
相关文章:
【代码随想录Day55】图论Part07
prim 算法精讲 题目链接/文章讲解:代码随想录 import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 读取顶点数和边数int vertexCount scanner.nextInt();int edgeCount scanner.nextI…...
软考在即!这些注意事项你提前了解!
11月软考马上就要开始了,但是,还有很多的考生,可能还不知道自己到底应该去了解些什么?本文将详细介绍机考注意事项及系统操作提示,帮助考生们备考无忧。 一、考试入场要求和考场规则 1、入场时间:考生需提…...
CMake知识点
参考: https://zhuanlan.zhihu.com/p/661284252 cmake使用教程(实操版)-CSDN博客 【CMake】CMake从入门到实战系列(二)——实例入手,讲解CMake的基本流程_cmake创建一个可执行目标的过程-CSDN博客 一、…...
git ls-remote
文章目录 1.简介2.格式3.选项4.示例5.小结参考文献 1.简介 git ls-remote 是一个 Git 命令,用于列出远程 Git 仓库的引用(refs),包括分支、标签等。 这个命令非常有用,可以帮助你查看远程仓库中可用的分支和标签&…...
低代码平台如何通过AI赋能,实现更智能的业务自动化?
引言 随着数字化转型的加速推进,企业在日常运营中面临的业务复杂性与日俱增。如何快速响应市场需求,优化流程,并降低开发成本,成为各行业共同关注的核心问题。低代码平台作为一种能够快速构建应用程序的工具,因其可视化…...
计算疫情扩散时间
该专栏题目包含两部分: 100 分值部分题目 200 分值部分题目 所有题目都会陆续更新,订阅防丢失 题目描述 在一个地图中(地图由 N ∗ N N*N N∗N 个区域组成),有部分区域被感染病菌。 感染区域每天都会把周围(上下左右)的4个区域感染。 请…...
【Windows11】24H2 内存占用高(截至10月31日)
文章目录 一、问题二、解决三、原因 一、问题 系统版本: 内存只有32GB。 以前只有我在运行数据处理程序的时候内存占用才会很高,日常情况下应该只有40%、50%左右的。 但是24H2,日常情况下内存占用80%以上。 而我只开了很少的应用&#…...
题目:多个字符从两端移动,向中间汇聚
【多个字符从两端移动,向中间汇聚】 char arr1[] "Good Good Study,Day Day Up!" ; char arr2[] "***************************"; 【思路】 首先两字符串中的元素个数要相同,将两串字符分别存放在数组中,那么字符串中…...
前端如何安全存储密钥,防止信息泄露
场景 把公钥硬编码在前端代码文件里,被公司安全检测到了要整改,于是整理几种常见的前端密钥存储方案。 1. 设置环境变量再读取 在打包或部署前端应用时,可以将密钥配置为环境变量,在应用运行时通过环境变量读取密钥。这样可以将密…...
银行电子户分账解决电商行业哪些问题
随着电子商务的快速发展,电商银行电子户分账作为金融科技领域的重要一环,逐渐成为现代金融业务的核心。本文将详细探讨电商银行电子户分账的原理、操作流程、安全措施以及在电子商务中的重要作用。 二、电商银行电子户分账的基本概念 电商银行电子户分…...
Web音乐库:SpringBoot实现的音乐网站
2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统,它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等,非常…...
Rust: 加密算法库 ring 如何用于 RSA 数字签名?
本来用 rsa 库基本搞定,但文心一言建议改用 ring 库。原因是 rsa 库已经放弃维护,而 ring 库性能公认很好。但是如何进行 RSA 数字签名,网上几乎查不到这方面材料。仔细查看了 ring 库的源代码和代码注释,终于完成趟坑。总结一下供…...
Matplotlib 网格线
Matplotlib 网格线 Matplotlib 是一个强大的 Python 绘图库,广泛用于数据可视化。在 Matplotlib 中,网格线是一种常用的辅助工具,用于增强图表的可读性和美观性。本文将详细介绍如何在 Matplotlib 中添加和使用网格线。 1. 简介 网格线是在…...
钉钉机器人禅道消息通知@指派人
钉钉、禅道怎么设置webhook? 点击查看:获取自定义机器人 Webhook 地址 在禅道上配置钉钉机器人webhook,使用管理员账号登录,找到通知设置 添加webhook 添加webhook所需要的数据即可 webhook设置,根据自己的实际…...
我的新书出版啦!和大家聊聊写书的酸甜苦辣
我的新书出版啦!小伙伴们问是不是赚翻了? 大家好,我是码哥。我的新书《Redis 高手心法》出版后(2024 年 8 月份出版),有一些小伙伴问了我一些问题: 写书是不是赚了很多钱?我也想写…...
【福建医科大学附属第一医院-注册安全分析报告】
前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 暴力破解密码,造成用户信息泄露短信盗刷的安全问题,影响业务及导致用户投诉带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞 …...
第二届新生程序设计竞赛热身赛(C语言)
A:饥饿的XP XP迷失在X星球,他醒来时已经很久很久很久没有吃过东西了。他突然发现身边有一张地图,上面有X星球上每一个食物供给点的位置。太好了,XP跳了起来。他决定先把肚子填饱再去寻找其他伙伴。现在已知XP的位置(X, Y),以及他的…...
WebSocket和HTTP请求的区别
1. 连接方式 HTTP请求:基于“请求-响应”模式。每次通信都要重新建立连接,客户端发送请求后服务器返回响应,连接就断开了。这种模式通常适合不频繁更新的数据,如静态页面的加载。WebSocket:支持长连接,连接…...
【Python · Pytorch】人工神经网络 ANN(中)
【Python Pytorch】人工神经网络 ANN(中) 6. 反向传播6.1 梯度下降法6.1.1 线搜索方法6.1.2 微分 & 导数6.1.3 偏导数6.1.4 Jacobian矩阵6.1.5 梯度 & 梯度下降法按维度介绍 6.1.6 面临挑战平原现象 & 振荡现象局部最小值鞍点梯度消失梯度爆…...
穷举vs暴搜vs深搜vs回溯vs剪枝 算法专题
一. 全排列 全排列 class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permute(int[] nums) {ret new ArrayList<>();//存放结果path new ArrayList<>();存放每个路径的…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...
