图论
程序员文章站
2022-03-25 13:27:42
...
图论
1. 图论基础
-
图 = 顶点 + 边
-
顶点的集合是 V ，边的集合是 E，图G = （V，E）。
-
图大体分为 有向图 和 无向图。
1.1 无向图
-
边没有指向性的图叫无向图。
-
相邻顶点间的序列称为路径 。
-
起点和终点重合的路径称为圈。
-
任意两点间都有连接的图称为连通图。
-
顶点连接的边数叫做这个顶点的度。
-
没有圈的连通图叫树，没有圈的非连通图叫森林。一棵树的边数恰好等于定点数减一。
1.2 有向图
-
以有向图v为起点的边的集合记做 ，以有向图v为起点的边的集合记做 ，___叫做v的出度，—叫做v的入度。
-
没有圈的有向图叫 DAG ，
待补
2.最短路问题
2.1 任意两点间的最短路问题 （ Floyd 算法 ）
O(n3)
DP的思想（待补）
一 .
一步步来，我们刚开始先求任意两点 i ，j 只经过 1 号顶点的最短路长度。d[i] [j] 数组维护两点间的最短距离。
for( int i = 1 ; i <= n ; ++ i ){
for( int j = 1 ; j <= n ; ++ j ){
//考虑两点间距离与过 1 号点的距离那个最小
d[i][j]=min( d[i][j] ,d[i][1]+d[1][j] )
}
}
二 .
接下来再考虑只经过 1 ，2 号顶点的最短路程。我们在一的基础上加上对 2 号顶点的考虑。试想一下，在 一 中 d[i] [j] 保存与 1 号顶点比较后，i , j 间的最短路程。这时再于 2 号顶点比较一下，d[i] [j] 就保存考虑 1，2 号顶点时的最短路程。
for( int i = 1 ; i <= n ; ++ i ){
for( int j = 1 ; j <= n ; ++ j ){
//考虑两点间最短距离与过 1 号点的距离那个最小
d[i][j]=min( d[i][j] ,d[i][1]+d[1][j] )
}
}
for( int i = 1 ; i <= n ; ++ i ){
for( int j = 1 ; j <= n ; ++ j ){
//考虑两点间最短距离与过 2 号点的距离那个最小
d[i][j]=min( d[i][j] ,d[i][1]+d[1][j] )
}
}
三 .
由二可以想象考虑全部顶点时的做法，就是遍历每一个顶点，对它们都考虑一遍。
for(int k = 1 ; k <= n ; ++ k){
for( int i = 1 ; i <= n ; ++ i ){
for( int j = 1 ; j <= n ; ++ j ){
//考虑两点间距离与过 k 号点的距离那个最小
d[i][j]=min( d[i][j] ,d[i][1]+d[1][j] );
}
}
}
四 .
刚学理解还不够，下面是完整代码。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MA=1e3+5;
const int INF=1e8+5;
int dis[MA][MA];//最短路距离
int V,E;//顶点数，边数
void Floyd(int n)
{
//算法核心代码
for(int k = 1 ; k <= n ; ++ k){
for( int i = 1 ; i <= n ; ++ i ){
for( int j = 1 ; j <= n ; ++ j ){
//考虑两点间距离与过 k 号点的距离那个最小
dis[i][j]=min( dis[i][j] ,dis[i][k]+dis[k][j] );
}
}
}
}
int main()
{
cin>>V>>E;//输入顶点数，边数
int a,b,c;
//初始化最短距离
for(int i=0;i<=V;++i){
for(int j=0;j<=V;++j){
if(i==j)
dis[i][j]=0;
else
dis[i][j]=INF;
}
}
//输入所有边的情况，起始点，终点，权值
for(int i=1;i<=E;++i){
cin>>a>>b>>c;//i,j,cost(权值)
dis[a][b]=c;//有向图
}
Floyd(V);
//输出
for(int i=1;i<=V;++i){
for(int j=1;j<=V;++j){
if(dis[i][j]!=INF)cout<<dis[i][j];
else cout<<"#";//不通
}
cout<<endl;
}
return 0;
}
时间复杂度 O( |V|3 ) 。
2.2 单源最短路问题 1 （Bellman - Ford 算法 ）
O( NE ) 与边有关，不适合稠密图使用
Bellman - Ford 算法是通过松弛操作来实现的。先说一下松弛操作，所谓松弛操作就是更新任意顶点距离源顶点的最短距离。
原来用一根橡皮筋连接a、b两点，现在有一点v到b的距离更短，则把橡皮筋的a点换成v点，使得v、b连接在一起。这样缓解橡皮筋紧绷的压力，使其变得松弛，即松弛操作。
Bellman - Ford 算法就是遍历每一条边，对每一条边进行松弛操作，最后dis[ i ] 就保存第 i 顶点到源顶点的最小距离。
算法步骤
- 准备 ：nodenum 节点数 ，edgenum 边数 , 源起点 original , 结构体数组 edge[ ] 保存边的数据（起点，终点，权值），pre[ ]数组 保存路径 ， ok 控制while循环结束，flag 标记是否有负权。
- 初始化：dis[] ,pre[]
- while循环求解，维护dis[ ],pre[ ] 数组
- 判断是否有负权回路。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MA=1e3+5;
const int INF=1e8+5;
struct Edge //边的情况
{
int st; //起点
int en; //终点
int cost; //权值
}edge[MA];
int nodenum,edgenum,original; //顶点数，边数，源起点
int dis[MA];//各个顶点距离源起点最短路距离
int pre[MA];//路径
bool Bellman_Ford()
{
int ok;//控制循环结束
for(int i=1;i<=nodenum;++i)
dis[i]=(i==original? 0 : INF );//初始化dis[]
pre[original]=-1;//设置路径终点标志
while(true){
ok=1;
//对每条边进行松弛操作
for(int i=1;i<=edgenum;++i){
if(dis[edge[i].en]>dis[edge[i].st]+edge[i].cost){
dis[edge[i].en]=dis[edge[i].st]+edge[i].cost;
pre[edge[i].en]=edge[i].st;
ok=0;
}
}
if(ok) break;
}
//判断是否有负权回路
bool flag=true;
for(int i=1;i<=edgenum;++i){
//负权回路的特点，沿着回路最短路距离会一直减小。利用这个特点判断。
if(dis[edge[i].en]>dis[edge[i].st]+edge[i].cost){
flag=0;
break;
}
}
return flag;
}
//输出路径函数
void print_path(int x)
{
vector<int>path;
//不断沿着 pre[ ] 走到 x==original，将路径保存在path中;
for( ; x != -1 ; x=pre[x]) path.push_back(x);
//因为刚才按前驱节点保存路径，所以路径是反向的，用reverse（）函数将路径正向。
reverse(path.begin(),path.end());
for(vector<int>::iterator it=path.begin();it!=path.end();++it){
cout<<*it<<" ";
}
cout<<endl;
}
int main()
{
cin>>nodenum>>edgenum>>original;
for(int i=1;i<=edgenum;++i){
cin>>edge[i].st>>edge[i].en>>edge[i].cost;
}
if(Bellman_Ford()){//没有负权回路就输出每一个节点到源节点的最小距离和路径。
for(int i = 1; i <= nodenum; ++i){ //每个点最短路
printf("%d\n", dis[i]);
printf("Path:");
print_path(i);
}
}
else printf("have negative circle\n");
return 0;
}
例如 ：
2.3 单源最短路问题 2（ Dijkstra 算法 ）
O(n2)
Dijkstra算法不能处理含有负边的情况。因为它利用广度优先搜索的思想，如过含有负边，dis[ i ] 会在更新中不断变小，无法结束。
思路：（大部分参考其他博客）
- 设置两个集合 S ，U 。S 为 已找到最短距离的顶点的集合，初始时只有源顶点，U 为其他顶点的集合。
- 按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。
- 重点需要理解这句拗口的”按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度”
- 实际上，Dijkstra 算法是一个排序过程，就上面的例子来说，是根据A到图中其余点的最短路径长度进行排序，路径越短越先被找到，路径越长越靠后才能被找到，要找A到F的最短路径，我们依次找到了
- 实际上，Dijkstra算法是一个排序过程，就上面的例子来说，是根据A到图中其余点的最短路径长度进行排序，路径越短越先被找到，路径越长越靠后才能被找到，要找A到F的最短路径，我们依次找到了
A–> C 的最短路径3
A–> C –> B 的最短路径5
A–> C –> D 的最短路径6
A–> C –> E 的最短路径7
A–> C –> D –> F 的最短路径9
底下的Dijkstra算法还未调试好，勿看！！！
#include<bits/stdc++.h>
using namespace std;
const int MA=1e3+5;
const int INF=1e8+5;
int cost[MA][MA];
int nodenum,edgenum,original;
int dis[MA]; //最小距离
bool vis[MA]; //是否使用标记
int pre[MA]; //最小路径
//求从出发点到其他点的最短距离。
void Dijkstra()
{
//初始化
fill(dis,dis+nodenum,INF);
fill(vis,vis+nodenum,false);
dis[original]=0;
int t=-1;
//循环
while(true){
int k=-1;//保存最小距离顶点
for( int i=1 ; i<=nodenum ; ++i ){
if( !vis[i] && ( k==-1 || dis[k]>dis[i] ) )
k=i;
}
if(k==-1)break;
vis[k]=true;
pre[k]=t;//保存前驱节点，pre[original]=-1;
t=k;
for(int i=1;i<=nodenum;++i){
dis[i]=min(dis[i],cost[k][i]+dis[k]); //更新各个顶点到源顶点的最小距离
}
}
}
void print_path(int x)
{
vector<int>path;
path.clear();
for(;x!=-1;x=pre[x]){
path.push_back(x);
}
//reverse(path.begin(),path.end());
for(vector<int>::iterator it=path.begin();it!=path.end();++it){
cout<<*it<<" ";
}
cout<<endl;
}
int main()
{
cin>>nodenum>>edgenum>>original;
int a,b,c;
//初始化cost数组，使不相邻的顶点间的距离是INF
for(int i=1;i<=nodenum;++i){
for(int j=1;j<=nodenum;++j){
cost[i][j]=INF;
}
}
for(int i=0;i<edgenum;++i){
cin>>a>>b>>c;
cost[a][b]=c;//有向图
}
Dijkstra();
for(int i=2;i<=nodenum;++i){
printf("node：%d dis：%d\n",i,dis[i]);
printf("path：\n");
print_path(i);
cout<<endl;
}
return 0;
}
/*
5 6 1
1 2 2
1 3 3
2 4 1
4 3 2
4 5 3
3 5 5
*/
/*天梯赛 L2-001 紧急救援 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MA=1e3;
const int INF=1e8;
int city,road,st,en;
int dis[MA],cost[MA][MA],par[MA],ju[MA],sum[MA];
int ans[MA];
bool vis[MA];
void Dijkstra()
{
//初始化
fill(dis,dis+city,INF);
fill(par,par+city,INF);
fill(vis,vis+city,false);
for(int i=0;i<city;++i)
par[i]=i;
dis[st]=0;
par[st]=st;
ans[st]=1;
while(1){
int k=-1;
for(int i=0;i<city;++i)
if(!vis[i]&&(k==-1||dis[k]>dis[i]))k=i;
if(k==-1)break;
vis[k]=true;
sum[st]=ju[st];
for(int i=0;i<city;++i){
if(cost[k][i]==INF)continue;
if(dis[i]>dis[k]+cost[k][i]){
par[i]=k;
dis[i]=dis[k]+cost[k][i];
sum[i]=sum[k]+ju[i];
ans[i]=ans[k];
}
else if(dis[i]==dis[k]+cost[k][i]){
ans[i]+=ans[k];
if(ju[i]+sum[k]>sum[i]){
par[i]=k;
dis[i]=dis[k]+cost[k][i];
sum[i]=ju[i]+sum[k];
}
}
}
}
}
void print_tu(int s,int e)
{
vector<int>path;
for(int j=en;par[j]!=j;j=par[j]){
path.push_back(j);
}
path.push_back(st);
reverse(path.begin(),path.end());
cout<<ans[e]<<" "<<sum[e]<<endl;
for(vector<int>::iterator it=path.begin();it!=path.end();++it){
if(it!=path.end()-1)
cout<<*it<<" ";
else cout<<*it<<endl;
}
}
int main()
{
cin>>city>>road>>st>>en;
for(int i=0;i<city;++i)
cin>>ju[i];
for(int i=0;i<city;++i){
for(int j=0;j<city;++j)
cost[i][j]=INF;
}
int a,b,c;
for(int i=0;i<road;++i){
cin>>a>>b>>c;
cost[a][b]=c;
cost[b][a]=c;
}
Dijkstra();
print_tu(st,en);
return 0;
}
使用邻接矩阵实现Dijkstra算法的复杂度为O( |V|2) ，使用邻接表的话这部分复杂度是O(|E|)，但每次要枚举所有的顶点来查找下一个使用的顶点，所以最终复杂度依然为O( |V|2) 。
堆优化： 把每个顶点当前的最短距离用堆维护。复杂度为O(|E|*log|V|)。
2.4 SPFA算法
SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
这个算法简单地说就是队列优化的Bellman-Ford算法，利用了每个点不会更新次数太多的特点发明的此算法。
==待补
推荐阅读
-
Educational Codeforces Round 37 (Rated for Div. 2) E. Connected Components?（图论+连通块+bfs）
-
2020.4.29省选模拟赛 A B C（容斥、图论计数DP、树套树+set）
-
【luogu3371】【图论】【最短路】【模板】单源最短路径（弱化版）
-
图论算法——无向图的邻接链表实现
-
1107 Social Clusters (30分)图论求连通分量
-
图论算法----Tarjan求无向图双连通分量及拓展
-
图论：连通分量和强连通分量
-
图论算法讲解--最短路--Dijkstra算法
-
9.11图论DAY 1
-
图论模型（Dijkstra算法和Floyd算法）