当前位置: 首页 > 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三、解压模…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...