【代码随想录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<>();存放每个路径的…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
