图论入门(二)

图论入门(二)

0 说明

以下的算法复杂度分析中,n为图中点的数量,m为图中边的数量

1 最短路

1.1 介绍

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:

  • 确定起点的最短路径问题(也称单源):即已知起始结点,求最短路径的问题。适合使用Dijkstra算法。
  • 确定终点的最短路径问题:与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
  • 确定起点终点的最短路径问题:即已知起点和终点,求两结点之间的最短路径。
  • 全局最短路径问题(也称多源):求图中所有的最短路径。适合使用Floyd算法。

这里讲述四种最短路算法:BFS,Floyd算法,Dijkstra算法,SPFA。

1.2 无边权-BFS

当图没有边权时可以使用BFS来求最短路径:

  • 单源:从源点直接BFS即可。
  • 多源:类似单源,多次处理即可。

BFS的单源处理时间复杂度是$O(n)$。多源处理是$O(n^2)$

1.3 多源-Floyd

Floyd算法是一个可以处理多源的最短路算法,它可以正确处理有向图或负权(但不可存在负权回路)的最短路径问题。Floyd算法基于动态规划思想。

  • 状态:使用三维数组F,F[k][i][j]表示经过1~k号结点,结点i到结点j的最短路
  • 转移方程:F[k][i][j]=min(F[k-1][i][j],F[k-1][i][k]+F[k-1][k][j])
  • 初始条件:F[0][i][j]表示初始权值(INF

从结点i到结点j的最短路径只有2种可能,第一种是直接从i到j,第二种是从i经过若干结点k到j。F[0][i][j]为结点i不经过任何结点到结点j的最短路(也就是连接它们的边的边权),如果不存在则把它赋值为INF,然后对于每一个结点k,我们检查F[k-1][i][k]+F[k-1][k][j]<F[k-1][i][j]是否成立,如果成立,证明从结点i到结点k再到结点j的路径比结点i经过结点k-1(k=0表示不经过任何结点)再到结点j的路径短,此时将F[k][i][j]赋值为F[k-1][i][k]+F[k-1][k][j],反之还是赋值为F[k-1][i][j]。这样一来,假设有n个结点,遍历完所有结点k,F[n][i][j]中记录的便是结点i到结点j的最短路。

对于上图,求结点1到结点5最短路。首先需要对矩阵进行初始化,然后开始遍历每个结点k(1 ~ 5),求经过该节点的结点i(1~ 5)到结点j(1 ~ 5)的距离。每次都更新了结点i到结点j的最短路,最终得到答案28。

如何实现?请看代码。

  • 例1.3.1
int f[maxn][maxn][maxn];

int main()
{
    //这里要写初始化
    for (int k=1;k<=n;k++)    // 注意顺序小心翻车  
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j]);
}

可以看出空间复杂度为$O(n^3)$,这是非常大的,maxn差不多在几百的时候就已经快要MLE了。可以发现,f[k][...][...]仅与F[k-1][...][...],因此可以像背包问题那样将第一维省去,变成二维数组。

  • 例1.3.2(空间优化)
int f[maxn][maxn];

int main()
{
    //这里要写初始化
    for (int k=1;k<=n;k++)    // 注意顺序小心翻车  
        for (int i=1;i<=n;i++)  
            for (int j=1;j<=n;j++)  
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

经过空间优化的Floyd算法的时间复杂度为$O(n^3)$,空间复杂度为$O(n^2)$

1.4 经典单源-Dijsktra

Dijkstra算法,是使用类似广度优先搜索的方法解决赋权图的单源最短路径问题的一种算法。算法基于贪心思想。绝大多数的Dijkstra算法不能有效处理带有负权边的图。

先介绍一下Dijkstra算法的原理。首先是创建数组与初始化:

  1. 创建一个数组Fvis,F[x]存储从源结点到结点x的最短路,vis[x]用于判断结点x是否被访问过。
  2. 设源节点为s,将F[s]初始化为0,其他结点初始化为INF

接下来进行操作,请看伪代码:

while (还有未标记的点)
{
    选出F[]最小的那个结点,更新vis[];
    从这个结点出发,更新周围点的距离;
}

这就是Dijkstra算法的操作过程,如果感觉不是很清楚,可以看看下面的动图。(演示的是求a到b的最短路)

明白了基本原理之后,我们来证明一下这个贪心的正确性与最优性。

正确性可以很明显的看出,直接连接到源结点的所有结点权值最小的那个的权值就是该结点最短路。如何证明最优呢?如果下一个最小的结点一定在当前已选出的结点的更新列表里,那么就可以保证最优。如何证明这句话?我们用反证法,假设的下一个最小的结点x确不是在当前已选出的结点的更新列表里,而是一个其他结点k,那么必有F[k]>F[x](结点x是下一个最小的结点,更新列表是之前的最小的结点),那么F[k]加上结点k与结点x的距离就更加大于F[x],所以反证得出这句话是成立的。

由上图可以看得出来Dijkstra算法非常类似BFS。现在介绍如何实现代码,Dijkstra有两种基本实现方式,分别为基本枚举二叉堆优化

  • 基本枚举

这种方法就是把所有点都跑一遍。一共要跑n次,一次要从n个结点中找到最小的结点,所以这种方法的时间复杂度为$O(n^2)$。请看代码。

  • 例1.4.1
struct Edge
{
    int v;
    int w;
    int next;
}edge[1000005];

int head[200005];
int cnt;
bool vis[200005];    //有无访问
unsigned int F[200005];    //存最短路

void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

int main()
{
    int n,m,s;
    cin>>n>>m>>s;

    for (int i=1;i<=n;i++) F[i]=INT_MAX;    //初始化

    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }

    int cur=s;
    F[s]=0;
    long long minn;

    while(!vis[cur])
    {
        vis[cur]=1;
        for(int i=head[cur];i!=0;i=edge[i].next)
        {
            if(!vis[edge[i].v]&&F[edge[i].v]>F[cur]+edge[i].w)
                F[edge[i].v]=F[cur]+edge[i].w;
        }

        minn=INT_MAX;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&minn>F[i])    //取新的最小值
            {
                minn=F[i];
                cur=i;
            }
        }
    }

    for(int i=1;i<=n;i++)
        cout<<F[i]<<' ';
    return 0;
}
  • 二叉堆优化

所谓二叉堆优化可以理解为就是用优先队列(类似二叉堆)来优化每次选取最小的F[]的过程,所以这种方法的时间复杂度为$O((n+m)logm)$。请看代码。

  • 例1.4.2
struct Edge
{
    int v;
    int w;
    int next;
}edge[1000005];

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;    //优先队列相当于二叉堆
int head[200005];
int cnt;
bool vis[200005];
int F[200005];

void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

int main()
{
    int n,m,s;
    cin>>n>>m>>s;

    for (int i=1;i<=n;i++) F[i]=INT_MAX;    //初始化

    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    
    F[s]=0;
    q.push(make_pair(0,s));
    while (!q.empty())  
    {
        int x=q.top().second;
        q.pop();    //在判断之前先pop
        if (vis[x]) continue;
        vis[x]=1;

        for (int i=head[x];i;i=edge[i].next) 
        {
            if(F[edge[i].v]>F[x]+edge[i].w)
            {
                F[edge[i].v]=F[x]+edge[i].w;
                q.push(make_pair(F[edge[i].v],edge[i].v));
            }
        }
    }

    for (int i=1;i<=n;i++)
        cout<<F[i]<<' ';
    return 0;
}

1.5 玄学单源-SPFA

SPFA,国际上一般认为是队列优化Bellman-Ford算法,是一个用于求解有向带权图单源最短路的算法。这一算法被认为在随机的稀疏图上表现出色,并且适用于带有负边权的图。然而SPFA在最坏情况的时间复杂度与Bellman-Ford算法相同,因此在非负边权的图中仍然最好使用Dijkstra算法。先来了解一下Bellman-Ford算法

Bellman–Ford算法,是求解单源最短路径问题的一种算法。它的原理是对图进行n-1次松弛操作,得到所有可能的最短路径。其优于Dijkstra算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,最多高达$O(nm)$。

Bellman-Ford算法和Dijkstra算法类似,都以松弛操作为基础,即估计的最短路径值渐渐地被更加准确的值替代,直至得到最优解。在两个算法中,计算时每个边之间的估计距离值都比真实值大,并且被新找到路径的最小长度替代。 然而,Dijkstra算法以贪心法选取未被处理的具有最小权值的节点,然后对其的出边进行松弛操作;而Bellman-Ford算法简单地对所有边进行松弛操作,共n-1次。在重复地计算中,已计算得到正确的距离的边的数量不断增加,直到所有边都计算得到了正确的路径。这样的策略使得Bellman-Ford算法比Dijkstra算法适用于更多种类的输入。下面来看看Bellman-Ford算法的具体操作:

  • 创建一个数组F,F[x]存储结点x的最短路,源结点F[]设为0,其他设为INF
  • 依次遍历所有边进行松弛这一步是$O(m)$的),共进行n-1次
  • 若仍然存在可以松弛的边,说明存在负环,否则,每个点的权值即为最短路
  • 松弛操作:存在边u->v使F[v]<F[u]+{u到v的距离}时,F[v]=F[u]+{u到v的距离}

先来实际模拟感受以下Bellman-Ford算法是怎么求得最短路的。假设我们所存的边是按照如下的顺序(括号内是边权)[5,15,7,10,6]。

  • 第1次操作:松弛只更新了F[1]和F[2]
  • 第2次操作:松弛更新了F[3],F[5],F[4],F[5](4->5的边又更新了一次)
  • 第3-4次操作:无用操作

再用上图来更好解释为什么最多有n-1次,假设A是起点,并且边以最坏的顺序处理,从右到左,需要n-1步或者说4次计算路径长度。相反地,若边以最优顺序处理,从左到右,算法只需要在一次遍历内就可以完成。

接下来介绍SPFA,SPFA即Bellman-Ford算法+队列优化。来看看SPFA的具体操作:

  • 创建一个数组F,F[x]存储结点x的最短路,源结点F[]设为0,其他设为INF
  • 维护一个队列q,先将源节点push入q
  • 当q非空时,执行以下操作
    • 弹出队首结点x
    • 对连接结点x的边进行松弛操作
    • 若某结点被更新且该结点不在队列中,将其入队
  • 若一个点进队n次,说明存在负环

如果清楚了Bellman-Ford算法的操作,那么理解SPFA也是没有任何问题的。SPFA的正确性是显然的:我们可以知道,如果要松弛一条边,那么这条边连接的一个结点必然是更新过的,所以SPFA是正确的。请看代码。

  • 例1.5.1
struct Edge
{
    int v;
    int w;
    int next;
}edge[1000005];

queue<int> q;
int head[200005];
int cnt=0;
bool vis[200005];    //有无访问
unsigned int F[200005];    //存最短路

void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

int main()
{
    int n,m,s;
    cin>>n>>m>>s;

    for (int i=1;i<=n;i++) F[i]=INT_MAX;    //初始化

    for(int i=0;i<m;i++)
    {
	    int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }

    F[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;

        for(int i=head[x];i;i=edge[i].next)
            if(F[edge[i].v]>F[x]+edge[i].w)
            {
                F[edge[i].v]=F[x]+edge[i].w;
                if(!vis[edge[i].v])
                {
                    q.push(edge[i].v);
                    vis[edge[i].v]=1;
                }
            }
    }

    for (int i=1;i<=n;i++)
        cout<<F[i]<<' ';
    return 0;
}

SPFA的平均时间复杂度为$O(2m)$,最坏的时间复杂度$O(mn)$。

注:西南交通大学的段凡丁于1994年发布的论文原文中提出该算法的复杂度为$O(km)$,其中k是个比较小的系数,但该结论被证明不适于于所有情况。

2 拓扑排序

2.1 有向无环图

在图论中,如果一个有向图从任意顶点出发无法经过若干条边回到该点,则这个图是一个有向无环图,简称DAG

2.2 拓扑排序

拓扑排序是DAG的专有。有向图的拓扑排序是其顶点的线性排序,使得对于从顶点u到顶点v的每个有向边u->v,u在排序中都在v之前。也就是说排完序后,序列中的某个元素(顶点)不会有到其前一个元素(顶点)的边。

对于这个图,其拓扑排序为[5,3,7,8,10,11,9,2]其中在同一位的有[5,3,7],[8,10,11],[9,2]。

2.3 卡恩算法

卡恩于1962年提出了该算法。简单来说,假设L是存放结果的列表,先找到那些入度为零的节点,把这些节点放到L中,因为这些节点没有任何的父节点。然后把与这些节点相连的边从图中去掉,再寻找图中的入度为零的节点。代码如下。

  • 例2.3.1
struct Edge
{
    int v;
    int next;
}edge[1000005];

int head[200005];
int cnt;
int vis[200005],d[200005],ans[200005];
int t;

void add(int u,int v)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
    d[v]++;
}

void topological_sorting(int x)
{
    ans[t++]=x;
    vis[x]=1;

    for (int i=head[x];i;i=edge[i].next)
    {
        d[edge[i].v]--;    //删边
        if (!vis[i]&&!d[edge[i].v])
            topological_sorting(edge[i].v);
    }
}

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
    }

    for (int i=1;i<=n;i++)
        if (!vis[i]&&!d[i])
            topological_sorting(i);

    for (int i=0;i<n;i++)
        cout<<ans[i]<<' ';
    return 0;
}

感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。