当前位置：首页 > news >正文

贪心算法：最小生成树

news 来源：原创 2025/7/13 8:34:56

假设无向图为：

A-B:1

A-C:3

B-C:1

B-D:4

C-D:1

C-E:5

D-E:6

一、使用Prim算法：

public class Prim {//声明了两个静态常量，用于辅助 Prim 算法的实现private static final int V = 5;//点数private static final int INF = Integer.MAX_VALUE;//若直接使用 0 表示无边，会与边权为 0 的情况冲突。而 Integer.MAX_VALUE 是一个极大的值，在比较边权时不会被误认为有效边权。public static void main(String[] args){int [][] graph = new int[][]{{0, 1, 3, 0, 0},{1, 0, 1, 4, 0},{3, 1, 0, 1, 5},{0, 4, 1, 0, 6},{0, 0, 5, 6, 0}};//用二维数组表示无向图primMST(graph);}private static void primMST(int[][] graph) {int[] parent = new int[V];//记录每个结点的父节点int[] key = new int[V];//记录每个结点当前最小边权boolean[] mstSet = new boolean[V];//标记顶点是否已被加入MSTfor(int i =0;i<V;i++){key[i] = INF;mstSet[i] = false;}//初始化key[0] = 0;parent[0] = -1;//初始化for(int count =0;count<V-1;count++){int u = minKey(key,mstSet);//从未加入 MST 的顶点中选择 key 值最小的顶点 umstSet[u] = true;//将 u 加入 MST
//遍历所有与 u 相邻的顶点 v：
//如果 v 未被加入 MST 且边 (u, v) 的权值小于 v 的当前 key，则更新 v 的 key 和 parent。for(int v=0;v<V;v++){if(graph[u][v] != 0&&mstSet[v]==false&&graph[u][v] < key[v]){parent[v] = u;key[v] = graph[u][v];}}}printMST(parent,graph);}
//打印结果private static void printMST(int[] parent, int[][] graph) {System.out.println("Edge \tWeight");for (int i = 1; i < V; i++) {System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);}}private static int minKey(int[] key, boolean[] mstSet) {int min = INF,minIndex = -1;//初始化for(int v = 0;v<V;v++){if(mstSet[v]==false && key[v]<min){min = key [v];minIndex = v;}}return minIndex;}}

二、使用Kruskal算法：

import java.util.*;public class Kruskal{private static final int V = 5; // Number of vertices in the graphprivate Edge[] edges; // 存储所有边，包含三个成员变量：src（源顶点）、dest（目标顶点）和 weight（边的权重）。private int edgeCount = 0; // 边的数量class Edge implements Comparable<Edge> {int src, dest, weight;public int compareTo(Edge compareEdge) {return this.weight - compareEdge.weight;}}
//用于实现并查集class subset {//用于跟踪每个顶点的父节点和秩int parent, rank;}
//查找顶点 i 的根节点，并实现路径压缩int find(subset[] subsets, int i) {if (subsets[i].parent != i) {subsets[i].parent = find(subsets, subsets[i].parent);}return subsets[i].parent;}
//合并两个子集，使用秩来保持树的平衡void Union(subset[] subsets, int x, int y) {int xroot = find(subsets, x);int yroot = find(subsets, y);if (subsets[xroot].rank < subsets[yroot].rank) {subsets[xroot].parent = yroot;} else if (subsets[xroot].rank > subsets[yroot].rank) {subsets[yroot].parent = xroot;} else {subsets[yroot].parent = xroot;subsets[xroot].rank++;}}public static void main(String[] args) {int[][] graph = new int[][]{{0, 1, 3, 0, 0},{1, 0, 1, 4, 0},{3, 1, 0, 1, 5},{0, 4, 1, 0, 6},{0, 0, 5, 6, 0}};Kruskal kruskal = new Kruskal();kruskal.kruskalMST(graph);}void kruskalMST(int[][] graph) {// 计算边的数量并初始化edges数组int edgeCount = 0;//初始化for (int i = 0; i < V; i++) {for (int j = i + 1; j < V; j++) {if (graph[i][j] != 0) {edgeCount++;}}}edges = new Edge[edgeCount];edgeCount = 0;// 初始化边数组for (int i = 0; i < V; i++) {for (int j = i + 1; j < V; j++) {if (graph[i][j] != 0) {edges[edgeCount] = new Edge();edges[edgeCount].src = i;edges[edgeCount].dest = j;edges[edgeCount].weight = graph[i][j];edgeCount++;}}}// 步骤1: 按权重升序排列边Arrays.sort(edges);// 步骤2: 初始化子集subset[] subsets = new subset[V];for (int i = 0; i < V; i++) {subsets[i] = new subset();subsets[i].parent = i;subsets[i].rank = 0;}// 步骤3: 用于存储MST的边Edge[] result = new Edge[V - 1];int e = 0; // 结果数组的索引int i = 0; // 排序后边的索引// 步骤4: 遍历每条边并添加到MST中(如果不形成环)while (e < V - 1 && i < edges.length) {Edge next_edge = edges[i++];int x = find(subsets, next_edge.src);int y = find(subsets, next_edge.dest);if (x != y) {result[e++] = next_edge;Union(subsets, x, y);}}// 输出结果System.out.println("Following are the edges in the constructed MST");for (i = 0; i < e; i++) {System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);}}
}

贪心算法：最小生成树

假设无向图为： A-B:1 A-C:3 B-C:1 B-D:4 C-D:1 C-E:5 D-E:6 一、使用Prim算法： public class Prim {//声明了两个静态常量，用于辅助 Prim 算法的实现private static final int V 5;//点数private static final int INF Integer.MA…...

编程日记 2025/7/13 8:34:56

免费 OCR 识别 + 批量处理！PDF 工具提升办公效率

各位办公小能手们！今天给你们介绍一款超厉害的软件——PDF工具V2.2！我跟你们说，这玩意儿就像是PDF界的超级英雄，专门搞定PDF文件的编辑、转换、压缩这些事儿。先说说它的核心功能哈。基础文档管理方面，它能把好几个PD…...

编程日记 2025/7/13 8:31:07

尼康VR镜头防抖模式NORMAL和ACTIVE的区别（私人笔记）

1. NORMAL 模式（常规模式） 适用场景：一般手持拍摄，比如人像、静物、风景或缓慢平移镜头（如水平追拍）等。工作特性： 补偿手抖引起的小幅度震动（比如手持时自然的不稳）&am…...

编程日记 2025/6/29 0:44:01

在scala中sparkSQL读入csv文件

以下是 Scala 中使用 Spark SQL 读取 CSV 文件的核心步骤和代码示例（纯文本）： 1. 创建 SparkSession scala import org.apache.spark.sql.SparkSession val spark SparkSession.builder() .appName("Spark SQL Read CSV") …...

编程日记 2025/7/13 8:30:24

swift flask python ipad当电脑键盘实现osu x键和z键长按逻辑有问题 quart 11毫秒

键盘不行我5星都打不过，磁轴不在身边 127.0.0.1不行要用192.168哪个地址 from flask import Flask from pynput.keyboard import Controller from threading import Threadapp Flask(__name__) keyboard Controller()# 按下按键 app.route("/press_down/<…...

编程日记 2025/7/13 8:32:31

浅论3DGS溅射模型在VR眼镜上的应用

摆烂仙君小课堂开课了，本期将介绍如何手搓VR眼镜，并将随手拍的电影变成3D视频。一、3DGS模型介绍 3D 高斯模型是基于高斯函数构建的用于描述三维空间中数据分布概率的模型，高斯函数在数学和物理领域有着广泛应用，其在 3D 情境下…...

编程日记 2025/7/13 8:32:30

React状态管理-对state进行保留和重置

相同位置的相同组件会使得 state 被保留下来当你勾选或清空复选框的时候，计数器 state 并没有被重置。不管 isFancy 是 true 还是 false，根组件 App 返回的 div 的第一个子组件都是 <Counter />： 你可能以为当你勾选复选框的时候 st…...

编程日记 2025/7/13 8:31:06

嵌入式STM32学习——外部中断EXTI与NVIC的基础练习⭐

按键控制LED灯按键控制LED的开发流程： 第一步：使能功能复用时钟第二布，配置复用寄存器第三步，配置中断屏蔽寄存器固件库按键控制LED灯外部中断EXTI结构体：typedef struct{uint32_t EXTI_Line; …...

编程日记 2025/6/29 0:50:37

git merge和git rebase

git merge和git rebase 在Git中merge和rebase都是git在管理整合分支的两种主要工具，但是他们的工作方式、提交历史影响和使用场景不同。 git merge 定义将两个分支的提交历史合并，创建一个新的合并提交（merge commit）&#xff…...

编程日记 2025/6/29 1:02:20

我的MCP相关配置记录

1.VSCode的Cline中的MCP {"mcpServers": {"github.com/modelcontextprotocol/servers/tree/main/src/github": {"autoApprove": [],"disabled": false,"timeout": 60,"command": "cmd","args&quo…...

编程日记 2025/7/6 14:21:56

浅聊一下数据库的索引优化

背景这里的索引说的是关系数据库（MSSQL）中的索引。本篇不是纯技术性的内容，只是聊一次性能调优的经历，包含到一些粗浅的实现和验证手段，所以，大神忽略即可。额…对了，笔者对数据库的优化手段…...

编程日记 2025/6/29 1:12:07

如何创建maven项目

1.IDEA 中创建 Maven 项目步骤一：点击 File -> New -> Project，在弹出的窗口左侧选择 Maven，点击 Next： 步骤二：填写项目的 GroupId、ArtifactId、Version 等信息（这些对应 pom.xml 中的关键配置&am…...

编程日记 2025/7/13 8:30:24

LORA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS

一、引言在自然语言处理领域，大规模预训练语言模型（LLMs）展现出强大的语言理解和生成能力。然而，将这些模型适配到多个下游任务时，传统微调方法面临诸多挑战。LoRA（Low-Rank Adaptation of Large Language Models）作为一种创新的微调技术，旨在解决这些问题，为大语言…...

编程日记 2025/7/13 7:37:37

Conda在powershell终端中无法使用conda activate命令

主要有以下原因： Windows PowerShell安全策略：默认情况下，PowerShell的执行策略设置为"Restricted"，这会阻止运行脚本，包括conda的初始化脚本。调用方式不同：在PowerShell中，需要使用…...

编程日记 2025/7/13 8:33:56

MySQL索引底层数据结构与算法

1、索引的数据结构 1.1、二叉树 1.2、红黑树(二叉平衡树） 1.3、hash表对key进行一次hash计算就可以定位出数据存储的位置问题：hash冲突问题、仅满足和in的查找，不支持范围查找 1.4、B-tree 1.5、B tree 非叶子节点不存储data&…...

编程日记 2025/6/29 0:36:02

GOOSE 控制块参数gocbRef及goID有大小写要求

在 IEC 61850 标准中，GOOSE 控制块参数gocbRef和goID的大小写是严格区分的。这一结论基于以下多维度分析： 一、标准协议与配置文件的强制性 XML 语法的刚性约束 GOOSE 控制块的配置信息通过 SCL（Substation Configuration Language&#xff…...

编程日记 2025/7/4 9:16:44

重庆医科大学附属第二医院外科楼外挡墙自动化监测

1.项目概述重庆医科大学附属第二医院，重医附二院，是集医疗、教学、科研、预防保健为一体的国家三级甲等综合医院。前身为始建于1892年的“重庆宽仁医院”。医院现有开放床位 1380张，年门诊量超过百万人次，年收治住院病人4.5万人…...

编程日记 2025/7/13 8:26:22

3.4 数字特征

本章系统讲解随机变量的数字特征理论，涵盖期望、方差、协方差与相关系数的核心计算与性质。以下从四个核心考点系统梳理知识体系： 考点一：期望（数学期望） 1. 离散型随机变量的数学期望一维情形： E ( X …...

编程日记 2025/6/29 0:45:42

servlet-api

本次内容总结 1、再次学习Servlet的初始化方法 2、学习Servlet中的ServletContext和<context-param> 3、什么是业务层 4、IOC 5、过滤器 7、TransActionManager、ThreadLocal、OpenSessionInViewFilter 1、再次学习Servlet的初始化方法 1）Servlet生命周期&…...

编程日记 2025/6/29 0:23:01

NLTK进行文本分类和词性标注

《python ⾃然语⾔处理实战》学习笔记 NLTK 下载依赖 !pip install nltkimport nltk nltk.download(punkt_tab)分词(tokenize) from nltk.tokenize import word_tokenize from nltk.text import Textinput_str """Twinkle, twinkle, little star, How I won…...

编程日记 2025/6/28 23:09:17

电机控制储备知识学习（一）电机驱动的本质分析以及与磁相关的使用场景

目录电机控制储备知识学习（一）一、电机驱动的本质分析以及与磁相关的使用场景1）电机为什么能够旋转2）电磁原理的学习重要性二、电磁学理论知识1）磁场基础知识2）反电动势的公式推导附学习参考网址欢迎大家…...

编程日记 2025/6/29 0:54:46

华三路由器单臂路由配置

目录 1.实验目的1.1 掌握华三路由器单臂路由配置方法2.1 路由器连接交换机，交换机划分多个 VLAN，不同 VLAN 的 PC 通过路由器实现通信配置步骤与命令解析1.配置交换机2.配置路由器验证配置3.1 配置交换机 VLAN3.1.1 创建 VLAN3.1.2 配置端口所属 VLAN3.…...

编程日记 2025/7/13 8:31:52

一键转换上百文件 Word 批量转 PDF 软件批量工具

各位办公族们，你们有没有被手动把Word一个个转成PDF给折腾得欲哭无泪过啊？我之前就因为这事忙得晕头转向，眼睛都快看瞎了！不过呢，后来我发现了专门为咱提升办公效率设计的Word批量转PDF软件，那简直就是办公…...

编程日记 2025/7/13 8:31:07

矫平机：工业精密矫正的全维度解析

作为现代制造业的核心设备之一，矫平机通过消除材料残余应力、提升平整度，持续推动着汽车、航空航天、新能源等领域的质量升级。本文基于最新行业动态与技术突破，从原理革新到智能化实践展开深度解析。一、核心原理：力学与智能的深…...

编程日记 2025/6/28 23:05:21

网络安全-等级保护(等保) 2-3 GB/T 22240—2020《信息安全技术网络安全等级保护定级指南》-2020-04-28发布【现行】

################################################################################ 在开始等级保护安全建设前，第一步需要知道要保护的是什么，要保护到什么程度，所以在开始等级保护中介绍的第一个标准是《定级指南》，其中明确了…...

编程日记 2025/6/28 23:05:23

GNSS数据自动化下载系统的设计与实现

摘要本文详细介绍了三种不同设计的GNSS数据自动化下载系统，分别针对IGS观测数据、GRACE-FO Level-1B数据以及通过代理服务器获取数据的需求场景。系统采用Python实现，具备断点续传、完整性校验、异常处理和进度显示等核心功能。实验结果表明&#xff0…...

编程日记 2025/7/13 8:33:57

c语言第一个小游戏：贪吃蛇小游戏06

实现贪吃蛇四方向的风骚走位实现代码 #include <curses.h> #include <stdlib.h> struct snake{ int hang; int lie; struct snake *next; }; struct snake *head; struct snake *tail; int key; int dir; //全局变量 #define UP 1 //这个是宏定义&a…...

编程日记 2025/7/13 8:27:14

人工智能_大模型数据标注主要做什么_拉框_人工智能训练师_数据标准师介绍---人工智能工作笔记0244

随着大模型的快速发展,数据标注迅速成为比较热门的工作,那么数据标注,具体干什么呢? 因为现在人工智能在某个领域如果理解,或者识别的越精准,那么就需要越高质量的数据, 就是因为,模型的训练,大多还是有监督深度学习.给他足够高质量的数据才行有好的效果. 可以看到在AI领…...

编程日记 2025/7/13 8:30:24

工业4G路由器IR5000公交站台物联网应用解决方案

随着城市化进程的加速，公共交通是智慧城市的重要枢纽。城市公共交通由无数的公交站台作作为节点组合而成，其智能化升级成为提升城市出行效率与服务质量的关键。传统公交站台信息发布滞后、缺乏实时性，难以满足乘客对公交信息快速获取的需求&a…...

编程日记 2025/7/10 0:54:36

文件操作: File 类的用法和 InputStream, OutputStream 的用法

目录 1. File 概述 1.1 File的属性 1.2 File的构造方法 1.3 File的方法 2. 文件的基本操作 2.1 InputStream 2.2 OutputStream 2.3.字符流读取(Reader) 2.4 字符流写（Writer） 1. File 概述 Java 中通过 java.io.File 类来对⼀个文件&#xf…...

编程日记 2025/7/13 8:29:26

SQL 中 INSTR 函数简介及截取地址应用

一、基本语法与参数解析语法： INSTR(string1, string2 [, start_position [, nth_occurrence]]) 参数说明： a.string1：源字符串（必选）。 b.string2：需查找的子字符串&am…...

编程日记 2025/6/28 23:05:28

Oracle SYSTEM/UNDO表空间损坏的处理思路

Oracle SYSTEM/UNDO表空间损坏是比较棘手的故障，通常会导致数据库异常宕机进而无法打开数据库。数据库的打开故障处理起来相对比较麻烦，读者可以参考本书第5章进一步了解该类故障的处理过程。如果数据库没有备份，通常需要设置官方不推荐的隐含…...

编程日记 2025/6/28 23:05:22

【HarmonyOs鸿蒙】七种传参方式

一、页面间导航传参使用场景：页面跳转时传递参数实现方式：通过router模块的push方法传递参数 // 页面A传参 import router from ohos.router;router.pushUrl({url: pages/PageB,params: { id: 123, name: HarmonyOS } });// 页面B接收参数 Entry Co…...

编程日记 2025/7/13 8:31:52

微信小程序密码框改为text后不可见，需要点击一下

这个问题是做项目的时候碰到的。密码框常规写法： <view class"inputBox"><view class"input-container"><input type"{{inputType}}" placeholder"请输入密码" data-id"passwordValue" bindin…...

编程日记 2025/6/29 0:00:52

Gatsby知识框架

一、Gatsby 基础概念 1. 核心特性基于React的静态站点生成器：使用React构建，输出静态HTML/CSS/JS GraphQL数据层：统一的数据查询接口丰富的插件系统：超过2000个官方和社区插件高性能优化：自动代码分割、预加载、…...

编程日记 2025/7/13 8:27:13

TCP协议十大核心特性深度解析：构建可靠传输的基石

TCP（传输控制协议）作为互联网的"交通指挥官"，承载着全球80%以上的网络流量。本文将深入解析TCP协议的十大核心特性，通过原理剖析、流程图解和实战案例，揭示其如何实现高效可靠的数据传输。一、面向连接的可…...

编程日记 2025/6/29 0:56:25

【架构】RUP统一软件过程：企业级软件开发的全面指南

一、RUP概述 RUP(Rational Unified Process，统一软件过程)是由Rational Software公司(后被IBM收购)开发的一种迭代式软件开发过程框架。它结合了传统瀑布模型的系统性和敏捷方法的灵活性，为中大型软件项目提供了全面的开发方法论。 RUP不仅仅是一种过程…...

编程日记 2025/6/29 1:11:34

基于智能家居项目实现DHT11驱动源代码

DHT11 温湿度传感器的数据读取一般分为四个步骤，下面详细介绍每个步骤的具体内容： 步骤一：主机发送起始信号主机（如 MCU）主动向 DHT11 发送开始信号，方式为： 将数据线拉低至少 18ms&…...

编程日记 2025/7/13 8:33:15

小程序的内置组件

一、Text文本组件 1.Text组件解析 Text组件用于显示文本, 类似于span标签, 是行内元素 user-select属性决定文本内容是否可以让用户选中 space有三个取值(了解) decode是否解码(了解) decode可以解析的有 < > & ' &ensp; &emsp;二、Butto…...

编程日记 2025/6/28 23:12:29

T-BOX硬件方案深度解析：STM32与SD NAND Flash存储的完美搭配

在智能网联汽车快速发展的当下，车载 T-BOX（Telematics Box）作为车辆与云端互联的核心枢纽，其性能和可靠性直接决定了用户体验的上限。米客方德（MK）推出的基于 STM32H7RX 主控芯片与 MKDV4GIL-AST&#xff0…...

编程日记 2025/7/13 8:29:27

hadoop3.x单机部署

jdk hadoop3.x需要jdk8以上的版本 hadoop3.x 从官网下载对应的tar.gz文件配置环境变量 vim /etc/profile# 需要替换为自己的安装地址！！！ export JAVA_HOME/usr/lib/jvm/java-1.8.0-openjdk-amd64 export PATH$PATH:$JAVA_HOME/bin expo…...

编程日记 2025/7/1 21:33:24

Hadoop的目录结构和组成

Hadoop 目录结构 bin 目录：包含了 Hadoop 的各种命令行工具，如hadoop、hdfs等，用于启动和管理 Hadoop 集群，以及执行各种数据处理任务。etc 目录：存放 Hadoop 的配置文件，包括core-site.xml、hdfs-site.xm…...

编程日记 2025/7/13 8:28:45

深度剖析 RTX 4090 GPU 算力租赁：从技术优势到生态价值的全维度解析

一、引言：当算力成为数字经济的 "新石油" 在 AI 大模型训练成本突破千万美元大关、元宇宙场景渲染需求呈指数级增长的 2025 年，算力已然成为驱动技术创新的核心生产要素。NVIDIA RTX 4090 显卡作为消费级 GPU 的性能天花板，正通…...

编程日记 2025/7/13 8:28:04

基于MATLAB的生物量数据拟合模型研究

一、研究背景在现代科学研究与工程实践的广泛领域中，数据拟合扮演着举足轻重的角色。从物理学中对复杂物理现象的建模，到生物学里对生物生长规律的探究，数据拟合已成为揭示数据内在规律、构建有效数学模型的关键技术手段。其核心要义在于&am…...

编程日记 2025/6/28 23:05:31

VSCode设置SSH免密登录

引言 2025年05月13日20:21:14 原来一直用的PyCharn来完成代码在远程服务器上的运行，但是PyCharm时不时同步代码会有问题。因此，尝试用VSCode来完成代码SSH远程运行。由于VSCode每次进行SSH连接的时候都要手动输入密码，为了解决这个问题在本…...

编程日记 2025/7/6 6:11:47

微信小程序的开发及问题解决

HttpClient 测试例子 SpringBootTest public class HttpClientTest {/*** 测试通过httpclient发送get方式的请求*/Testpublic void testGET() throws IOException {//创建httpclient对象CloseableHttpClient httpClient HttpClients.createDefault();//创建请求对象HttpGet ht…...

编程日记 2025/6/29 1:02:55

vscode百宝箱工具插件(devtools)

vscode百宝箱插件是一款结合JSON格式化， 正则表达式测试等工具为一体的插件， 直接嵌入到vscode里面， 省去了上网去找相应的工具一、插件名称：devtools(TraesureBox) 目前插件上传到vscode插件市场， 搜索 devtools 看…...

编程日记 2025/6/28 23:19:14

3.5 统计初步

本章系统阐述统计推断理论基础，涵盖大数定律、抽样分布、参数估计与假设检验等核心内容。以下从六个核心考点系统梳理知识体系： 考点一：大数定律与中心极限定理 1. 大数定律切比雪夫不等式： 设随机变量 X X X 的数学期望 E (…...

编程日记 2025/6/28 23:05:25

物联网设备状态监控全解析：从告警参数到静默管理的深度指南-优雅草卓伊凡

物联网设备状态监控全解析：从告警参数到静默管理的深度指南-优雅草卓伊凡在当今万物互联的时代，物联网设备的稳定运行已成为企业数字化转型的基石。优雅草星云智控系统作为新一代智能监控平台，其设备告警管理模块集成了先进的监控逻辑与人性…...

编程日记 2025/6/28 23:44:23

讯联云库项目开发日志（一）

1、设计数据库 2、写基本框架 entity、controller、service、exception、utils、mapper mapper层： 生成了一系列的CRUD方法工具类：线程安全的日期工具类、参数校验工具类线程安全的日期工具类：主要用于日期格式化&…...

编程日记 2025/7/8 0:36:11

假设无向图为：

一、使用Prim算法：

二、使用Kruskal算法：

相关文章：