没有合适的资源？快使用搜索试试~ 我知道了~

C++图论专题(form Alex_Wei

需积分: 10 0 下载量 141 浏览量 2022-08-07 12:29:28 上传评论收藏 37KB DOCX 举报

温馨提示

试读

13页

最短路（Bellman-Ford，Dijsktra，SPFA，Johnson，Floyd），差分约束，最小生成树（Kruskal，Prim，Boruvka），有向图与无向图连通性（割点，割边，E-BCC 和 SCC 的缩点），欧拉回路。适合刚接触C++，并对基础数据结构有所了解（栈，二叉树，队列等），对建图有一定要求，需要熟练运用编程语言，掌握如vector,set,map等

资源推荐

资源详情

资源评论

基本定义

� 边导出子图：选出若干条边，以及这些边所连接的所有顶点组成的图称为边

导出子图。

� 点导出子图：选出若干个点，以及两端都在该点集的所有边组成的图称为点

导出子图。

� 闭合子图：定义在有向图上。点集 V 导出的闭合子图是所有 V 可达的点的

点导出子图。其精确定义为若 x 在子图内，则 x 的所有出点和出边均在子图

内的原图子图；等价于每个点能到的所有点都在子图中。

1. 最短路

最短路是图论最基本的一类问题。

下文记 disu 表示从源点到节点 u 的最短路，n 为节点数 |V|，m 为边数

|E|。

1.1 Bellman-Ford

Bellman-Ford 是一种非常暴力的求解最短路的方法（BF 之于 dijkstra 如同

FF 之于 dinic）。

称一轮松弛为对于每一条边 (u,v)，用 disu+wu,v 更新 disv。我们断言每轮

至少有一个节点的最短路被更新。松弛 n−1 轮即可。

正确性证明：设源点为 1。在 1→u 的最短路 1→p1→⋯→u 中，对于每个

节点 pi，1→p1→⋯→pi 也一定是 1→p 的最短路，反证法易证。所以一个

节点的最短路一定由另一个节点的最短路扩展而来。因为最短路最多有 n−1

条边，而第 i 轮松弛会得到边数为 i 的最短路，故至多只需松弛 n−1 轮。

该算法还可以判断一张图上是否存在负环。如果在第 n 轮松弛时仍有节点的

最短路被更新，那么图存在负环。

算法的时间复杂度为 O(nm)。

1.2 Dijkstra

dijkstra 是基于贪心的最短路算法，适用于非负权图。

称扩展节点 u 为对于 u 的所有出边 (u,v)，用 disu+wu,v 更新 disv。

在已经得到最短路的节点中，取出没有扩展过的距离源点最近（即 dis 最小）

的节点并扩展。因为没有负权边，所以取出的节点的最短路长度单调不降。

如何判断一个节点已经取到了最短路？实际上不需要判断，每次取出的节点恰

取到了其最短路。根据边权非负以及 dijkstra 的贪心算法流程，可以通过归纳

法与反证法证明这一点。

归纳假设已经扩展过的节点 p1,p2,⋯,p 在扩展时均取到了其最短路。pk 为

没有被扩展的 dis 最小的节点。

pk 的最短路一定由 pi(1≤i<k) 的最短路扩展而来，不可能出现

dis(pi)+w(pi,pk+1)+w(pk+1,pk)<dis(pj)+w(pj,pk)(1≤i,j<k) 的情况。

否则由于边权非负，w(pk+1,pk)≥0，所以

dis(pi)+w(pi,pk+1)<dis(pj)+w(pj,pk)，即当前 dis(pk+1)<dis(pk)，与

dis(pk) 的最小性矛盾。

初始令源点的 dis 为 0，假设成立，因此算法正确。

取出 dis 最小的节点的过程可以用优先队列 priority_queue 维护。每次扩展

u 时，若 disu+wu,v<disv，那么将 (v,disu+wu,v) 即节点编号和它更新后的

dis 作为二元组丢进优先队列。尝试取出节点时，以 disu+wu,v 为关键字取

出最小的二元组，则它对应的节点编号就是我们要找的节点。

注意，一个节点可能有多个入边并多次进入优先队列。但当它第一次被取出时，

得到的一定是最短路。为此，需要记录 vis[i] 表示一个节点是否被扩展过。

若当前取出节点已经被扩展过，则忽略。也可以判断是否有当前二元组的第二

个元等于第一个元（节点编号）的 dis，若不等说明当前节点被扩展过了。否

则复杂度将退化为 m2logm。

算法的时间复杂度为 O(mlogm)。

P4779 模板题代码。

//dijkstra

#include <bits/stdc++.h>

using namespace std;

#define pair<int, int> pi;

const int N=1e5+5;

int n,m,s,dis[N];

vector<pi> v[N]

int main(){

cin>>n>>m>>s;

for (int i=1;i<=m;i++){

int n,v,w;

scanf("%d%d%d",&u,&v,&w);

v[u].push_back(make_pair(v,w));

}

memset(dis,0x3f,sizeof(dis));

dis[s]=0;

qriority_queue<pi,vector<pi>,greater<pi>> q;//

优先取权值较小的

pair

q.push(make_pair(0,s));//

注意第一关键字要放到前面

while(!q.empty){

auto t=q.top();

q.pop();

int id=t.second;//

不要搞反了，编号是

second

if (t.first!=dis[id]){

continue;

}

for (auto _ :v[id]){

int it=_.first,d=t.first+_.second;

if(d<dis[it]){

q.push(make_pair(dis[it]=d,it));

}

剩余12页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

世末OIer

粉丝: 0
资源: 1

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

C++图论专题(form Alex_Wei

图论算法库 C++ 语言实现.zip_C++图论_C++图论的库_c++ 图论库_starfish_图论最优路径

图论基础_C++_学习_C++图论_图论方法c++_

aa.zip_C++ 图论的库_bellman_starfish_单源最短路径_图论最小路径

【最新】C++ http 服务端，接收来自http post form_data文件(图片)源码

C++_GUI_Programming_with_Qt_4_中文版

C++之父 的std_lib_facilities.h

21天学通C++(第五版) vs2008程序打包 深入浅出MFC 浙大教材C++达内 C++ 华为C++培训资料 visual c++_MFC

c++面向对象程序设计_杜茂康_课后答案[1-6章]_

C++程序设计_谭浩强_PDF电子书

poco/c++开源库学习资料打包下载

c++ 2017_vc_redist.x64

C++_STL范例大全_教程

C++并行与分布式编程_肖和平2004译.pdf

图论算法.zip_ACM算法_C/C++__ACM算法_C/C++_

找第K短路 c++ 图论

C++ 图论 离散数学

【Visual C++】Code_Note_2

C++ 图论的基本应用

HideProcess完结篇.zip_c++ 进程隐藏_c++隐藏进程_隐藏进程_隐藏驱动_驱动隐藏进程

第十五届蓝桥杯大赛软件赛省赛C++B组题目

C/C++中文参考手册离线最新版

代码随想录-八股文 pdf

第十五届蓝桥杯大赛软件赛省赛-C++A组题目

编译器（gcc、g++）

Qt5.9 C++开发指南.pdf 及示例源码

Qt （高仿Visio）流程图组件开发，源码分享

mingw-w64-install.exe

Qt、QCustomPlot、实时波形绘制、实时曲线绘制

C/C++中文帮助文档

最新资源

C++之父的std_lib_facilities.h

21天学通C++(第五版) vs2008程序打包深入浅出MFC 浙大教材C++达内 C++ 华为C++培训资料 visual c++_MFC

C++ 图论离散数学