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

图论模板详解

目录

Floyd算法

例题:蓝桥公园

Dijkstra算法

例题:蓝桥王国 

SPFA算法

例题:随机数据下的最短路问题

总结

最小生成树MST

Prim算法

Kruskal算法

例题:聪明的猴子

Floyd算法

最简单的最短路径算法,使用邻接矩阵存图,因为Floyd算法计算的结果是所有点对之间的最短路,本身就要n^{2}的空间,用矩阵存储最合适。效率不高,计算复杂度为O\left ( n^{3} \right ),只能用于n<300的小规模的图,不能用于大图,在某些场景下有自己的优势,难以替代,能做传递闭包问题。

for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=min(dp[i][j],d[i][k]+dp[k][j]);}}
} 

Floyd算法是多源最短路算法,以此计算能得到图中每一对结点之间(多对多)的最短路径。

Floyd算法能判断负圈,若图中有权值为负的边,某个经过这个负边的环路,所有边长相加的总长度也是负数,这就是负圈。在这个负圈上每绕一圈,总长度就更小,从而陷入在兜圈子的死循环。Floyd算法很容易判断负圈,只要在算法运行过程中出现任意一个dp[i][j]<0就说明有负圈,因为dp[i][j]是从i出发,经过其它中转点绕一圈回到自己的最短路径,如果等于0,就存在负圈。

例题:蓝桥公园

#include<bits/stdc++.h>
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int N=405;
long long dp[N][N];
int n,m,q;
void floyd(){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);}}}
}
int main(){cin>>n>>m>>q;memset(dp,0x3f,sizeof(dp));for(int i=1;i<=m;i++){int u,v;long long w;cin>>u>>v>>w;dp[u][v]=dp[v][u]=min(dp[u][v],w);}floyd();while(q--){int s,t;cin>>s>>t;if(dp[s][t]==INF){cout<<"-1"<<endl;}else if(s==t){cout<<"0"<<endl;}else{cout<<dp[s][t]<<endl;}}return 0;
}

Dijkstra算法

Dijkstra算法用于求解单源最短路径问题,非常高效而且稳定,但是只能处理不含负权边的图。

Dijkstra算法是贪心思想实现的,首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,所谓的松弛操作就是,遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,这样把所有的点找遍之后就存下了起点到其它所有点的最短距离。

采用优先队列实现,每次往队列中放数据时,按从小到大的顺序放,采用小顶堆的方式,复杂度是O\left ( logn \right ),保证最小的数总在最前面。找最小值,直接取第一个数,复杂度是O\left ( 1 \right )

例题:蓝桥王国 

#include<bits/stdc++.h>
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int N=3e5+2;
struct edge{int from,to;long long w;edge(int a,int b,long long c){from=a;to=b;w=c;}
};
vector<edge>e[N];
struct s_node{int id;long long n_dis;s_node(int b,long long c){id=b;n_dis=c;}bool operator < (const s_node &a) const{ return n_dis>a.n_dis;}
};
int n,m;
int pre[N];
void print_path(int s,int t){if(s==t){printf("%d ",s);return;}print_path(s,pre[t]);printf("%d ",t);
}
long long dis[N];
void dijkstra(){int s=1;bool done[N];for(int i=1;i<=n;i++){dis[i]=INF;done[i]=false;}dis[s]=0;priority_queue<s_node>Q;Q.push(s_node(s,dis[s]));while(!Q.empty()){s_node u=Q.top();Q.pop();if(done[u.id]){continue;}done[u.id]=true;for(int i=0;i<e[u.id].size();i++){edge y=e[u.id][i];if(done[y.to]){continue;}if(dis[y.to]>y.w+u.n_dis){dis[y.to]=y.w+u.n_dis;Q.push(s_node(y.to,dis[y.to]));pre[y.to]=u.id;}}}
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){e[i].clear();}while(m--){int u,v,w;cin>>u>>v>>w;e[u].push_back(edge(u,v,w));}dijkstra();for(int i=1;i<=n;i++){if(dis[i]>=INF){cout<<"-1";}else{cout<<dis[i];}}return 0;
}

SPFA算法

SPFA算法=队列处理+Bellman-Ford

Bellman-Ford算法有很多低效或无效的操作,其核心内容,是在每一轮操作中,更新所有节点到起点s的最短距离。

计算和调整一个节点u到s的最短距离后,如果紧接着调整u的邻居节点,这些邻居肯定有新的计算结果,而如果漫无目的的计算不与u相邻的节点,这可能毫无变化,所以这些操作是低效的。

改进:计算结点u之后,下一步只计算和调整它的邻居,能加速收敛的过程。这些步骤用队列操作

例题:随机数据下的最短路问题

 

#include<bits/stdc++.h>
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3f;
const int N=5e3+10;
struct edge{int to;long long w;edge(int tt,long long ww){to=tt;w=ww;}
};
long long dist[N];
int inq[N];
vector<edge>e[N];
void spfa(int s){memset(dist,0x3f,sizeof(dist));dist[s]=0;queue<int>q;q.push(s);inq[s]=1;while(!q.empty()){int u=q.front();q.pop();inq[u]=0;if(dist[u]==INF){continue;}for(int i=0;i<e[u].size();i++){int v=e[u][i].to;long long w=e[u][i].w;if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;if(!inq[v]){q.push(v);inq[v]=1;}}}}
}
int main(){int n,m,s;cin>>n>>m>>s;for(int i=1;i<=m;i++){int u,v;long long w;cin>>u>>v>>w;e[u].push_back(edge(v,w));}spfa(s);for(int i=1;i<=n;i++){if(dist[i]==INF){cout<<-1;}else{cout<<dist[i];}if(i!=n){cout<<" ";}else{cout<<endl;}}return 0;
}

总结

单源最短路

(1)当权值非负时,用Dijkstra算法。

(2)当权值有负值,且没有负圈,则用SPFA。SPFA能检测负圈,但是不能输出负圈。

(3)当权值有负值而且有负圈需要输出,则用Bellman-Ford,能够检测并输出负圈。

多源最短路

使用Floyd算法。

最小生成树MST

一个含有n个结点的连通图的生成树是原图的极小连通子图,包含原图中的所有n个结点,并且边的权值之和最小。

Prim算法

对点进行贪心操作,从任意一个点u开始,把距离它最近的点加入到MST中,下一步,把距离{u,v}最近的点w加入到MST中;继续这个过程,直到所有的点都在MST中。适用于稠密图。

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f3f3f3f3f;
const int MAXN=1005;
vector<int>demo;
int closest[MAXN],lowcost[MAXN],n,m;//m为节点的个数,n为边的数量
int G[MAXN][MAXN];//邻接矩阵
int prim(){for(int i=0;i<n;i++){lowcost[i]=INF;}for(int i=0;i<m;i++){closest[i]=0;}closest[0]=-1;//加入第一个点,-1表示该点在集合U中,否则在集合V中int num=0,ans=0,e=0;while(num<m-1){//当点还没有全部放进去 int micost=INF;for(int i=0;i<m;i++){if(closest[i]!=-1){int temp=G[e][i];if(temp<lowcost[i]){lowcost[i]=temp;closest[i]=e;}if(lowcost[i]<micost){micost=lowcost[i];}}ans+=micost;demo.push_back(micost);closest[e]=-1;num++;}} return ans;
} 
int main(){cin>>m>>n;memset(G,INF,sizeof(G));for(int i=0;i<n;i++){int a,b,c;cin>>a>>b>>c;G[b][a]=G[a][b]=c;}cout<<prim()<<endl;for(int i=0;i<m-1;i++){cout<<demo[i]<<" ";}return 0;
}

Kruskal算法

对边进行贪心操作。从最短的边开始,把它加入到MST中,在剩下的边中找最短的边,加入到        MST中,继续这个过程,直到所有的点都在MST中。适用于稀疏图。

kruskal算法的两个关键技术:

(1)对边进行排序

(2)判断圈,即处理连通性问题。这个问题用并查集简单而高效,并查集是krustral算法的绝配。

例题:聪明的猴子

#include<bits/stdc++.h>
using namespace std;
int n,m,father[1100000];
struct node{int x,y,k;
}Q[1100000];
int find(int x){if(father[x]==x){return x;}return father[x]=find(father[x]);
} 
bool cmp(node a,node b){return a.k<b.k;
}
int main(){cin>>n>>m;int sum=0,st=0;for(int i=0;i<m;i++){//把m条边扫描进来 cin>>Q[i].x>>Q[i].y>>Q[i].k;}sort(Q,Q+m,cmp);for(int i=1;i<=n;i++){father[i]=i;}for(int i=0;i<m;i++){int tx=find(Q[i].x);int ty=find(Q[i].y);if(tx!=ty){sum+=Q[i].k;st++;father[tx]=ty;if(st==n-1){break;}}}cout<<sum<<endl;return 0;
}

相关文章:

图论模板详解

目录 Floyd算法 例题&#xff1a;蓝桥公园 Dijkstra算法 例题&#xff1a;蓝桥王国 SPFA算法 例题&#xff1a;随机数据下的最短路问题 总结 最小生成树MST Prim算法 Kruskal算法 例题&#xff1a;聪明的猴子 Floyd算法 最简单的最短路径算法&#xff0c;使用邻接…...

ArcGIS Pro打不开Excel?Microsoft驱动程序安装不上?

刚用ArcGIS pro的朋友们可能经常在打开xls或者xlsx文件的时候都会提示&#xff0c;未安装所需的Microsoft驱动程序。 怎么办呢&#xff1f;当然&#xff0c;按照提示装一下驱动就会好吗&#xff1f;有什么状况会出现&#xff1f;有什么临时替代方案呢&#xff1f; 全文目录&a…...

简单了解裸眼3D呈现技术

裸眼3D呈现是一种不需要佩戴任何特殊设备&#xff08;如3D眼镜或头盔&#xff09;即可观看到3D效果的技术。这种技术近年来得到了快速发展&#xff0c;为观众带来了更加沉浸式的视觉体验。 实现裸眼3D呈现的关键步骤包括&#xff1a; 创建立体图像源&#xff1a;首先需要有一…...

单元测试——Junit (断言、常用注解)

单元测试 Junit单元测试框架 使用 断言测试 使用Assert.assertEquals(message, 预期值, 实际值); 这段代码是用于在测试中验证某个方法的返回值是否符合预期。其中&#xff0c;"方法内部有bug"是用于在断言失败时显示的提示信息。4是预期的返回值&#xff0c;index…...

【蓝桥杯每日一题】4.2 全球变暖

原题链接&#xff1a;1233. 全球变暖 - AcWing题库 由题意可知&#xff1a; 需要找到淹没的岛屿的数量淹没的岛屿所具备的条件&#xff1a;咩有“高地”&#xff0c;也就是说岛屿&#xff08;连通块&#xff09;中的所有元素的 4 4 4-邻域中均含有’ . ’ 思路1&#xff1a;…...

ffmpeg点对点音视频udp协议传输

参考&#xff1a;https://zhuanlan.zhihu.com/p/636152437?utm_id0 ffmpeg查看可用设备&#xff1a; ffmpeg -list_devices true -f dshow -i dummy1、音频 局域网内两台设备间 设备1-音频&#xff1a; ffmpeg -f dshow -i audio"麦克风阵列 (适用于数字麦克风的英特…...

ensp华为AC+AP上线配置

AR1配置&#xff1a; <Huawei>system-view # 进入系统视图<Huawei>sysname R1 # 设备重命名[R1]dhcp enable # 开启DHCP功能[R1]interface GigabitEthernet0/0/0 # 进入接口 [R1-GigabitEthernet0/0/0]ip address 192.168.0.1 23 # 配置接口地址 [R1-GigabitE…...

JAVA基础02-Java语言基础以及编译准备工作

什么是JAVA语言 Java是一门面向对象的编程语言&#xff0c;不仅吸收了C语言的各种优点&#xff0c;还摒弃了C里难以理解的多继承、指针等概念&#xff0c;因此Java语言具有功能强大和简单易用的两个特征。 &#xff08;可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式…...

Photoshop 2024 Mac/win---图像处理的新纪元,解锁无限创意

Photoshop 2024是一款功能强大的图像处理软件&#xff0c;以其卓越的性能和广泛的应用领域&#xff0c;赢得了设计师、摄影师、图形艺术家等各类创意工作者的青睐。它提供了丰富的绘画和编辑工具&#xff0c;让用户能够轻松进行图片编辑、合成、校色、抠图等操作&#xff0c;实…...

【MySQL系列】使用 ALTER TABLE 语句修改表结构的方法

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

ElementUI 表格横向滚动条时滚动到指定位置

ElementUI 表格横向滚动条时滚动到指定位置 getColumnOffset(columnProp) {this.$nextTick(() > {const table this.$refs.tableRef.$refs.multipleTable;const columns table.columns;const column columns.find((col) > col.property columnProp);if (column) {// …...

【论文阅读】DETR 论文逐段精读

【论文阅读】DETR 论文逐段精读 文章目录 【论文阅读】DETR 论文逐段精读&#x1f4d6;DETR 论文精读【论文精读】&#x1f310;前言&#x1f4cb;摘要&#x1f4da;引言&#x1f9ec;相关工作&#x1f50d;方法&#x1f4a1;目标函数&#x1f4dc;模型结构⚙️代码 &#x1f4…...

负载均衡:实现高效稳定的网络服务

随着互联网技术的快速发展&#xff0c;网络应用服务的规模和复杂性日益增加。为了满足日益增长的用户需求&#xff0c;确保服务的高可用性和稳定性&#xff0c;负载均衡技术应运而生。本文将详细介绍负载均衡的概念、原理、分类以及应用场景&#xff0c;帮助读者深入了解这一关…...

2024最新软件测试【测试理论+ 抓包与网络协议】面试题(内附答案)

一、测试理论 3.1 你们原来项目的测试流程是怎么样的? 我们的测试流程主要有三个阶段&#xff1a;需求了解分析、测试准备、测试执行。 1、需求了解分析阶段 我们的 SE 会把需求文档给我们自己先去了解一到两天这样&#xff0c;之后我们会有一个需求澄清会议&#xff0c; …...

极简7照训练法,奇趣相机引领儿童AI摄影潮流

近日&#xff0c;奇趣未来推出一款专注于儿童AI摄影市场的微信小程序——奇趣相机&#xff0c;搭载了专为中国儿童精心研发的AIGC大模型&#xff0c;精准捕捉并贴合亚洲儿童人脸特征&#xff0c;让每一个孩子的笑容都能被完美定格。它不仅涵盖了从3岁至12岁各个年龄段的儿童摄影…...

Flink应用

1.免密登录 2.flink StandAlone模式 3.Flink Yarn 模式 (on per 模式,on session 模式) Flink概述 按照Apache官方的介绍&#xff0c;Flink是一个对有界和无界数据流进行状态计算的分布式处理引擎和框架。通俗地讲&#xff0c;Flink就是一个流计算框架&#xff0c;主要用来处…...

C# 委托与事件 终章

C# 委托与事件 浅尝 C# 委托与事件 深入 委托 委托有什么用&#xff1f; 将函数作为函数的参数传递声明事件并用来注册 强类型委托 Action<T1> Func<T1, TResult>事件 希望一个类的某些成员在发生变化时能被外界观测到 CollctionChangedTextChanged 标准.Ne…...

MySQL-linux安装-万能RPM法

一、MySQL的Linux版安装 1、 CentOS7下检查MySQL依赖 1. 检查/tmp临时目录权限&#xff08;必不可少&#xff09; 由于mysql安装过程中&#xff0c;会通过mysql用户在/tmp目录下新建tmp_db文件&#xff0c;所以请给/tmp较大的权限。执行 &#xff1a; chmod -R 777 /tmp2. …...

elment UI el-date-picker 月份组件选定后提交后台页面显示正常,提交后台字段变成时区格式

需求&#xff1a;要实现一个日期的月份选择<el-date-picker :typeformData.dateType :value-formatdateFormat v-modelformData.leaveFactoryDateplaceholder选择月份></el-date-picker>错误示例&#xff1a;将日期显示类型(type)dateType或将日期绑定值的格式(val…...

基于 NGINX 的 ngx_http_geoip2 模块 来禁止国外 IP 访问网站

基于 NGINX 的 ngx_http_geoip2 模块 来禁止国外 IP 访问网站 一、安装 geoip2 扩展依赖 [rootfxkj ~]# yum install libmaxminddb-devel -y二、下载 ngx_http_geoip2_module 模块 [rootfxkj tmp]# git clone https://github.com/leev/ngx_http_geoip2_module.git三、解压模…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...