初级图论

发表于 2022-11-27 更新于 2023-02-23 分类于算法 Waline：

摘要：初级图论，Dijkstra，待更新

前言

1.图的定义及基本概念

假设由一个图 $G=(V,E)$ ， $V$ 是点集，存储了图中所有的点； $E$ 是边集，存储了图中所有的边。

说白了，你可以将图理解成有几个地点，其中某些地点间有道路连通。而这些道路，可能是单向道，也可能是双向道。这些地点对应图中的点，道路对应图中的边。

如果每条道路都是单向道，即边都是单向的，那么称这张图为有向图。否则称这张图为无向图。当然，在有向图中，可能存在两点间有两条边，使两点可以互相连通。

有时两点间有多条边连接，被称为重边。
有时存在从一个点到它自己的边，称为自环。
每条边可能会对应一个数值，称为边权。
每个点可能会对应一个数值，成为点权。

对于无向图：

一个点所连边的数量叫做度。

对于有向图：

通向这个点的边的数量叫做入度。
从这个点出发的边的数量叫做出度。

例如，有如下两张图。左图为无向图，右图为有向图。

求左图点 $1$ 的度，右图点 $2$ 的入度、点 $1$ 的出度。

答案：（1）3，（2）2，（3）2 （点击 ctrl+a 查看答案）

2.本文会用到的一些术语

本文中，我们会用 $u\to(v,c)$ 表示一条从 $u$ 通向 $v$ 的边，权值为 $c$ 。

一、常用的存图方式

1.邻接矩阵

一个二位数组 $g$ ，其中 $g_{i,j}$ 表示从 $i$ 到 $j$ 的边权。

空间复杂度 $O(n^2)$ 。

缺点是空间复杂度极大，不能存储重边。但是，要查询一条从 $i$ 通向 $j$ 的边，时间复杂度为 $O(1)$ ，更优于其它方式。

2. vector

通常是 vector<pair<int,int> > g[N] 的形式。其中 $g_i$ 存储了 $i$ 点的所有出边。

空间复杂度 $O(N)$ 。

3. 邻接表

空间复杂度为 $O(n)$ 。但邻接表只用几个静态数组便可以存图，稍优于 vector。且邻接表更便于查询反向边。

$head_i$ 存储 $i$ 点的所有出边中，存储位置做靠右的那一条。

$nxt_i$ 表示与 $i$ 边相同入点的，存储在它左侧的，最靠近它的边（如果不存在，则 $nxt_i=1$ ）。

$to_i$ 表示 $i$ 边的出点。

$qz_i$ 表示 $i$ 边的权值。

每次添加一条边时，将此边的 $nxt$ 值指向这个入点的上一条边，并将此边入点的 $head$ 值设为此边。

int head[N],to[M],qz[M],nxt[M];
int cnt;
void add_edge(int x,int y,int z)//添加一条边：从x通向y，权值为z
{
    cnt++;
    to[cnt]=y;//将cnt边的出点设为y
    qz[cnt]=z;//将cnt边的权值设为z
    nxt[cnt]=head[x];//把nxt[cnt]指向上一条x的出边
    head[x]=cnt;//将cnt暂时设为x的出边中，存储位置最靠右的边
}

//遍历i点的所有出边（相当于从右向左将i点的出边扫了一遍）
for(int j=head[i];j;j=nxt[i]) //出边通向的点：to[j]，出边的权值：qz[j]

二、单源最短路径问题

单元最短路径问题（简称 SSSP）。

顾名思义，此类问题给出一个起点，求出它到所有点的最短路径。

1、Dijkstra 算法

Dijkstra，基于贪心的思想，可用来解决单源最短路径问题。但前提是所有边权都非负。

· 大致思路

创建 $dis$ 数组，其中 $dis_i$ 表示从起点 $s$ 到点 $i$ 的最短距离。
维护两个顶点集合 $S$ 与 $Q$ 。其中 $S$ 中点的 $dis$ 值已经为最终值，无法继续修改。
将原点 $s$ 的 $dis$ 值设为 $0$ ，其他点的 $dis$ 值设为 $+\infty$ 。
取出 $Q$ 集合中 $dis$ 值最小的点 $u$ ，将它放入 $S$ 中，并遍历这个点所有的出边 $p \to (q,c)$ ，将 $q$ 的 $dis$ 值更新为 $\max(dis_q,dis_p+c)$ 。
重复执行步骤 4，直到 $Q$ 集合为空。

下面这张动图完美地解释了 Dijkstra 算法的执行过程（ $0$ 为起点，圆圈里的数字为点的编号，红色的数字表示 $dis$ 值）：

（图片来源于网络）

关于 Dijkstra 算法的正确性

显然，每次从集合 $Q$ 中取出的点的 $dis$ 值只要不会再次被更新即可。

假设集合 $Q$ 中 $dis$ 值最小的点为 $p$ 。现在将它从 $Q$ 中取出。

集合 $S$ 中的每一个点都曾用来更新过 $p$ 点的 $dis$ 值，因此 $p$ 点的 $dis$ 值不会再变小。

假设集合 $Q$ 中的点 $q$ 与点 $p$ 相连，因为 $dis_p\le dis_q$ ，那么当边权非负时， $dis_q$ 加上边权也一定大于等于 $dis_p$ 。

因此 $p$ 的 $dis$ 值不会再被更新。

而在上面的证明过程中，用到了边权非负的条件。显然，边权为负数时，证明不成立。因此，Dijkstra 只能处理边权全部非负的图。

Dijkstra 的代码实现以及优化

按照上文提到的大致思路模拟即可。代码中使用了 $vis$ 数组。如果 $vis_p$ 为假，则 $p$ 点在 $Q$ 集合中，否则 $p$ 点在 $S$ 集合中。

洛谷 P3371 代码：

#include<bits/stdc++.h>
using namespace std;
#define N 10010
#define M 500010

int n,m,s;
int head[N],to[M],qz[M],nxt[M];
int dis[N];bool vis[N];
#define inf 2147483647
int cnt;
void add_edge(int x,int y,int z)
{
    cnt++;
    to[cnt]=y;qz[cnt]=z;nxt[cnt]=head[x];head[x]=cnt;
}

void dij()
{
    for(int i=1;i<=n;i++) dis[i]=inf;
    dis[s]=0;
    
    for(int i=1;i<=n;i++)
    {
        int u=1,minn=inf;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dis[j]<minn) u=j,minn=dis[j];//找到 Q 集合中 dis 值最小的点
        vis[u]=1;//将它放入 S 集合
        for(int j=head[u];j;j=nxt[j])//遍历 u 点的所有出边
        {
            int v=to[j],c=qz[j];//这条边是 u->(v,c)
            dis[v]=min(dis[v],dis[u]+c);//更新 v 点的 dis 值
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        add_edge(u,v,c);
    }
    dij();
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0; 
}

假设 $n$ 为点数， $m$ 为边数。

在 $\operatorname{dij}$ 函数中，每一次的外层循环，会将一个点放入 $S$ 集合中。所以， $n$ 次循环后，所有的点都会在 $S$ 集合中。循环中“找到 $Q$ 集合中 $dis$ 值最小的点”这个过程的时间复杂度是 $O(n)$ ，所以总体时间复杂度为 $O(n^2)$ 。在从 $Q$ 集合中取出每个点时，遍历了这个点的所有出边，相当于在循环过程中遍历了所有的边。所以严格来说，时间复杂度为 $\Theta(n^2+m)$ 。

这个时间复杂度非常不理想，考虑对它进行优化。而优化的入手点，便是“找到 $Q$ 集合中 $dis$ 值最小的点”这个过程。

可以使用 STL 中的优先队列（priority_queue），每当更新一个点的 $dis$ 值时，就将它的 $dis$ 值放入到队列中。显然，从队列取出的值，一定是 $Q$ 集合中 $dis$ 的最小值。

我们要这样使用优先队列，使其成为小根堆：

struct node
{
    int dis,p;//dis表示这个点的dis值，p表示这个点的编号
    node(int _dis,int _p){dis=_dis,p=_p;}//构造函数
};
struct cmp
{
    bool operator()(node a,node b){return a.dis>b.dis;}//cmp函数，使其成为小根堆
};
priority_queue<node,vector<node>,cmp> Q;//定义优先队列

洛谷 P4779 代码：

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define M 200010
struct node
{
    int dis,p;//dis 表示这个点的 dis 值，p 表示这个点的编号
    node(int _dis,int _p){dis=_dis,p=_p;}//构造函数
};
struct cmp
{
    bool operator()(node a,node b){return a.dis>b.dis;}//cmp 函数，使其成为小根堆
};
priority_queue<node,vector<node>,cmp> Q;//定义优先队列
int n,m,s;
int head[N],to[M],qz[M],nxt[M];
int dis[N];bool vis[N];
#define inf 2147483647
int cnt;
void add_edge(int x,int y,int z)
{
    cnt++;
    to[cnt]=y;qz[cnt]=z;nxt[cnt]=head[x];head[x]=cnt;
}

void dij()
{
    for(int i=1;i<=n;i++) dis[i]=inf;
    dis[s]=0;
    Q.push(node(0,s));//先将 dis 值为 0 的起点放入队列中
    
    while(!Q.empty())
    {
        node t=Q.top();Q.pop();//取出队列中的元素
        int u=t.p;//u 为 Q 集合中 dis 值最小的点
        if(vis[u]) continue;//判断 u 是否在 Q 集合中
        vis[u]=1;//将 u 点放入 S 集合中
        for(int j=head[u];j;j=nxt[j])
        {
            int v=to[j],c=qz[j];
            if(dis[u]+c<dis[v])
            {
                dis[v]=dis[u]+c;
                Q.push(node(dis[v],v));//将 dis 值为 dis[v] 的 v 点放入队列
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        add_edge(u,v,c);
    }
    dij();
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0; 
}

堆优化 dijkstra 的时间复杂度为 $O(m\log n)$ 。

--------待更新--------