#创作计划# 并查集、最小生成树和最短路
2025-07-14 08:12:39
发布于：上海
89阅读
0回复
0点赞
并查集：
并查集（）是一种用于管理不相交集合的高效数据结构，主要解决元素的分组、合并与连通性查询问题。主要分成查询（）和合并（）两个操作。
模板代码：
const int N=5050;
int pa[N];
//核心代码
int find(int x){ //查找函数
if(pa[x]==x)return x; //找到根源，即自己的祖先就是自己
return pa[x]=find(pa[x]); //递归去寻找，将结果赋值给pa[x]进行路径压缩，防止超时
}
void unite(int a,int b){ //合并函数
int ra=find(a),rb=find(b); //找到各自的祖先，判断是否为同一个祖先
if(ra!=rb)pa[rb]=ra; //进行合并操作
}
//初始化
for(int i=1;i<=n;i++)
pa[i]=i; //默认祖先是自己
生成树：
在连通图 中，对于 ，有且仅有一条路，且生成树中不存在回路。
最小生成树：
是所有的生成树中边权值和最小的一棵生成树。常见算法有 （克鲁斯卡尔）和 （普里姆）
求最小生成树的方法：
· Kruskal 算法：
1、将所有的边按从小到大顺序排序
2、按排序顺序选择联通 两个结点的边
3、通过并查集判断 两个结点是否联通
4、如果不联通则合并两个结点
模板代码：
#include<bits/stdc++.h>
using namespace std;
const int N=5050;
#define pb push_back
#define int long long
struct Edge{
int u,v,w; //u、v表示两个端点，w表示边权值
}e;
bool cmp(Edge a,Edge b){ //比较函数，因为权值和最小，所以按照边权值从小到大排序
return a.w<b.w;
}
vector<Edge>edges; //存连通图的每条边
int n,m,c[N],ans,cnt;
int find(int x){ //并查集 查询函数
if(c[x]==x)return x;
return c[x]=find(c[x]); //路径压缩
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)c[i]=i; //并查集初始化
while(m--){
cin>>e.u>>e.v>>e.w;
edges.pb(e);
}
sort(edges.begin(),edges.end(),cmp); //按边的权值从小到大的顺序将边进行排序
for(auto edge:edges){ //按顺序遍历数组
int cu=find(edge.u),cv=find(edge.v); //找到两个结点所在的联通子图
if(cu!=cv){ //两点并未联通
c[cv]=cu; //合并两个结点，即并查集
cnt++; //计数，可以在下面节约时间
ans+=edge.w; //加上权值
}
if(cnt==n-1)break; //已经找到一棵最小生成树，退出循环
}
if(cnt!=n-1)puts("orz"); //不联通
else cout<<ans; //联通 输出最小权值和
return 0;
}
时间复杂度：
空间复杂度：
· Prim算法：
1、选择初始结点
2、从当前结点开始找到相邻边权值最小的结点，加入最小生成树中
3、加入的结点继续更新相邻结点的边权值，重复执行直到更新所有点
模板代码：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int MAXN=0x7f7f7f7f;
const int N=5050;
int n,m,u,v,w,ans,dist[N];
bool vis[N];
struct Node{
int v,w; //v表示目标结点，w表示边权值
};
vector<Node>graph[N]; //邻接表存图
void prim(int u){
for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
dist[u]=0; //以u为初始结点，距离为u到u的距离，即0
for(int i=1;i<=n;i++){ //重复执行n次，包括传入的参数u
u=0; //和赋值为0的u比较
for(int j=1;j<=n;j++)
if(!vis[j]&&dist[j]<dist[u]) //通过比较找到距离最近的结点
u=j; //更新u
vis[u]=1; //标记为已到达
for(auto node:graph[u]){ //遍历其相邻结点
int v=node.v,w=node.w;
if(!vis[v]) //一定要未被标记过，否则会重复
dist[v]=min(dist[v],w); //更新，因为结果是累加的，所以这边更新后只要保留w
}
}
}
signed main(){
cin>>n>>m;
while(m--){
cin>>u>>v>>w;
graph[u].pb({v,w});
graph[v].pb({u,w});
}
prim(1); //从任意的结点开始遍历都可行
bool f=0;
for(int i=1;i<=n;i++){
if(!vis[i]){ //不连通
f=1;
}
ans+=dist[i]; //累加
}
if(f)puts("orz"); //不连通
else cout<<ans; //连通输出结果
return 0;
}
时间复杂度：
空间复杂度：
最短路算法：
即求从结点到结点所有的道路中边权值之和最短的一条道路的算法。分为单源最短路和多源最短路算法。单源最短路即从定结点到所有其它结点的算法，而多源最短路算法可以求作为起点到其它结点的最短路。
单源最短路算法：
常见的有 （迪杰斯特拉）、（贝尔曼-福特）和 三个算法。
求单源最短路的方法：
· Dijkstra
的算法思想和 算法找最小生成树类似，采用“蓝白点”思想。
1、从当前结点开始找到相邻路径长度最短的结点
2、从新结点开始继续更新相邻结点的最短路，重复执行直到更新（松弛）所有点
模板代码：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int MAXN=0x7f7f7f7f;
const int N=5050;
int n,m,k,u,v,w,dist[N];
bool vis[N];
struct Node{
int v,w; //v表示目标结点，w表示边权值
};
vector<Node>graph[N]; //邻接表存图
void dijkstra(int u){
for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
dist[u]=0; //以u为初始结点，距离为u到u的距离，即0
for(int i=1;i<n;i++){ //重复n-1次，类似冒泡排序，可以省最后一次
u=0; //和赋值为0的无效u比较
for(int j=1;j<=n;j++)
if(!vis[j]&&dist[j]<dist[u]) //通过比较找到距离最近的结点
u=j; //更新u
vis[u]=1; //标记为已到达
for(auto node:graph[u]){ //遍历其相邻结点
int v=node.v,w=node.w;
if(!vis[v]) //一定要未被标记过，否则会重复
dist[v]=min(dist[v],dist[u]+w); //更新
//和Prim不同的是这里是和dist[u]+w比较更新
}
}
}
signed main(){
cin>>n>>m>>k;
while(m--){
cin>>u>>v>>w;
graph[u].pb({v,w}); //注意这里是有向图
//无向图再存一遍：graph[v].pb({u,w});
}
dijkstra(k); //一定要从单源起点开始遍历
for(int i=1;i<=n;i++)cout<<(dist[i]!=MAXN?dist[i]:-1)<<" ";
return 0;
}
时间复杂度：
空间复杂度：
Dijkstra 不适用的情况：
根据 算法的逻辑和流程，可以进行简单的模拟，易证它不适用于出现 负边权 的情况。
· Bellman-Ford：
不同于 算法， 算法枚举的是边而非结点。
1、遍历所有的边
2、从边的起点做到终点的松弛操作
3、如果没有进行过松弛操作则退出循环
模板代码：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int MAXN=0x7f7f7f7f;
const int N=5050;
int n,m,k,u,v,w,dist[N];
struct Edge{
int u,v,w; //u、v表示两个端点，w表示边权值
};
vector<Edge>graph; //存图的每条边
void Bellman_Ford(int u){
for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
dist[u]=0; //以u为初始结点，距离为u到u的距离，即0
for(int i=1;i<n;i++){ //重复n-1次，和Dijkstra一样
bool opt=0; //用于判断是否进行松弛操作
for(auto edge:graph){ //按顺序遍历数组
int u=edge.u,v=edge.v,w=edge.w;
if(dist[u]+w<dist[v]) //注意这里是有向图，无向图还需交换u和v
dist[v]=dist[u]+w,opt=1; //松弛操作后可以进行标记
}
if(!opt)return; //如果这次没有操作，下次也不会有操作，退出节省时间
}
}
signed main(){
cin>>n>>m>>k;
while(m--){
cin>>u>>v>>w;
graph.pb({u,v,w}); //有向图无向图都可以这样操作
}
Bellman_Ford(k);
for(int i=1;i<=n;i++)cout<<(dist[i]!=MAXN?dist[i]:-1)<<" ";
return 0;
}
时间复杂度：
空间复杂度：
Bellman-Ford 不适用的情况：
可以用于负权边的情况，不适用于负权回路。
· SPFA：
（）是 算法的进阶版本，通过队列来对其进行优化。
模板代码：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int N=5050;
const int MAXN=0x7f7f7f7f;
int n,m,k,u,v,w,dist[N],cnt[N];
bool vis[N];
struct node{
int v,w; //v表示目标结点，w表示边权值
};
vector<node>graph[N]; //邻接表存图
void spfa(int u){
for(int i=1;i<=n;i++)dist[i]=MAXN,vis[i]=0; //初始化
queue<int>q;
dist[u]=0; //以u为初始结点，距离为u到u的距离，即0
q.push(u);
while(q.size()){
u=q.front(); //取出队首，同bfs
q.pop(); //弹出队首，同bfs
vis[u]=0; //撤销标记，因为spfa可以重复入队
cnt[u]++; //计数
if(cnt[u]>n)return; //和Bellman-Ford一样最多只能入队n次，大于n直接返回
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].pb({v,w}); //注意这里是有向图
//无向图再存一遍：graph[v].pb({u,w});
}
spfa(k);
for(int i=1;i<=n;i++)cout<<(dist[i]!=MAXN?dist[i]:-1)<<" ";
return 0;
}
时间复杂度：（为常数，通常是在 之间）
空间复杂度：
队列空间复杂度：
多源最短路算法：
一般用 算法（也有版本叫它 ）。
求多远最短路的方法：
· Floyd-Warshall：
算法可能是大多数人最喜欢的方法。其核心思想是动态规划，把每个结点作为中转点、起点和终点进行计算。注意不能够把它循环顺序反过来，否则结果会出问题。
模板代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=0x7f7f7f7f; //极大值
int n,m,q,dp[110][110],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:INF; //初始化
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]==INF?-1:dp[u][v])<<"\n"; //访问
}
return 0;
}
时间复杂度：
空间复杂度：
Floyd-Warshall 不适用的情况
不适用于出现负权回路的情况。
备注：
符号解释：
：表示点的数量
：表示边的数量
：指点的集合
：指边的集合
有帮助，赞一个