#创作计划#图论算法精讲

༺ཌༀཉི༒白·羊༒༃ༀད༻

2025-09-22 06:18:00

发布于：上海

35阅读

0回复

0点赞

本篇文章讲解图论算法，包括最短路、最小生成树、并查集和基础的 $LCA$

大家请坐稳，我们马上开始。

Part 1 最短路算法

最短路算法是图论中最基础的方法，在各大比赛中都有涉及，本篇将会提到4种最短路算法。

一、定义

最短路问题即求一个带权图中两个节点的最短的路径。

二、 $Dijkstra$ 算法

1.简介

这是图论中最常用的最短路算法，由荷兰计算机科学家 $Edsger W. Dijkstra$ 于 $1956$ 年提出，其核心思想是贪心和广度优先搜索。它解决的是单源最短路问题。

2.核心思想

$Dijkstra$ 算法的核心在于维护一个 $dist$ 数组， $dist[i]$ 表示从起点到 $i$ 号点的最短路。

3.适用范围

非负权图， $Dijkstra$ 算法每个点只松弛一次的特性决定了其无法解决负权问题。

4.朴素 $Dijkstra$ 算法

$Dijkstra$ 算法将节点分为两类：
1. 已确定节点：已经找到从起点到该节点的最短路径的节点集合。
2. 未确定节点：尚未找到最短路径的节点集合。
算法流程：
1. 每次从 “未确定节点” 集合中，选择一个距离起点最近的节点。
2. 将其加入 “已确定节点” 集合。
3. 松弛这个新确定节点的所有邻居。
松弛操作（也是该算法最重要的思想）：

检查对于新确定节点 $u$ 的每一个邻居 $v$ ，如果从起点 $s$ 先到 $u$ ，再从 $u$ 到 $v$ 的路径距离，比之前已知的到 $v$ 的距离更短，那么就更新 $v$ 的距离。
核心代码：

if(dist[u]+weight(u, v)<dist[v])
    dist[v]=dist[u]+weight(u,v)

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	int y,w;
};
int n,m,s,vis[1009],dis[1009];
vector<node>graph[1009];
signed main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int a,b,w;
		cin>>a>>b>>w;
		graph[a].push_back({b,w});
	}
	for(int i=0;i<=n;i++)
		dis[i]=1e9;
	dis[s]=0;
	for(int i=1;i<n;i++){
		int u=0;
		for(int j=1;j<=n;j++){
			if(dis[j]<dis[u]&&vis[j]==0)
				u=j;
		}
		vis[u]=1;
		for(auto p:graph[u]){
			if(p.w+dis[u]<dis[p.y])
				dis[p.y]=p.w+dis[u];
		}
	}
	for(int i=1;i<=n;i++)
		if(dis[i]==1e9)
            cout<<-1<<" ";
        else
            cout<<dis[i]<<" ";
	return 0;
}

时间复杂度： $O(n^2+m)$ （一般写作 $O(n^2)$ ）
空间复杂度： $O(n+m)$

5.堆优化 $Dijkstra$ 算法

区别于朴素做法的枚举每个可能松弛的节点，堆优化算法使用堆找到目前最近（最可能松弛）的节点。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int MAXN=1e9;
int n,m,k,u,v,w,dist[5009];
bool vis[5009];
struct node{
    int v,w;
    friend bool operator<(const node&a,const node&b){
        return a.w>b.w;
    }
};
vector<node> graph[N];
void dijkstra(int u){
    priority_queue<node> q;
    for(int i=0;i<=n;i++)
		dist[i]=1e9;
    dist[u]=0;
    q.push({u,0});
    while(q.size()){
        node f=q.top();
        q.pop();
        u=f.v;
        if(vis[u])
			continue;
        vis[u]=1;
        for(auto i:graph[u]){
            if(dist[i.v]>dist[u]+i.w){
                dist[i.v]=dist[u]+i.w;
            	q.push({i.v,dist[i.v]});
            }
        }
    }
}
int main(){
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        graph[u].push_back({v,w});
    }
    dijkstra(k);
    for(int i=1;i<=n;i++){
        if(dist[i]==1e9)
			cout<<-1<<" ";
        else 
			cout<<dist[i]<<" ";
    }
    return 0;
}

时间复杂度： $O(mlogn)$
空间复杂度： $O(n+m)$
$\color{red}{注意在稠密图中，堆优化算法会退化为O(n^2logn),此时应使用朴素算法。}$

6. 练习

三、 $Floyd$ 算法

1.简介

$Floyd$ 算法是一种基于 $dp$ 的思想，是学生们最喜欢的一种基础最短路算法~~也是最慢的~~（竞赛中不常用）

2.核心思想

从节点 $i$ 到节点 $j$ 的最短路径，无非有两种可能：

直接从 $i$ 到 $j$ 。
从 $i$ 经过某些中间节点 $k$ 再到 $j$ 。

$Floyd$ 算法不断尝试和比较这些可能性，逐步优化最短路径的估计值（这也是该算法较慢的原因）。

3.适用范围

$Floyd$ 不适用于存在负权回路的图中。

4. $Floyd$ 算法实现

状态定义：

$d[k][i][j]$ ：表示从节点 $i$ 到节点 $j$ ，仅使用 $1, 2, \cdots, k$ 号节点作为中间节点的所有可能路径中的最短路径长度。
状态转移方程：

对于每一个中间节点 $k$ ，我们检查对于每一对 $(i, j)$ ，是否存在一条更短的路径：

$d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j])$

这个方程的含义：

$d[k-1][i][j]$ ：不使用 $k$ 作为中间节点， $i$ 到 $j$ 的最短路径。

$d[k-1][i][k] + d[k-1][k][j]$ ：使用 $k$ 作为中间节点，路径分解为 $i$ -> $k$ 和 $k$ -> $j$ 两段，这两段路径只使用前 $1$ 到 $k-1$ 号节点作为中间节点。
取这两种情况的最小值。
代码（空间优化版）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n' 
int n,m,q,dp[409][409],u,v,w;
signed main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=i==j?0:1e9;
    while(m--){
        cin>>u>>v>>w;
        dp[u][v]=min(dp[u][v],w);
        dp[v][u]=min(dp[v][u],w);
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
    while(q--){
        cin>>u>>v;
        cout<<(dp[u][v]==1e9?-1:dp[u][v])<<endl;
    }
    return 0;
}

时间复杂度： $O(n^3)$
空间复杂度： $O(n^2)$

5. 练习

四、 $Bellman$ - $Ford$ 算法

1.简介

$Bellman$ - $Ford$ 算法是另一种单源最短路算法，价值在于可以解决负权（回路）问题。

2.核心思想

$Bellman$ - $Ford$ 算法的思想非常直接：

最短路径最多经过 $n-1$ 条边。如果一条从源点 $s$ 到终点 $t$ 的最短路径经过了超过 $n-1$ 条边，那么它必定包含一个环。如果是正环或零环，可以移除它得到更短的路径；如果是负环，则不存在最短路径。

基于这个思想，通过松弛操作对图中的所有边进行 $n-1$ 轮遍历。每一轮遍历都尝试用一条边来更新和优化当前已知的最短距离。经过 $n-1$ 轮后，理论上所有可能的最短路径都已经被找到。这时执行一轮松弛操作，还能有路径被更新，则证明图中存在负权回路。

3.适用范围

$Bellman$ - $Ford$ 算法适用于所有情况

4. $Bellman$ - $Ford$ 算法实现

初始化：
1. 将 $dist[s]$ 设为 $0$ 。
2. 将所有其他节点的 $dist$ 值初始化为 $1e9$ 。
进行 $n-1$ 轮松弛：
1. 对每一轮，遍历图中的所有 $m$ 条边。
2. 对于每条边 $(u, v, w)$ ，执行松弛操作：
核心代码：

if(dist[u]!=1e9&&dist[u]+w<dist[v])
    dist[v]=dist[u]+w;

如果需要检查负权回路，再额外进行一次对所有边的遍历（即第 $n$ 轮松弛），如果发现任何一条边还能进行松弛操作，就可以得出结论：图中存在从源点 $s$ 可达的负权回路。
$\color{red}{注意：每一轮松弛的顺序可能会影响效率，但不影响最终结果的正确性。}$
完整代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,k,u,v,w,dist[5009];
struct node{
    int u,v,w;
};
vector<node>graph;
void Bellman_Ford(int u){
    for(int i=0;i<=n;i++)
		dist[i]=1e9;
    dist[u]=0;
    for(int i=1;i<n;i++){
        bool op=0;
        for(auto p:graph){
            int u=p.u,v=p.v,w=p.w;
            if(dist[u]+w<dist[v])
                dist[v]=dist[u]+w,op=1;
        }
        if(!op)
			return;
    }
}
signed main(){
    cin>>n>>m>>k;
    while(m--){
        cin>>u>>v>>w;
        graph.push_back({u,v,w});
    }
    Bellman_Ford(k);
    for(int i=1;i<=n;i++)
		cout<<(dist[i]!=1e9?dist[i]:-1)<<" ";
    return 0;
}

时间复杂度： $O(nm)$
空间复杂度： $O(n+m)$

5. 练习

五、 $SPFA$ 算法

1.简介

$SPFA（Shortest Path Faster Algorithm）$ 是对于 $Bellman$ - $Ford$ 的队列优化版本，在随机图中时间更优，但容易被卡。

2.核心思想

我们发现， $Bellman$ - $Ford$ 算法中，并不是每一次松弛操作都会有效，只有那些在前一轮松弛中成功更新了最短路径值的点，才有可能引领下一次有效的松弛。

$SPFA$ 对此进行了关键优化：

使用一个队列来维护有可能引起松弛操作的点。只有当某个点 $u$ 的最短距离 $dist[u]$ 被更新变小了，才说明它的出边有可能使其邻居 $v$ 的 $dist[v]$ 也变小。这时，我们才将 $u$ 放入队列，等待后续用它来松弛它的邻居。

这个过程避免了 $Bellman$ - $Ford$ 中大量无用的松弛尝试，使其在平均情况下的时间复杂度远优于 $Bellman$ - $Ford$ 。

3.适用范围

$SPFA$ 适用于所有情况

4. $SPFA$ 算法实现

初始化：
1. 创建 $dist$ 数组， $dist[s] = 0$ ，其余为 $INF$ 。
2. 创建一个队列 $q$ ，将源点 $s$ 入队。
创建一个 $in\_queue$ 数组，标记节点是否已在队列中，防止重复入队。初始时， $in\_queue[s] = True$ 。
(可选，用于检测负环) 创建一个 $count$ 数组，记录每个节点的入队次数，初始为 $0$ 。
主循环：当队列不为空时
1. 从队首弹出一个节点 $u$ ，并标记 $in\_queue[u] = False$ 。
2. 遍历 $u$ 的所有出边。
3. 尝试对边 $(u, v)$ 进行松弛操作。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,k,u,v,w,dist[5009],cnt[5009];
bool vis[5009];
struct node{
    int v,w;
};
vector<node>graph[5009];
void spfa(int u){
    for(int i=1;i<=n;i++)
		dist[i]=1e9,vis[i]=0;
    queue<int>q;
    dist[u]=0;
    q.push(u);
    while(q.size()){
        u=q.front();
        q.pop();
        vis[u]=0;
        cnt[u]++;
        if(cnt[u]>n)
			return;
        for(auto edge:graph[u]){
            int v=edge.v,w=edge.w;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
signed main(){
    cin>>n>>m>>k;
    while(m--){
        cin>>u>>v>>w;
        graph[u].push_back({v,w});
    }
    spfa(k);
    for(int i=1;i<=n;i++)
		cout<<(dist[i]!=1e9?dist[i]:-1)<<" ";
    return 0;
}

平均时间复杂度： $O(km)$ 其中 $k$ 是个很小的常数
最坏时间复杂度： $O(nm)$ 在一些特殊数据，比如网格图中，会退化为 $Bellman$ - $Ford$
空间复杂度： $O(n+m)$

六、小结

算法	$Dijkstra$	$Bellman$ - $Ford$	$SPFA$	$Floyd$
类型	单源最短路径	单源最短路径	单源最短路径	多源最短路径
策略	贪心	动态规划	队列优化	动态规划
时间复杂度	$O(m log n)$	$O(nm)$	$O(km)$	$O(n^3)$
空间复杂度	$O(n+m)$	$O(n+m)$	$O(n+m)$	$O(n+m)$
负权边	❌	✅	✅	✅
负环检测	❌	✅	✅	✅
适用场景	非负权图	负权图	随机图	$n<500$
最佳情况	非负权图	负权图	随机图	$n<500$
最坏情况	无，均可用对应优化	稠密图	特殊图，例如网格图	小数据，大规模查询
实现难度	中等	中等	较难	简单

Part 2 并查集

并查集是图论中一种基础算法，是最小生成树等算法的基础，本篇将会提到3种并查集。

一、定义

并查集是一种用于管理元素分组情况的数据结构。

二、朴素版

1.简介

并查集高效地支持以下两种操作：

合并：将两个元素所在的集合合并为一个集合。
查找：查询某个元素是否在同一集合。

2.核心思想

并查集的核心思想在于用多棵树来表示集合。森林中的每一棵树代表一个集合，树中的每个节点对应一个元素，树的根节点就是这个集合的“代表”。

3.算法流程

初始化：
一开始，我们拥有 $n$ 个元素。通常我们用一个数组 $parent$ 来表示每个元素的父节点。
初始化时，每个元素都是自己的父亲，即每个元素自成一个集合，自己是自己那棵树的根。
查找
即查找元素 $x$ 所在集合的根节点。方法很简单：不断地通过 $parent$ 数组向上查找，直到找到那个父节点指向自己的元素（即 $parent[x] = x$ ），它就是根节点。
合并
即将元素 $x$ 和元素 $y$ 所在的两个集合合并成一个集合，主要有两个步骤：
1. 找到 $x$ 的根节点 $rootx = find(x)$ 和 $y$ 的根节点 $rooty = find(y)$ 。
2. 如果 $rootx=rooty$ ，说明它们本来就在同一个集合里，无需合并。否则将其中一棵树挂到另一棵树的根节点下面。即让 $parent[rootx] = rooty$ 。

4.代码实现

#include<bits/stdc++.h>
using namespace std;
int a[5005];
int f(int x){
	if(a[x]==x)
        return x;
	return f(a[x]);
}
int main(){
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
        a[i]=i;
    for(int i=1;i<=m;i++){
        int z,x;
		cin>>z>>x;
		a[f(z)]=f(x);
	}
	for(int i=1;i<=q;i++){
		int r,l;
		cin>>r>>l;
		if(f(r)==f(l))
            cout<<"Yes"<<endl;
		else
            cout<<"No"<<endl;
	}
}

单次操作时间复杂度：最坏 $O(n)$
空间复杂度： $O(n)$

5. 练习

三、按秩合并

1.简介

在朴素算法中，我们不难发现，在特殊数据下，树会退化为一条链，时间会退化为 $O(n)$ ，无法满足需求，于是按秩合并应运而生。

2.核心思想

我们使用一个额外的数组 $rank$ 来记录每个根节点所代表的树的“高度”的估计值（这就是秩）。

初始时，每个元素都是根节点，自己构成一棵高度为 $0$ 的树，所以 $rank[i] = 0$ 。

$\color{red}{注意：我们只维护根节点的 rank 值，非根节点的rank值没有意义。}$

3.算法流程

在合并两个根节点 $rootx$ 和 $rooty$ 时：
1. 比较它们的秩（ $rank[rootx]$ 和 $rank[rooty]$ ）。
2. 将秩较小的树挂到秩较大的树下。
注意：如果两棵树的秩相等：任意选择一方作为新的根，并将新根的秩加 $1$ 。
为什么相等时要加 $1$ ？
想象两颗高度均为 $h$ 的树。当它们合并时，新树的高度至少为 $h+1$ （将一颗树挂到另一颗的根节点下，整个树的高度必然增加 $1$ ）。

4.代码实现

这段代码请由各位自行完成(doge)。

5. 还是这道

四、路径压缩

1.简介

路径压缩是并查集中一种非常重要的优化技术，它在查找中实施，可以显著提高并查集的效率。

2.核心思想&算法流程

朴素算法通过递归查找根节点，而路径压缩指的是在递归返回的过程中，将路径上每个节点的父节点直接设置为根节点，这样，整个路径被"压缩"了，所有节点都直接指向根。

3.代码实现

这是朴素的 $find$

int f(int x){
	if(a[x]==x)
        return x;
	return f(a[x]);
}

这是路径压缩的 $find$

int f(int x){
	if(a[x]==x)
        return x;
	return a[x]=f(a[x]);
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
int a[5005];
int f(int x){
	if(a[x]==x)
        return x;
	return a[x]=f(a[x]);
}
int main(){
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
        a[i]=i;
    for(int i=1;i<=m;i++){
        int z,x;
		cin>>z>>x;
		a[f(z)]=f(x);
	}
	for(int i=1;i<=q;i++){
		int r,l;
		cin>>r>>l;
		if(f(r)==f(l))
            cout<<"Yes"<<endl;
		else
            cout<<"No"<<endl;
	}
}

5. 还是这道

6.复杂度分析

时间复杂度：并查集的时间复杂度分析比较特殊，它不是一个简单的 $O(log n)$ 或 $O(n)$ ，路径压缩的时间复杂度是由一个增长极其缓慢的函数——反阿克曼函数 $α(n)$ 来描述。至于这个函数有多缓慢呢？在 $n ≤ 2^{65536}$ 时， $α(n) ≤ 5$ 。所以路径压缩并查集的单次操作一般认为是 $O(1)$ 的。
空间复杂度： $O(n)$

Part 3 最小生成树

最小生成树是图论中一种基础方法，考试中会出现很多变体，本篇将会提到两种最小生成树算法。

一、定义

生成树是一个无向连通图的子图。它必须包含原图的所有顶点，但只包含足够形成一棵树的边，并满足以下三个条件：

是连通图：所有顶点都连接在一起。
无环：图中不存在任何环路。
边数 = 顶点数 - $1$ 。

最小生成树就是在一个带权连通无向图中，所有可能的生成树里，边的权重之和最小的那一棵（或那几棵）。

二、 $Kruskal$ 算法

1.简介

$Keuskal$ 算法是基于边的一种最小生成树算法，也是竞赛中最常用的一种。

2.核心思想

从小到大选择不会形成环的边，直到连接所有顶点。

3.算法流程

排序：将图中所有的边按权重从小到大排序。
初始化：创建一个空的集合用于存放最小生成树的边。
遍历：按权重从小到大遍历每条边：
如果当前边连接的两个顶点不在集合的同一个连通分量中（即加入这条边不会形成环），则将这条边加入集合。
如果会形成环，则跳过。
终止条件：当集合中的边数等于顶点数减 $1$ 时，算法结束。
如何判断是否成环？

我们通常使用并查集来高效地判断两个顶点是否属于同一个集合以及把两个点的集合合并。

4.代码实现

#include <bits/stdc++.h>
using namespace std;
struct node{
	int x,y,z;
}a[200009];
bool cmp(const node a,const node b){
	return a.z<b.z;
}
int f[5009];
int n,m;
int find(int x){
	if(f[x]==x)
		return x;
	else
		return f[x]=find(f[x]); 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		f[i]=i;
	for(int i=1;i<=m;i++)
		cin>>a[i].x>>a[i].y>>a[i].z;
	sort(a+1,a+m+1,cmp);
	int cnt=1,sum=0;
	for(int i=1;i<=m;i++){
		if(find(a[i].x)!=find(a[i].y)){
			sum+=a[i].z,cnt++;
            int xx=find(a[i].x),yy=find(a[i].y);
            f[xx]=yy;
        }
	}
	if(cnt==n)
		cout<<sum;
	else
		cout<<"orz";
	return 0;
}

时间复杂度： $O(mlogm)$
空间复杂度： $O(n+m)$

5. 练习

三、 $Prim$ 算法

1.简介

不同于 $Kruskal$ 算法， $Prim$ 算法是基于点的一种最小生成树算法，比较慢。

2.核心思想

从一个顶点开始，每次选择与当前树相连的权重最小的边，并扩展这棵树。

3.算法流程

初始化：
1. 随机选择一个顶点作为起点，加入最小生成树集合。
2. 维护一个数组 $key$ ，记录每个顶点到当前最小生成树的最小权重，初始值为无穷大（起点为 $0$ ）。
3. 维护一个数组 $parent$ ，记录每个顶点是由哪条边连接进来的。
循环扩展：
1. 从未被选择的顶点中，选择一个 $key$ 值最小的顶点 $u$ ，将其加入树中。
2. 遍历顶点 $u$ 的所有邻接顶点 $v$ ，如果边 $(u,v)$ 的权重小于 $v$ 当前的 $key$ 值，则更新 $v$ 的 $key$ 值为这个权重，并记录 $parent[v] = u$ 。
终止条件：所有顶点都被加入树中后，算法结束。 $parent$ 数组就定义了最小生成树的结构。

4.代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,u,v,w,ans,dist[5009];
bool vis[5009];
struct node{
    int v,w;
};
vector<node>graph[5009];
void prim(int u){
    for(int i=0;i<=n;i++)
		dist[i]=1e9;
    dist[u]=0;
    for(int i=1;i<=n;i++){
        u=0;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dist[j]<dist[u])
                u=j;
        vis[u]=1;
        for(auto node:graph[u]){
            int v=node.v,w=node.w;
            if(!vis[v])
                dist[v]=min(dist[v],w);
        }
    }
}
signed main(){
    cin>>n>>m;
    while(m--){
        cin>>u>>v>>w;
        graph[u].push_back({v,w});
        graph[v].push_back({u,w});
    }
    prim(1);
    bool f=0;
    for(int i=1;i<=n;i++){
        if(!vis[i])
            f=1;
        ans+=dist[i];
    }
    if(f)
		cout<<"orz";
    else
		cout<<ans;
    return 0;
}

时间复杂度： $O(mlogn)$ （不用优先队列的朴素版是 $O(n^2)$ ）
空间复杂度： $O(n+m)$

四、小结

算法	$Kruskal$	$Prim$
对象	边	点
时间复杂度	$O(m log m)$	$O(mlogn)$
空间复杂度	$O(n+m)$	$O(n+m)$
适用场景	稀疏图	稠密图
数据结构	并查集	优先队列

Part 4 $LCA$ —最近公共祖先

这是一个在树中非常常见且重要的问题，是许多其他高级问题的基础。

一、定义

~~字面意思~~对于一棵有根树中的两个节点 $p$ 和 $q$ ，它们的最近公共祖先被定义为同时是 $p$ 和 $q$ 的祖先的节点中，深度最大的那个节点。

二、倍增法求 $LCA$ （暴力解法这里就跳过了）

1.简介

这是求 $LCA$ 最常用的方法，用倍增的思想来向上“跳”。

2.核心思想

倍增法的主要思想是：任何整数都可以用二进制表示，那么从任何一个节点到其祖先的路径长度，也可以拆分为多个 $2$ 的幂次方步长。我们预先计算好每个节点向上跳 $2^k$ 步会到达哪里，查询时就能快速向上“跳”，而不需要一步一步走。

3.算法流程

预处理：

$depth[i]$ ：记录每个节点 $i$ 的深度。

$up[i][j]$ ：这是核心的倍增表。它表示从节点 $i$ 开始，向上跳 $2^j$ 步后，所到达的祖先节点。

这两个数组均可在 $dfs$ 中通过递推实现。

$depth$ 就不说了，我们重点讲解 $up$ ，注意到从 $i$ 点跳 $2^j$ 步 $=$ 先从 $i$ 点跳 $2^{j-1}$ 步到一个中间节点 $mid$ ，再从 $mid$ 节点跳 $2^{j-1}$ 步，由此， $up[i][j] = up[ up[i][j-1] ][j-1]$ ，这样，我们可以用已经计算好的第 $j-1$ 层的信息，来构建第 $j$ 层的信息。
查询
1. 深度对齐：首先，确保两个节点 $u$ 和 $v$ 处于同一深度。假设 $depth[u] > depth[v]$ ，我们需要把 $u$ 往上提。计算深度差 $d = depth[u] - depth[v]$ 。将深度差 $d$ 看作一个二进制数，利用倍增表快速提升 $u$ 。
2. 检查是否同一节点：如果此时 $u =v$ ，那么这个点就是 $LCA$ ，直接返回。
3. 同步攀升：如果深度对齐后 $u$ 和 $v$ 不同，则让它们一起向上跳，从最大的步数 $k = 20$ 开始尝试，向下递减，如果 $up[u][k] != up[v][k]$ ，说明这个祖先还不是公共的（还没越过 $LCA$ ），我们就可以安全地将 $u$ 和 $v$ 同时向上跳 $2^k$ 步，否则说明越过了 $LCA$ ，不跳。
4. 经过第 $3$ 步后， $u$ 和 $v$ 会停留在 $LCA$ 的正下方的两个直接子节点上。因此， $u$ 和 $v$ 此时的父节点就是 $LCA$ ，即 $up[u][0]$ 。

4.代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,s,fa[500009][20],dep[500009];//点，询问，根 
bool vis[500009];
vector<int> v[500009];
void dfs(int s,int f){
	dep[s]=dep[f]+1;
	for(int i=1;i<=19;i++)
		fa[s][i]=fa[fa[s][i-1]][i-1];
	for(auto p:v[s]){
		if(p==f)
			continue;
		dep[p]=dep[s]+1;
		fa[p][0]=s;
		dfs(p,s);
	}
}
int LCA(int a,int b){
	if(dep[a]<dep[b])
		swap(a,b);
	for(int i=19;i>=0;i--){
		if(dep[fa[a][i]]>=dep[b])
			a=fa[a][i];
	}
	if(a==b)
		return a;
	for(int i=19;i>=0;i--){
		if(fa[a][i]!=fa[b][i]){
			a=fa[a][i];
			b=fa[b][i];
		}
	}
	return fa[a][0];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	vis[s]=1;
	dfs(s,0);
	
	while(m--){
		int a,b;
		cin>>a>>b;
		cout<<LCA(a,b)<<endl;
	}
	return 0;
}

时间复杂度： $O(nlogn)$
空间复杂度： $O(nlogn)$

OK，耗时6天，终于杀青了，打字不易，点个赞吧。

@AC君求加精

有帮助，赞一个

去预览

0/2000

全部评论 41

沈思邈
@AC君加精！

昨天来自上海
3
沈思邈
建议适量加上注释

昨天来自上海
2
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复沈思邈
  后期会更新的哈
  
  昨天来自上海
  1
沈思邈
你完全可以不写“我还没学”以及“熟练剖分求LCA”

昨天来自上海
2
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复沈思邈
  已修改
  
  昨天来自上海
  1
🥥
d

昨天来自上海
1
🥥
d

昨天来自上海
1
🥥
d

昨天来自上海
1
‮༺དༀ༒∞░∞༒ༀཌ༻
666《精讲》

昨天来自浙江
1
- ‮༺དༀ༒∞░∞༒ༀཌ༻
  回复‮༺དༀ༒∞░∞༒ༀཌ༻
  无恶意啊
  
  昨天来自浙江
  1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复‮༺དༀ༒∞░∞༒ༀཌ༻
  不精吗？
  
  昨天来自上海
  1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复‮༺དༀ༒∞░∞༒ༀཌ༻
  给个赞呗
  
  昨天来自上海
  1
༺ཌༀཉི༒白·羊༒༃ༀད༻
由于有人提醒我 $Floyd$ 可以做负权图，各位大佬可以教教我怎么用 $Floyd$ 做负权图吗？@复仇者_帅童

昨天来自上海
1
- AAA混泥土批发ppl哥
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  负权图好像都能跑的吧，是跑不了负环（？）
  
  18小时前来自浙江
  0
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

昨天来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

昨天来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

昨天来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

昨天来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

昨天来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

昨天来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

昨天来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

昨天来自上海
1
沈思邈
顶

昨天来自上海
1
沈思邈
顶

昨天来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

昨天来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

昨天来自上海
1

本篇文章讲解图论算法，包括最短路、最小生成树、并查集和基础的LCALCALCA

大家请坐稳，我们马上开始。

Part 1 最短路算法

最短路算法是图论中最基础的方法，在各大比赛中都有涉及，本篇将会提到4种最短路算法。

一、定义

二、DijkstraDijkstraDijkstra算法

1.简介

2.核心思想

3.适用范围

4.朴素DijkstraDijkstraDijkstra算法

5.堆优化DijkstraDijkstraDijkstra算法

6.

练习

三、FloydFloydFloyd算法

1.简介

2.核心思想

3.适用范围

4.FloydFloydFloyd算法实现

5.

练习

四、BellmanBellmanBellman-FordFordFord算法

1.简介

2.核心思想

3.适用范围

4.BellmanBellmanBellman-FordFordFord算法实现

5.

练习

五、SPFASPFASPFA算法

1.简介

2.核心思想

3.适用范围

4.SPFASPFASPFA算法实现

六、小结

Part 2 并查集

并查集是图论中一种基础算法，是最小生成树等算法的基础，本篇将会提到3种并查集。

一、定义

二、朴素版

1.简介

2.核心思想

3.算法流程

4.代码实现

5.

练习

三、按秩合并

1.简介

2.核心思想

3.算法流程

4.代码实现

5.

还是这道

四、路径压缩

1.简介

2.核心思想&算法流程

3.代码实现

5.

还是这道

6.复杂度分析

Part 3 最小生成树

最小生成树是图论中一种基础方法，考试中会出现很多变体，本篇将会提到两种最小生成树算法。

一、定义

二、KruskalKruskalKruskal算法

1.简介

2.核心思想

3.算法流程

4.代码实现

5.

练习

三、PrimPrimPrim算法

1.简介

2.核心思想

3.算法流程

4.代码实现

四、小结

Part 4 LCALCALCA—最近公共祖先

这是一个在树中非常常见且重要的问题，是许多其他高级问题的基础。

一、定义

二、倍增法求LCALCALCA（暴力解法这里就跳过了）

1.简介

2.核心思想

3.算法流程

本篇文章讲解图论算法，包括最短路、最小生成树、并查集和基础的 $LCA$

二、 $Dijkstra$ 算法

4.朴素 $Dijkstra$ 算法

5.堆优化 $Dijkstra$ 算法

三、 $Floyd$ 算法

4. $Floyd$ 算法实现

四、 $Bellman$ - $Ford$ 算法

4. $Bellman$ - $Ford$ 算法实现

五、 $SPFA$ 算法

4. $SPFA$ 算法实现

二、 $Kruskal$ 算法

三、 $Prim$ 算法

Part 4 $LCA$ —最近公共祖先

二、倍增法求 $LCA$ （暴力解法这里就跳过了）