5.3图的综合应用算法

一.最小生成树算法

1.概念(Minimum-Spanning-Tree)MST

生成树:针对于连通图,包含全部顶点,去掉一条边后不连通,加一条边形成环
最小生成树:带权连通无向图,边的权值之和最小的生成树(MST)

2.普里姆Prim算法(顶点)

从一个顶点开始出发,选择这个顶点代价最小的顶点进行构造,重复执行,一直到所有顶点全部进入生成树中
只关注顶点,,时间复杂度:O(|V|)
适合边稠密图

//伪代码核心
1.节点入树数组
isJoint[v];
2.用于更新各顶点的代价地图
lowCost[v];

在这里插入图片描述

3.Kruskal最小生成树算法(边)

算法执行过程:
从代价最小的一条边出发,选择最小的两端顶点未连接的边,不断重复,直到把全部顶点装入生成树中
只关注边,时间复杂度O(|E|log2|E|)
适合边稀疏图
在这里插入图片描述

二、最短路径生成算法

1.BFS寻找无向不带权图最短路径

适用于无权无向图寻找最短路径

相关代码原理:

d[i]:表示从u到i结点的最短路径
path[i]:最短路径从哪个顶点过来**
bool visited[MAX_VERTEX_NUM]; //记录该节点是否访问过

    void BFS_MIN_Distance(Graph G, int u)
    {
        for (i = 0; i < G.vexnum; ++i)
        {
            d[i] = 无穷       //初始化路径长度
            path[i] = -1; //最短路径从哪个顶点过来
        }
        d[u] = 0;
        visited[u] = TRUE;
        EnQueue(Q, u);
        while (!= isEmpty(Q))
        {
            DeQueue(Q, u);
            for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor)
            {
                if (!visited[w])
                {
                    d[w] = d[u] + 1;
                    path[w] = u;
                    visited[w] = TRUE;
                    EnQueue(Q, w);
                }
            }
        }    

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

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

相关文章

基于LPP算法实现MNIST数据集降维

目录 1、作者介绍2、LPP算法简介2.1 基本概念及原理2.2 算法流程 3、LPP算法实现3.1 数据集简介3.2 代码实现3.2.1 完整代码3.2.2 运行结果 4、参考链接 1、作者介绍 刘晨雨&#xff0c;男&#xff0c;西安工程大学电子信息学院&#xff0c;2022级研究生 研究方向&#xff1a;…

Tomcat部署

Tomcat 一、Tomcat什么是 servlet&#xff1f;什么是 JSP?Tomcat 功能组件结构&#xff1a;Container 结构分析&#xff1a;Tomcat 请求过程&#xff1a; 二、Tomcat服务部署三、虚拟主机配置四、Tomcat多实例部署 Tomcat 是 Java 语言开发的&#xff0c;Tomcat 服务器是一个免…

前端录制回放rrweb

rrweb 是 ‘record and replay the web’ 的简写&#xff0c;旨在利用现代浏览器所提供的强大 API 录制并回放任意 web 界面中的用户操作。 rrweb中文文档 https://github.com/rrweb-io/rrweb/blob/master/guide.zh_CN.md 本文项目地址 https://github.com/qdfudimo/vue-rrweb…

目标检测算法:YOLO v1论文解读

目标检测算法&#xff1a;YOLO v1论文解读 前言 ​ 其实网上已经有很多很好的解读各种论文的文章了&#xff0c;但是我决定自己也写一写&#xff0c;当然&#xff0c;我的主要目的就是帮助自己梳理、深入理解论文&#xff0c;因为写文章&#xff0c;你必须把你所写的东西表达清…

深入了解Java虚拟机之高效并发

目录 Java内存模型与线程 概述 硬件的效率与一致性 Java内存模型 主内存与工作内存 内存间交互操作 对于volatile型变量的特殊规则 原子性、可见性与有序性 先行发生原则 Java与线程 线程实现 线程调度 状态切换 小结 线程安全与锁优化 概述 线程安全 Java中…

简单的UDP网络程序·续写

该文承接文章 简单的UDP网络程序 对于客户端和服务端的基本源码参考上文&#xff0c;该文对服务器润色一下&#xff0c;并且实现几个基本的业务服务逻辑 目录 demo1 第一个功能&#xff1a;字典翻译 初始化字典 测试代码&#xff1a;打印 字符串分割 客户端修改 成品效果…

AI宝典:AI超强工具大整合

&#x1f604;&#x1f604;个人介绍 光子郎.进行开发工作七年以上&#xff0c;目前涉及全栈领域并进行开发。会经常跟小伙伴分享前沿技术知识&#xff0c;java后台、web前端、移动端&#xff08;Android&#xff0c;uniapp&#xff0c;小程序&#xff09;相关的知识以及经验体…

C#发送邮箱设置及源码

用C#调用发送邮箱代码之前需要邮箱开通SMTP/POP3及设置授权码&#xff0c;开通及获取方法如下&#xff1a; 1、打开邮箱&#xff0c;登录邮箱&#xff0c;进入设置&#xff0d;》帐户 2、在“帐户”设置中&#xff0c;找到服务设置项&#xff0c;进行设置&#xff0c;如下…

[Flink] Flink On Yarn(yarn-session.sh)启动错误

在Flink上启动 yarn-session.sh时出现 The number of requested virtual cores for application master 1 exceeds the maximum number of virtual cores 0 available in the Yarn Cluster.错误。 版本说明&#xff1a; Hadoop&#xff1a; 3.3.4 Flink&#xff1a;1.17.1 问题…

Python实战基础20-解密文件及目录操作

任务1 为泸州驰援湖北的89名白衣勇士点赞 【任务描述】 设计python程序&#xff0c;实现用户可以为泸州驰援湖北的89名白衣勇士点赞留言。用户点赞留言内容保存到本地txt文件中。 import os # 导入os模块 import random # 导入随机模块 import string # 导入string模块# 定义…

《Lua程序设计》--学习3

输入输出 简单I/O模型 Lua 文件 I/O | 菜鸟教程 (runoob.com) 暂留 补充知识 局部变量和代码块 Lua语言中的变量在默认情况下是全局变量&#xff0c;所有的局部变量在使用前必须声明 在交互模式中&#xff0c;每一行代码就是一个代码段&#xff08;除非不是一条完整的命…

chatgpt赋能python:Python如何将IP地址转换为整数

Python如何将IP地址转换为整数 在计算机网络中&#xff0c;IP地址是一个包含32位的二进制数字&#xff0c;通常由四个8位二进制数字&#xff08;即“点分十进制”&#xff09;表示。但在某些情况下&#xff0c;需要将IP地址转换为整数&#xff0c;例如在网络编程中检查网络连接…

Ingress详解

Ingress Service对集群外暴露端口两种方式&#xff0c;这两种方式都有一定的缺点&#xff1a; NodePort &#xff1a;会占用集群集群端口&#xff0c;当集群服务变多时&#xff0c;缺点明显LoadBalancer&#xff1a;每个Service都需要一个LB&#xff0c;并且需要k8s之外设备支…

FPGA量子类比机制-FPQA,将在量子运算设计中引发一场新的革命

1980年代现场可程式化逻辑门阵列(FPGA)的出现彻底改变了电子设计。大约40年后&#xff0c;现场可程式化量子位元阵列(FPQA)可望在量子运算电路设计中引发一场类似的革命。 1980年代现场可程式化逻辑闸阵列(FPGA)的出现彻底改变了电子设计。FPGA允许设计人员创建适合特定应用的…

ArrayList 万字长文解析:使用、优化、源码分析

文章目录 ArrayList 万字长文解析&#xff1a;使用、优化、源码分析前言ArrayList 简介ArrayList 的基本使用方法ArrayList 性能优化ArrayList 的源码分析内部结构构造方法解析扩容机制System.arraycop与 Arrays.copyof 实现方式 与 使用场景迭代器 JDK 8版本 ArrayList bug 示…

【基于Rsync实现Linux To Windows文件同步】

基于Rsync实现Linux To Windows文件同步 简介安装步骤安装Linux服务器端1.安装rsync2.启动Rsync3.验证是否启动成功4.修改rsyncd.conf重启rsync服务 安装Windows客户端1.rsync客户端安装&#xff1a;2.配置环境变量3.测试rsync命令4.创建密码文件5.密码文件授权6.查看服务端需要…

Python高光谱遥感数据处理与机器学习实践技术丨Matlab高光谱遥感数据处理与混合像元分解

目录 Python高光谱遥感数据处理与机器学习实践技术 第一章 高光谱基础 第二章 高光谱开发基础&#xff08;Python&#xff09; 第三章 高光谱机器学习技术&#xff08;python&#xff09; 第四章 典型案例操作实践 Matlab 高光谱遥感数据处理与混合像元分解 第一章 理论…

【大数据之路4】分布式计算模型 MapReduce

4. 分布式计算模型 MapReduce 1. MapReduce 概述1. 概念2. 程序演示1. 计算 WordCount2. 计算圆周率 π 3. 核心架构组件4. 编程流程与规范1. 编程流程2. 编程规范3. 程序主要配置参数4. 相关问题1. 为什么不能在 Mapper 中进行 “聚合”&#xff08;加法&#xff09;&#xff…

操作系统原理 —— 什么是基本分页存储管理?(二十二)

在操作系统中&#xff0c;一个新的进程需要载入内存当中执行&#xff0c;在装入的时候需要给该进程分配一定的运行内存&#xff0c;在之前的章节中讲解了连续分配的几种方式&#xff0c;比如&#xff1a;单一连续分配、固定分区分配、动态分区分配&#xff0c;还讲解了对应的动…

Nacos架构与原理 - 总体架构

文章目录 Nacos 起源Nacos 定位Nacos 优势Nacos 生态Nacos 总体设计设计原则架构图用户层业务层内核层插件 小结 Nacos 起源 Nacos 在阿里巴巴起源于 2008 年五彩石项目&#xff08;完成微服务拆分和业务中台建设&#xff09;&#xff0c;成长于十年双十⼀的洪峰考验&#xff…