#创作计划# 并查集、最小生成树和最短路

沈思邈

2025-09-21 09:11:02

发布于：上海

146阅读

0回复

0点赞

（由于对 $Python$ 略有研究，本帖子还会附带 $Python$ 模板）

并查集：

并查集（ $Union-Find$ ）是一种用于管理‌不相交集合‌的高效数据结构，主要解决元素的‌分组、合并与连通性查询‌问题。主要分成查询（ $Find$ ）和合并（ $Unite$ ）两个操作。
C++模板代码：

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; //默认祖先是自己

Python模板代码：

pa=[i for i in range(n+1)] #列表生成式自带初始化
#核心代码
def find(x): #查找递归
    if pa[x]==x: #找到根源，自己的祖先是自己
        return x #返回结果
    pa[x]=find(pa[x]) #路径压缩
    return pa[x] #返回结果
def unite(a=int,b=int): #合并
    ra,rb=find(a),find(b) #利用元组特性进行赋值
    if ra!=rb: #祖先不同，进行合并
        pa[rb]=ra #朴素的合并操作

生成树：

在连通图 $G$ 中，对于 $\forall u、v\in G.V$ ，有且仅有一条路，且生成树中不存在回路。

最小生成树：

是所有的生成树中边权值和最小的一棵生成树。常见算法有 $Kruskal$ （克鲁斯卡尔）和 $Prim$ （普里姆）

求最小生成树的方法：

· Kruskal 算法：

1、将所有的边按从小到大顺序排序
2、按排序顺序选择联通 $u、v$ 两个结点的边
3、通过并查集判断 $u、v$ 两个结点是否联通
4、如果不联通则合并两个结点
C++模板代码：

#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;
}

时间复杂度： $O(E\log E)$
空间复杂度： $O(V+E)$
Python模板代码：

n,m=map(int,input().split())
edges=[] #存边，而非邻接表
while m>0:
    m-=1
    u,v,w=map(int,input().split())
    edges.append((u,v,w)) #存边
pa=[i for i in range(n+1)] #列表生成式，并查集初始化
def find(x): #并查集的查找函数
    if pa[x]==x: #找到根源，自己的祖先是自己
        return x #返回结果
    pa[x]=find(pa[x]) #路径压缩
    return pa[x] #返回结果
edges.sort(key=lambda x:x[2]) #按照边权从小到大排序进行贪心
cnt=ans=0 #cnt计数，ans最小边权和
for u,v,w in edges: #遍历
    cu,cv=find(u),find(v) #找到祖先
    if cu!=cv: #两个点未连通，进行边权添加，连入同一棵最小生成树
        cnt+=1 #选的边数+1
        ans+=w #更新答案
        pa[cv]=cu; #合并
    if cnt==n-1: #n个顶点n-1条边，选到了提前退出
        break
if cnt<n-1: #没选到，证明有顶点不连通
    print("orz") #不连通输出
else: #连通
    print(ans) #连通输出

· Prim算法：

1、选择初始结点
2、从当前结点开始找到相邻边权值最小的结点，加入最小生成树中
3、加入的结点继续更新相邻结点的边权值，重复执行直到更新所有点
C++模板代码：

#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;
}

时间复杂度： $O(V^2)$
空间复杂度： $O(V+E)$
Python模板代码：

n,m=map(int,input().split())
graph=[[] for i in range(n+1)] #列表生成式创建邻接表
while m>0:
    m-=1
    u,v,w=map(int,input().split())
    graph[u].append((v,w)) #建边
    graph[v].append((u,w)) #建边
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式初始化
vis=[0 for i in range(n+1)] #列表生成式初始化
def prim(u): #核心函数
    dist[u]=0 #u到u距离为0
    for i in range(n): #循环n次找开始更新的点，包括u
        u=0 #和赋值为极大值的0号结点比较，且0号结点不参与更新
        for j in range(1,n+1): #遍历
            if not vis[j] and dist[j]<dist[u]: #通过比较找到距离最近的结点
                u=j #更新u
        vis[u]=1 #标记为已到达
        for v,w in graph[u]: #遍历从当前结点出发的每一条边
            if not vis[v]: #未标记过以防重复
                dist[v]=min(dist[v],w) #更新，结果是累加的，所以只保留w
prim(1) #任意结点开始都可以
ans=sum(dist[1:]) #求和
if ans>0x3f3f3f3f/2: #超过，根据题目要求判断是否合法
    print("orz") #不连通输出
else: #未超过则连通
    print(ans) #连通输出

最短路算法：

即求从结点 $u$ 到结点 $v$ 所有的道路中边权值之和最短的一条道路的算法。分为单源最短路和多源最短路算法。单源最短路即从定结点 $u$ 到所有其它结点 $v$ 的算法，而多源最短路算法可以求 $\forall u \in G.V$ 作为起点到其它结点 $v$ 的最短路。

单源最短路算法：

常见的有 $Dijkstra$ （迪杰斯特拉）、 $Bellman-Ford$ （贝尔曼-福特）和 $SPFA$ 三个算法。

求单源最短路的方法：

· Dijkstra

$Dijkstra$ 的算法思想和 $Prim$ 算法找最小生成树类似，采用“蓝白点”思想。
1、从当前结点开始找到相邻路径长度最短的结点
2、从新结点开始继续更新相邻结点的最短路，重复执行直到更新（松弛）所有点
C++模板代码：

#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;
}

时间复杂度： $O(V^2)$
空间复杂度： $O(V+E)$
Python模板代码：

n,m,s=map(int,input().split())
graph=[[] for i in range(n+1)] #列表生成式创建邻接表
while m>0:
    m-=1
    u,v,w=map(int,input().split())
    graph[u].append((v,w)) #建边
    #如果无向图则再建一条边graph[v].append((u,w))
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式初始化
vis=[0 for i in range(n+1)] #列表生成式初始化
def dijkstra(u): #核心函数
    dist[u]=0 #u到u距离为0
    for i in range(n): #循环n次找开始更新的点，包括u
        u=0 #和赋值为极大值的0号结点比较，且0号结点不参与更新
        for j in range(1,n+1): #遍历
            if not vis[j] and dist[j]<dist[u]: #通过比较找到距离最近的结点
                u=j #更新u
        vis[u]=1 #标记为已到达
        for v,w in graph[u]: #遍历从当前结点出发的每一条边
            if not vis[v]: #未标记过以防重复
                dist[v]=min(dist[v],dist[u]+w) #更新，注意最短路里面就需要累加
dijkstra(s) #从源点s开始更新
for i in range(1,n+1): #遍历
    print(dist[i] if dist[i]!=0x3f3f3f3f else -1,end=" ") #可达输出，不可达输出-1

当然我们也可以利用优先队列优化 $Dijkstra$ 算法：

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;
    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]=MAXN; //初始化
    dist[u]=0; //以u为初始结点，距离为u到u的距离，即0
    q.push({u,0}); //初始结点加入队列
    while(q.size()){ //bfs思路
    	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]}); //入队
			}
		}
	}
}

时间复杂度： $O(V\log V+E\log V)$

Dijkstra 不适用的情况：

根据 $Dijkstra$ 算法的逻辑和流程，可以进行简单的模拟，易证它不适用于出现 负边权 的情况。

· Bellman-Ford：

不同于 $Dijkstra$ 算法， $Bellman-Ford$ 算法枚举的是边而非结点。
1、遍历所有的边
2、从边的起点做到终点的松弛操作
3、如果没有进行过松弛操作则退出循环
C++模板代码：

#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;
}

Python模板代码：

n,m,s=map(int,input().split())
edges=[] #存边，而非邻接表
while m>0:
    m-=1
    u,v,w=map(int,input().split())
    edges.append((u,v,w)) #存边，有向边
    #无向边再存一遍edges.append((v,u,w))
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式初始化
def Bellman_Ford(u):
    dist[u]=0 #u到u距离为0
    for i in range(n): #一共枚举n次
        opt=0 #用于判断是否进行松弛操作
        for u,v,w in edges: #枚举所有边
            if dist[u]+w<dist[v]: #可以进行松弛
                dist[v]=dist[u]+w #松弛
                opt=1 #标记
        if not opt: #没有进行松弛，那么下一轮也不会松弛，退出循环
            break            
Bellman_Ford(s) #从源点开始更新
for i in range(1,n+1):
    print(dist[i] if dist[i]!=0x3f3f3f3f else -1,end=" ") #可达输出，不可达输出-1

当然，对于某些题目，要求走的边数不超过 $k$ 且求最短路，可以使用 $dp$ 思想，来进行最短路的计算，如下：

#define pb push_back
#define int long long
const int MAXN=0x3f3f3f3f; //防止做加法超出int范围 
const int N=5050;
int n,m,k,u,v,w,dist[N][N]; //dist[i][j]表示选用i条边到达j的最短路，必然不会超过n-1条边
struct Edge{
    int u,v,w; //u、v表示两个端点，w表示边权值
};
vector<Edge>graph; //存图的每条边
void Bellman_Ford(int u){
    memset(dist,MAXN,sizeof(dist)); //初始化
    dist[0][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[i-1][u]+w<dist[i][v]) //注意这里是有向图，无向图还需交换u和v
                dist[i][v]=dist[i-1][u]+w,opt=1; //松弛操作后可以进行标记
        }
        if(!opt)return; //如果这次没有操作，下次也不会有操作，退出节省时间
    }
}

时间复杂度： $O(VE)$
空间复杂度： $O(V+E)$

Bellman-Ford 不适用的情况：

$Bellman-Ford$ 可以用于负权边的情况，没有不适用的情况。

· SPFA：

$SPFA$ （ $Shortest\,\,Path\,\,Faster\,\,Algorithm$ ）是 $Bellman-Ford$ 算法的进阶版本，通过队列来对其进行优化。
C++模板代码：

#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;
}

时间复杂度： $O(kV)$ （ $k$ 为常数，通常是在 $[2,3]$ 之间）
空间复杂度： $O(V+E)$
队列空间复杂度： $0< x\leq O(V)$

多源最短路算法：

一般用 $Floyd-Warshall$ 算法（也有版本叫它 $Floyed-Warshall$ ）。

求多源最短路的方法：

· Floyd-Warshall：

$Floyd-Warshall$ 算法可能是大多数人最喜欢的方法。其核心思想是动态规划，把每个结点作为中转点、起点和终点进行计算。注意不能够把它循环顺序反过来，否则结果会出问题。
C++模板代码：

#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;
}

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

Floyd-Warshall 不适用的情况

$Floyd-Warshall$ 不适用于出现负权回路的情况。

备注：

符号解释：
$G$ ：表示一张图
$V$ ：表示点的数量
$E$ ：表示边的数量
$G.V$ ：指点的集合
$G.E$ ：指边的集合

实际上只不过是个上课笔记

有帮助，赞一个

去预览

0/2000

全部评论 15

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

2025-08-19 来自上海
1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  @༺ཌༀཉི༒复仇天神༒༃ༀད༻
  
  2025-08-19 来自上海
  0
- Gold（有关必回）
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  %%%
  
  2025-08-19 来自上海
  0
- 沈思邈
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  orz
  
  2025-08-21 来自上海
  0
0℃
加团

2025-08-21 来自浙江
0
🍀

2025-08-21 来自浙江
0
🍀
BTNNN

2025-08-21 来自浙江
0
cjdstttttt

你说得对，但是SPFA已经死了，所以 $k$ 应该是 $E$ （（（

2025-08-19 来自浙江
0
- 沈思邈
  回复cjdstttttt
  666有道理
  
  2025-08-19 来自上海
  0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复cjdstttttt
  卡常就老实了hhh
  
  2025-08-19 来自上海
  1
Lexore_
%%%

2025-07-30 来自浙江
0
huchen(已老实）
delicious

2025-07-30 来自浙江
0
AAA水泥批發白哥
那么很好，请给出证明（（（

2025-07-08 来自山西
0
- ppl 大帝
  回复AAA水泥批發白哥
  那么很好，请学会贪心
  
  2025-07-08 来自浙江
  0
- 沈思邈
  回复AAA水泥批發白哥
  那么很好，请你帮我穿越回之前成为Kruskal或者Prim
  
  2025-07-08 来自上海
  0
- AAA水泥批發白哥
  回复ppl 大帝
  %%%
  
  2025-07-08 来自山西
  0
zsy
你好你好，同样拥有题解仙人

2025-07-07 来自浙江
0
- 沈思邈
  回复zsy
  你好
  
  2025-07-07 来自上海
  0
- zsy
  回复沈思邈
  虽然这些我都不会……
  
  2025-07-08 来自江苏
  0
古希腊掌管AC和WA的神
%%%

2025-07-07 来自上海
0
你是不是喜欢c++
%%%

2025-07-07 来自广东
0
ppl 大帝
好像是少数的拥有“题解仙人”的入%%%

2025-07-07 来自浙江
0
- zsy
  回复ppl 大帝
  我也有！
  
  2025-07-07 来自浙江
  0
cjdstttttt
wc秒精

2025-07-07 来自广东
0
- ppl 大帝
  回复cjdstttttt
  你一辈子（（（
  
  2025-07-07 来自浙江
  0
ppl 大帝
%%%

2025-07-07 来自浙江
0
cjdstttttt
%%%

2025-07-07 来自广东
0