【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)
文章目录
- 前置问题
- 问题解答
- 一、基础概念:最小生成树的定义和性质
- (1)最小生成树(Minimal Spanning Tree)的定义
- (2)最小生成树(MST)的性质
- 二、如何利用MST性质寻找最小生成树
- 三、Prim算法
- (1)Prim算法思想
- (2)Prim算法形成最小生成树的详细过程
- (3)Prim算法的C++和python实现
- 四、Dijkstra算法
- (1)和Prim算法的联系
- (2)Dijkstra算法思想
前置问题


问题解答

一、基础概念:最小生成树的定义和性质
(1)最小生成树(Minimal Spanning Tree)的定义
生成树的代价:设G(V,E)G(V,E)G(V,E)是一个无向连通网图,生成树上各边的权值之和称为生成树的代价。最小生成树:在图GGG所有生成树中,代价最小的生成树为最小生成树。
(2)最小生成树(MST)的性质
假设G=(V,E)G=(V,E)G=(V,E)是一个无向连通网图,UUU是顶点集的一个非空子集。若(u,v)(u,v)(u,v)是一条具有最小权值的边,其中u∈U,v∈V−Uu\in U,v\in V-Uu∈U,v∈V−U,则必存在一棵包含边u,vu,vu,v的最小生成树。

二、如何利用MST性质寻找最小生成树
- 找到两个点集之间最小权值的边(u,v)(u,v)(u,v),让具有最小权值的(u,v)(u,v)(u,v)成为最小生成树的一部分,将大于最小权值的(u,v)(u,v)(u,v)删除。
接下来有两个思路:
- 从一个点出发,一次加入点形成点集
(Prim算法) - 从边出发,将点集合并,避免形成环
(Kruskal算法)
三、Prim算法
(1)Prim算法思想
对点做操作,维护一个在最小生成树中的点的顶点集A,以及一个待处理点的顶点集B,每次找出连接这两个集合的最短边,并将其两个顶点都加入集合A,直到所有顶点都处理完毕。
抽象描述:(觉得抽象跳过)

(2)Prim算法形成最小生成树的详细过程

图注:
- 红色线段表示最小生成树
- 蓝圈表示集合UUU,其他顶点集合为V−UV-UV−U
- 蓝色线段表示UUU和V−UV-UV−U的相邻边

计算U中每个点和其相邻点之间的代价,找出代价最小的点V5,将V5纳入U集合。计算U中每个点和其相邻点之间的代价,找出代价最小的点V5,将V5纳入U集合。计算U中每个点和其相邻点之间的代价,找出代价最小的点V5,将V5纳入U集合。







(3)Prim算法的C++和python实现
四、Dijkstra算法
(1)和Prim算法的联系
Dijkstra算法和Prim算法都是最短路径算法,主要用于求图的最短路径。
不同点在于,Dijkstra算法适用于有向图起点到其他点的最短路径,而Prim算法适用于无向图求最小生成树。它们的求解过程也略有不同。Dijkstra算法每次选择距离起点最近的点作为新的访问点,更新其他点到起点的最短距离,直到所有点都被访问。Prim算法则从一个起点开始,不断选择与已经访问过的点相连且边权最小的点,直到图上所有点都被访问。
(2)Dijkstra算法思想


算出A点到图中每一点的路径长度,选出一条最短路径:A->B,将顶点B加入集合S。
增加了一条最短路径之后,顶点A到其他点的路径是不是有更短的路径了呢?
更新最短路径:

在A->C,A->D,A->E中选出最短路径:A->D,并将D顶点加入S集合。更新所有最短路径。



相关文章:
【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)
文章目录前置问题问题解答一、基础概念:最小生成树的定义和性质(1)最小生成树(Minimal Spanning Tree)的定义(2)最小生成树(MST)的性质二、如何利用MST性质寻找最小生成树…...
Session与Cookie的区别(一)
从我刚开始学程序时这一题就常出现在面试考题里,一直到现在都还是能看见这个问题。 这个问题重要吗?我觉得蛮重要的。因为 Session 所代表的是「状态」,如果没有了状态,一大堆功能都会失效。 对于工程师来说必须去理解什么是 Sess…...
【Java】重载和重写的区别
重载(Overload) 在同一个类中,同名的方法如果有不同的参数列表(参数类型不同、参数个数不同甚至是参数顺序不同)则视为重载。同时,重载对返回类型没有要求,可以相同也可以不同,但不能通过返回类型是否相同…...
AcWing 第 90 场周赛
目录A、首字母大写B、找数字C、构造字符串A、首字母大写 原题链接:AcWing 4806. 首字母大写 签到题。 #include <bits/stdc.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string s;cin >> s;s[0] toupper(s[0]);…...
刚刚,体验了一把Bing chat很爽
文章目录刚刚,体验了一把Bing chat很爽你能做啥?与chatgpt有什么不同?以下是Bingchat的 10个新功能1⃣️在网上搜索结果2⃣️摘要链接3⃣️对话助手4⃣️向您发送实际信息,正确的链接5⃣️在单个查询中执行多个搜索6⃣️玩冒险游戏…...
牛客网Python篇数据分析习题(二)
1.现有一个Nowcoder.csv文件,它记录了牛客网的部分用户数据,包含如下字段(字段与字段之间以逗号间隔): Nowcoder_ID:用户ID Level:等级 Achievement_value:成就值 Num_of_exercise&a…...
如何用Python打包好exe文件,并替换图标
前言 Python打包?打包exe文件?怎么操作? ok,今天我来分享分享,教你们如何打包号文件,顺便还来展示一下,如何替换好图标 首先把你的代码准备好,尽量不要中文路径,容易报…...
NFC概述摘要
同学,别退出呀,我可是全网最牛逼的 WIFI/BT/GPS/NFC分析博主,我写了上百篇文章,请点击下面了解本专栏,进入本博主主页看看再走呗,一定不会让你后悔的,记得一定要去看主页置顶文章哦。 原理来说,NFC和Wi-Fi类似,利用无线射频技术来实现设备间通信。NFC的工作频率为13.5…...
Python-项目实战--贪吃蛇小游戏(1)
1.贪吃蛇游戏规则贪吃蛇游戏规则如下:1.1开始和结束贪吃蛇初始出现在游戏窗口的左上角位置,体长共有3节游戏过程中,一旦蛇头撞到了窗口的边缘或者身体的其他部位,游戏结束游戏过程中,点击游戏窗口的关闭按钮,或者按下ESC键可以直接退出游戏一…...
vscode sftp从linux服务器下载文件至本地:No such file or dictionary【已解决】
在服务器跑完程序需要下载数据的时候报错: [warn] ENOENT: no such file or directory, open /home/LIST_2080Ti/.ssh/config load /home/LIST_2080Ti/.ssh/config failed 完整报错内容如下: [02-10 08:38:47] [info] config at /home/LIST_2080Ti {&q…...
详解指针(2)(初阶版)
前言:内容包括:指针运算,指针和数组,二级指针,指针数组 详解指针(1)(点击即跳转) part 1:指针运算 1 指针-整数 以如下代码为例:初始化数组内容…...
超详细讲解字符串查找函数(保姆级教程!!!)
超详细讲解字符串查找函数(保姆级教程!!!)字符串查找函数strstr函数strstr函数的使用strstr函数的模拟实现strtok函数strtok函数的使用strtok函数的模拟实现strpbrk函数strpbrk函数的使用strpbrk函数的模拟实现strcspn…...
LeetCode-1138. 字母板上的路径【哈希表,字符串】
LeetCode-1138. 字母板上的路径【哈希表,字符串】题目描述:解题思路一:首先考虑坐标位置,字符是有序的从0开始,当前字符c的行为(c-a)/5,列为(c-a)%5。其次是考虑特殊情况z。若当前从‘z’开始则只能往上走;若是其他字符…...
Vue 可配置化的路由缓存(Vu2 Vue3)
Vue 可配置化的路由缓存(Vu2 & Vue3) 1 介绍 在Vue的项目当中,路由缓存是一个比较常见的功能,譬如,从列表页面进入到详情页面,返回到列表页面时,如果可以保持列表的状态,那用户…...
Linux VPU驱动
1. 前言 限于作者能力水平,本文可能存在谬误,因此而给读者带来的损失,作者不做任何承诺。 2. 概述 VPU 是用来进行图像、视频数据进行硬件编、解码的硬件模块。内部集成了 Encoder、Decoder 功能部件进行图像、视频数据进行硬件编、解码&a…...
spring 笔记
一、spring概述 1.1 spring介绍 spring是一个轻量级的控制反转和面向切面的容器框架,用来解决企业项目开发的复杂度问题---解耦 轻量级:体积小,对代码没有侵入性控制反转:IOC inverse of control, 把创建对象的工作交…...
Java日志框架学习
首先,Java日志框架可以分为两类:门面型日志框架和记录型日志框架。 门面型日志框架 JCL:Java日志接口,后更名为Commons LoggingSLF4J:是一套简易Java日志门面,本身并无日志的实现 记录型日志框架 JUL&a…...
基础面试题:堆和栈的区别
面试题:堆和栈的区别(往往讲的是内存zha) 为什么说访问栈栈比访问堆快些? 目录 一、数据结构中的堆栈 1、数据结构中的堆 1)堆的定义 2)堆的效率 2、 数据结构中的栈 二、内存中的堆栈 1、内存堆的定义…...
(干货教程)在VSCode并使用chatgtp插件编写CC++语言程序
(干货教程)在VSCode并使用chatgtp插件编写CC语言程序 下载并安装VSCODE 第1步,下载VSCODE https://code.visualstudio.com/Download 第2步,安装VSCODE 安装过程较简单,这里省略。 安装好后效果如图:…...
【思维模型】概率思维的价值:找到你的人生算法,实现阶级跃迁!
把同样公平的机会放在放在很多人面前,不同的人生算法,会得到迥然不同的结果。 概率思维是什么? 【ChatGPT】概率思维是一种通过使用数学模型来思考和评估不确定性事件的方法。它通过计算不同可能性的概率来预测事件的结果,并评估风险和机会。 概率思维的价值在于它可以帮…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
