图论

Part 1 图

Part 1.1 简介

一张图 $G$ 由若干个点和连接这些点的边构成。称点的集合为 点集 $V$，边的集合为 边集 $E$，记 $G=(V,E)$。

Part 1.2 图的种类

图大体上分为两种：边没有指向性的图称为无向图，有指向性的图称为有向图。

我们可以给点和边赋予属性，例如权值（cost）。边上带有权值的图称为带权图。

途径：连接一串结点的序列称为 途径，用点序列 $v_{0..k}$​ 和边序列 $e_{1..k}$ 描述，其中 $e_i=(v_{i-1},v_i)$。通常写为 $0​→v_1​→⋯→v_k$​。

连通：对于无向图的两点 $u,v$，若存在途径使得 $v_0=u$ 且 $v_k=v$，则称 $u,v$ 连通。

弱连通：对于有向图的两点 $u,v$，若将有向边改为无向边后 $u,v$ 连通，则称 $u,v$ 弱连通。

连通图：任意两点连通的无向图称为 连通图。

弱连通图：任意两点弱连通的有向图称为 弱连通图。

简单图：不含重边和自环的图称为 简单图。

基图：将有向图的所有有向边替换为无向边得到的图称为该有向图的 基图。

有向无环图：不含环的有向图称为 有向无环图，简称 DAG（Directed Acyclic Graph）。

稀疏图 / 稠密图： $|E|$ 远小于 $|V|^2$ 的图称为 稀疏图，$|E|$ 接近 $|V|^2$ 的图称为 稠密图。

约定

一般记 $n$ 表示点集大小 $|V|$，$m$ 表示边集大小 $|E|$。

Part 1.3 度

有向图中，顶点的度分为入度和出度。

• 入度：以该顶点为头的弧的数目；
• 出度：以该顶点为尾的弧的数目。

Part 2 图的存储

Part 2.1 邻接矩阵

邻接矩阵使用 $n^2$ 的二维数组来表示图。$g_{i,j}$ 表示点 $i$ 与点 $j$ 是否有边相连。

Part 2.2 邻接表

Part 2.2.1 vector存图

在邻接矩阵中，有很多的空间被浪费了。使用 vector 可以节省很多空间，使得空间复杂度达到 $\mathcal{O}(m)$。

vector<int> g[100010]; //定义

//设有一条边为 u -> v

g[u].push_back(v); //存边

//设从u点开始遍历

for(int i=0;i<g[u].size();i++)
{
    int v=g[u][i]; // u -> v
    // ...
}

Part 2.2.2 链式前向星

前置知识：链表

使用 vector 存图常数大，因此我们使用链式前向星来实现邻接表。

建立结构体：

struct edge
{
    int to,w,nxt;
};

其中 $to$ 为终点，$w$ 为权值，$nxt$ 为下一条边的存储位置。

另外一个数组 $head$，表示以 $i$ 为起点的第一条边存储的位置。由于在插入链表的时候使用 头插法，所以在链式前向星是以倒序存储的。

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

遍历：

for(int i=head[u];i;i=a[i].nxt)
	// ...

Part 3 最短路

Part 3.1 Dijkstra

Part 3.1.1 Dijkstra 朴素算法

洛谷 P3371 【模板】单源最短路径（弱化版）

Dijkstra 算法

Dijkstra 算法的流程如下：

1. 初始化 $dist[1]=0$，其余节点的 $dist$ 值为正无穷大。
2. 找出一个未被标记的、 $dist[x]$ 的最小节点 $x$，然后标记节点$x$。
3. 扫描节点 $x$ 的所有出边 $(x,y,z)$，若 $dist[y]>dist[x]+z$，则使用 $dist[x]+z$ 更新 $dist[y]$。
4. 重复上述 2~3 两个步骤，知道所有节点都被标记。

Dijkstra 算法基于贪心思想，它只适用于所有边的长度都是非负数的图。Dijkstra 算法的时间复杂度为 $\mathcal{O}(n^2)$。

struct edge{
	int z,w;
};
int n,m,s,u,v,w,dis[100010],vis[100010];
vector<edge> a[100010];
void dijkstra(int s)
{
	fill(dis+1,dis+1+n,INT_MAX);
	dis[s]=0;
	for(int i=1;i<n;i++)
	{
		int x=0;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&(x==0||dis[j]<dis[x]))
				x=j;
		if(x==0) return ;
		vis[x]=1;
		for(int j=0;j<a[x].size();j++)
			if(!vis[a[x][j].z])
				dis[a[x][j].z]=min(dis[a[x][j].z],dis[x]+a[x][j].w);
	}
}

Part 3.1.2 Dijkstra 堆优化

观察 Dijkstra 的流程，我们发现步骤2可以优化。

我们可以用堆对 $dist$ 数组进行维护，用 $\mathcal{O}(\log n)$ 的时间取出堆顶元素并删除，用 $\mathcal{O}(\log n)$ 的时间遍历每条边，总时间复杂度为 $\mathcal{O}((n+m) \log n)$。

struct edge
{
	int z,w;
	bool operator <(const edge &x)const
	{
		return x.w<w;
	}
};
int n,m,s,u,v,w,dis[100010],vis[100010];
vector<edge> a[100010];
priority_queue<edge> q;
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	q.push(edge{s,0});
	dis[s]=0;
	while(!q.empty())
	{
		int x=q.top().z;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=0;i<a[x].size();i++)
		{
			int y=a[x][i].z,l=a[x][i].w;
			if(dis[y]>dis[x]+l&&!vis[y])
			{
				dis[y]=dis[x]+l;
				q.push(edge{y,dis[y]});
			}
		}
	}
}

Part 3.2 Bellman-Ford & SPFA

Part 3.2.1 Bellman-Ford算法

将所有边进行 $n-1$ 次松弛操作，在求解它的过程中，每次循环都要修改所有顶点对应的 $dist$ 数组的值，最短路径长度直到算法结束才能确定。算法的时间复杂度为：$\mathcal{O}(nm)$。

void BellmanFord(int s)
{
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(dis[j]==0x3f3f3f3f) continue;
			for(int k=0;k<a[j].size();k++)
				if(dis[a[j][k].z]>dis[j]+a[j][k].w)
					dis[a[j][k].z]=dis[j]+a[j][k].w;
		}
	}
}

Part 3.2.2 SPFA算法

SPFA 算法，即 Shortest Path Faster Algorithm，最短路径快速算法。

SPFA 算法在 Bellman-Ford 算法上进行了优化，将待更新的 $dist$ 数组的对应顶点存进队列里，每次取出队首元素 $u$，将与 $u$ 相连的节点进行松弛，如果节点 $y$ 不在队列里，且 $dis[y]$ 可以更新，那么将节点 $y$ 入队。

与 BFS 不同的是，SPFA 算法可以将一个节点多次入队。

SPFA 算法的时间复杂度为 $\mathcal{O}(km)$ ，其中 $k$ 是一个较小的常数。但是，如果题目数据故意卡 SPFA ，那么 SPFA 的时间复杂度会退化为 $\mathcal{O}(km)$。相较于 SPFA，Dijkstra 算法更为稳定。