最小生成树
理论
最小生成树的定义见生成树。
常见的两种相关算法分别是加点的Prim算法和加边的Kruskal算法。
Prim算法
prim算法适用于稠密图，通过选择最近点增加以构建树，总体思路是循环选择距离当前树最近且不在树中的点加入树，依赖邻接矩阵实现。
在数据规模较大的情况下，考虑使用优先队列和堆优化空间。
实现
朴素Prim的思路如下：
- 初始化和建图。需要至少一个存边的二维数组
edges，以及一个存当前未加入生成树的点与生成树的最小距离的一维数组lowcost，元素均初始化为一个极大值INF。
选择或确定生成树的第一个元素，将lowcost中对应的元素置为0，将其它所有元素置为和第一个元素之间的直接连边的边权。如果没有直接连边，则默认为INF。
- 循环，选择距离生成树最小距离的点加入生成树，直到所有点都加入生成树。
- 遍历
lowcost，找到最小权的边和对应的节点
- 将节点加入生成树，累加总边权
- 遍历
lowcost，检查未加入生成树的节点和本轮加入生成树的节点的直接连边边权，如果比lowcost中记录的更小就更新。
- 返回总边权。
朴素Prim代码
| #include<iostream>
using namespace std;
const int MAX=1005;
const int INF=2147483647;
int n,m; //顶点数、边数
int map[MAX][MAX];
int a,b,w;
int lowcost[MAX];
int sum=0;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)map[i][j]=INF;
}
for(int i=0;i<m;i++){
cin>>a>>b>>w;
map[a][b]=w;
map[b][a]=w;
}
//初始化lowcost
for(int i=1;i<=n;i++){
if(i==1)lowcost[i]=0;
else lowcost[i]=map[1][i];
}
//prim
for(int i=1;i<n;i++){
int minP=-1;
int minCost=INF;
for(int j=1;j<=n;j++){
if(lowcost[j]==0)continue;
if(lowcost[j]<minCost){
minCost=lowcost[j];
minP=j;
}
}
//更新lowcost
sum+=lowcost[minP];
lowcost[minP]=0;
for(int j=1;j<=n;j++){
if(lowcost[j]==0)continue;
if(lowcost[j]>map[minP][j])lowcost[j]=map[minP][j];
}
}
cout<<sum;
return 0;
}
|
堆优化
使用优先队列存储当前点可以到达的点的状态。
题目链接：P1111 修复公路 - 洛谷
通过代码
| #include<iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
struct compare{
bool operator()(pair<int,int> a,pair<int,int> b){
return a.second>b.second;
}
};
const int MAX=1e3+5;
const int INF=0x3f3f3f3f;
int n,m,u,v,c,res;
vector<pair<int,int>> graph[MAX]; //target,dist
int dist[MAX];
bool isvis[MAX];
priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v>>c;
graph[u].push_back(make_pair(v,c));
graph[v].push_back(make_pair(u,c));
}
//初始化pq，dist；
for(int i=1;i<=n;i++)dist[i]=INF;
dist[1]=0;
pq.push(make_pair(1,0));
//prim
while(!pq.empty()){
//取出队首，标记，更新相邻点到树的距离
pair<int,int> curr=pq.top();
pq.pop();
if(isvis[curr.first])continue;
isvis[curr.first]=true;
res=max(res,curr.second);
for(auto point:graph[curr.first]){
if(isvis[point.first])continue;
if(dist[point.first]<=point.second)continue;
dist[point.first]=point.second;
pq.push(point);
}
}
//检查是否所有村庄都标记
for(int i=1;i<=n;i++){
if(!isvis[i]){
cout<<"-1";
return 0;
}
}
cout<<res;
return 0;
}
|
Kruskal算法
kruskal算法适用于稀疏图，通过选择最短边构建树，总体思路是先对边权进行排序，然后从边权小的开始取，直到取到点数-1条边。
并非所有边都能取，只有一条边连接的两个点之间不连通时，这条边才能连接。因此，kryakal算法使用并查集辅助判断两点是否在同一连通图。
实现
总体思路如下：
- 初始化。结构体数组存边并按边权排序，初始化并查集
- 遍历边数组
- 根据并查集判断当前边能否加入生成树
- 更新并查集，累加边权
- 返回总边权
为了时间和空间的优化，可以使用带小根堆存储边结构体。Kruskal与点无关，不需要存点。
若题目要求查询最大连通子图，可以在结构体中额外维护一个参数，记录以当前节点为根的点数，初始化为1。
模板题
题目链接：P1195 口袋的天空 - 洛谷
实现代码
| #include<iostream>
#include<vector>
#include<queue>
using namespace std;
using ll=long long;
struct Edge{
int u;
int v;
ll dist;
};
struct compare{
bool operator()(Edge a,Edge b){
return a.dist>b.dist;
}
};
const int MAX=1e4+5;
const int P=1e3+5;
int n,m ,k,x,y,l,num,maxEdges=-1;
ll w;
priority_queue<Edge,vector<Edge>,compare> pq;
pair<int,int> parent[P]; //point,num
int find(int x){
if(parent[x].first!=x)parent[x].first=find(parent[x].first);
return parent[x].first;
}
void unite(int x,int y){
int rootx=find(x);
int rooty=find(y);
if(rootx!=rooty){
parent[rooty].first=rootx;
parent[rootx].second+=parent[rooty].second;
maxEdges=max(maxEdges,parent[rootx].second);
}
}
bool query(int x,int y){
int rootx=find(x);
int rooty=find(y);
return rootx==rooty;
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<m;i++){
cin>>x>>y>>l;
pq.push({x,y,l});
}
if(n<k){
cout<<"No Answer";
return 0;
}
if(num==k){
cout<<"0";
return 0;
}
//init
for(int i=1;i<=n;i++){
parent[i].first=i;
parent[i].second=1;
}
num=n;
while(!pq.empty()&&num!=k){
Edge edge=pq.top();
pq.pop();
if(!query(edge.u,edge.v)){
num--;
unite(edge.u,edge.v);
w+=edge.dist;
}
}
if(num==k)cout<<w;
else cout<<"No Answer";
return 0;
}
|
其中记录每个根节点的子节点数目在此题是多余的，仅用于对该类型的记录。