欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图论

程序员文章站 2022-03-25 13:27:42
...

图论

1. 图论基础

  1. 图 = 顶点 + 边

  2. 顶点的集合是 V ,边的集合是 E,图G = (V,E)。

  3. 图大体分为 有向图无向图

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 顶点到源顶点的最小距离。

算法步骤

  1. 准备 :nodenum 节点数 ,edgenum 边数 , 源起点 original , 结构体数组 edge[ ] 保存边的数据(起点,终点,权值),pre[ ]数组 保存路径 , ok 控制while循环结束,flag 标记是否有负权。
  2. 初始化:dis[] ,pre[]
  3. while循环求解,维护dis[ ],pre[ ] 数组
  4. 判断是否有负权回路。
#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算法,利用了每个点不会更新次数太多的特点发明的此算法。

==待补