数据结构预算法-图论- 最小生成树-prim and kruskal
基础文字知识
最小生成树（Minimum Spanning Tree，MST）是图论中的一个重要概念，以下是关于它的详细介绍：
定义
在一个无向连通加权图中，最小生成树是一棵包含图中所有顶点，且边的权值之和最小的树。它是原图的一个子图，具有以下特点：包含原图中所有的顶点；是一棵树，即没有回路；所有边的权值之和最小。
作用及应用场景
网络设计：在通信网络、电力网络等基础设施建设中，需要连接多个节点（如城市、基站、发电厂等），使用最小生成树算法可以找到最经济的连接方式，即总线路长度最短或总建设成本最低。
聚类分析：在数据挖掘和机器学习中，最小生成树可用于聚类分析，将数据点看作图的顶点，点与点之间的距离看作边的权值，通过构建最小生成树可以根据数据点之间的连接关系进行聚类。
图像处理：在图像分割等图像处理任务中，可将图像中的像素点视为图的顶点，像素点之间的某种相似性度量作为边的权值，最小生成树可以帮助识别图像中的不同区域。
常见算法
普里姆（Prim）算法
基本思想：从任意一个顶点开始，每次选择与当前生成树相连的边中权值最小的边，将其对应的顶点加入到生成树中，直到包含所有顶点。
时间复杂度：使用二叉堆等数据结构来实现时，时间复杂度为O(ElogV)，其中E是边的数量，V是顶点的数量。
（n^2 or 堆优化（被下面的算法完爆））
克鲁斯卡尔（Kruskal）算法
基本思想：将所有边按照权值从小到大排序，依次选取权值最小的边，只要该边与已选的边不会形成回路，就将其加入到生成树中，直到生成树包含所有顶点。
时间复杂度：时间复杂度为O(ElogE)，主要是排序操作的时间开销。
简单示例
假设有一个无向连通加权图，顶点为 A、B、C、D、E，边及其权值分别为：AB (3)、AC (5)、AD (2)、BC (4)、BD (6)、CD (1)、CE (7)、DE (8)。
使用普里姆算法：若从顶点 A 开始，首先选择权值最小的边 AD，然后从与 A、D 相连的边中选择权值最小的 CD，接着选择 AB，再选择 BC，最后选择 CE，得到的最小生成树包含边 AD、CD、AB、BC、CE，总权值为 2 + 1 + 3 + 4 + 7 = 17。
使用克鲁斯卡尔算法：首先对所有边按照权值从小到大排序，得到 CD (1)、AD (2)、AB (3)、BC (4)、AC (5)、BD (6)、CE (7)、DE (8)。依次选择 CD、AD、AB、BC、CE，构成的最小生成树与普里姆算法结果相同，总权值也为 17。
习题1：最短网路（板子题）：
分析：
这是一道利用最小生成树算法解决实际问题的题目，思路如下：
构建图模型：将每个农场看作图的顶点，农场之间的连接距离视为边的权值，从而构建一个无向加权图。
选择算法：为使连接所有农场的光纤最短，即求该图的最小生成树。可选用普里姆（Prim）算法或克鲁斯卡尔（Kruskal）算法。
普里姆算法：从农场 1（编号为 1）开始，将其加入已访问顶点集合。每次从未访问顶点中，选择与已访问顶点集合相连且权值最小的边，将对应的顶点加入已访问集合，直到所有农场都被连接。
克鲁斯卡尔算法：先把所有边按权值从小到大排序，依次选取权值最小的边，只要该边连接的两个农场不在同一连通分量（可通过并查集判断），就将其加入最小生成树，直到所有农场连通。
计算结果：使用选定的算法得到最小生成树后，其所有边的权值之和就是连接所有农场所需的最短光纤长度。
这里的输入是邻接矩阵，可以直接用prim更加方便
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n;
int w[N][N];
int prim(){
int res=0;
int dis[N]={0};
int vis[N]={0};
memset(dis,0x3f,sizeof dis);
dis[0]=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=0;j<n;j++){
if(vis[j])continue;
if(t==-1||dis[t]>dis[j])t=j;
}
vis[t]=1;
res+=dis[t];
for(int j=0;j<n;j++){
dis[j]=min(dis[j],w[t][j]);
}
}
return res;
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>w[i][j];
cout<<prim();
}
习题2：局域网（板子题2）：
分析：
这道题可以通过最小生成树算法来解决，思路如下：
构建图模型：把每台计算机当作图中的顶点，计算机之间的网线看作边，网线的畅通程度就是边的权值，从而构建一个无向加权图。
计算最小生成树的权值和：为了使网络中没有回路，需要找到图的最小生成树，可使用普里姆（Prim）算法或克鲁斯卡尔（Kruskal）算法。这两种算法都能找出连接所有顶点且无回路的边集合，并且这些边的权值总和最小。
计算被除去网线的权值和最大值：先计算所有网线（即图中所有边）的权值总和，再减去最小生成树的权值和，得到的差值就是被除去网线的∑f(i,j)的最大值。
这个的输入按照边进行的，适合使用克鲁斯卡尔算法：
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=N*N;
typedef struct ed{
int u,v,w;
bool operator >(const ed &a){
return w>a.w;
}
bool operator <(const ed &a){
return w<a.w;
}
}ed;
int par[N];
ed edge[M];
int find(int x){
if(x!=par[x])par[x]=find(par[x]);
return par[x];
}
void merge(int x,int y){
int px=find(x);int py=find(y);
if(px==py)return;
par[px]=py;
}
int main(){
int n,k,sum=0;
cin>>n>>k;
for(int i=0;i<k;i++){
int u,v,w;
cin>>u>>v>>w;
edge[i]={u,v,w};
sum+=w;
}
sort(edge,edge+k);
for(int i=1;i<=n;i++){
par[i]=i;
}
int res=0;
for(int i=0;i<k;i++){
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
if(find(u)!=find(v)){
merge(u,v);
res+=w;
}
}
cout<<sum-res;
return 0;
}
习题3:繁忙的都市（板子题3）：
分析：
这道题可通过最小生成树算法来求解，思路如下：
构建图模型：将交叉路口视为图的顶点，道路看作边，道路分值作为边的权值，构建无向加权图。
求最小生成树：使用普里姆（Prim）算法或克鲁斯卡尔（Kruskal）算法求出该图的最小生成树。因为最小生成树能连接所有顶点且边数最少，满足题目中把所有交叉路口连通起来且改造道路尽量少的要求。
确定结果：在最小生成树的边中，找出权值最大的边，该权值就是改造的那些道路中分值的最大值，此即为最终答案。
综上，解题步骤是先构建图，再用最小生成树算法得到最小生成树，最后找出其中最大的边权值。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=N*N;
typedef struct ed{
int u,v,w;
bool operator >(const ed &a){
return w>a.w;
}
bool operator <(const ed &a){
return w<a.w;
}
}ed;
int par[N];
ed edge[M];
int find(int x){
if(x!=par[x])par[x]=find(par[x]);
return par[x];
}
void merge(int x,int y){
int px=find(x);int py=find(y);
if(px==py)return;
par[px]=py;
}
int main(){
int n,k,sum=0;
cin>>n>>k;
for(int i=0;i<k;i++){
int u,v,w;
cin>>u>>v>>w;
edge[i]={u,v,w};
sum+=w;
}
sort(edge,edge+k);
for(int i=1;i<=n;i++){
par[i]=i;
}
int res=0;
for(int i=0;i<k;i++){
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
if(find(u)!=find(v)){
merge(u,v);
res=max(w,res);
}
}
cout<<n-1<<' '<<res;
return 0;
}
习题4：联络员：
分析：
处理必选通信渠道：先遍历输入数据，把所有必选通信渠道（即 p=1 的情况）进行处理。将
这些渠道对应的管理员连接起来（可以使用并查集来管理连通性），同时累加这些必选渠道
的费用，记录下它们连接的管理员集合情况。
筛选可选通信渠道并排序：把所有选择性通信渠道（p=2 的情况）筛选出来，按照费用 w 从
小到大进行排序。
构建最小生成树：基于前面处理必选渠道后的管理员连通情况，从排序后的选择性通信渠道
中，依次选取费用最小的渠道。如果选取该渠道能连接不同的连通分量（通过并查集判断），
就将其加入到最终的通信渠道集合中，并累加其费用。重复此操作，直到所有管理员都处于
同一个连通分量中，即实现了两两都可以联络。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=10010;
typedef struct ed{
int u,v,w;
bool operator >(const ed &a){
return w>a.w;
}
bool operator <(const ed &a){
return w<a.w;
}
}ed;
int par[N];
ed edge[M];
int find(int x){
if(x!=par[x])par[x]=find(par[x]);
return par[x];
}
void merge(int x,int y){
int px=find(x);int py=find(y);
if(px==py)return;
par[px]=py;
}
int main(){
int n,k,sum=0;
cin>>n>>k;
for(int i=1;i<=n;i++){
par[i]=i;
}
int cnt=0,res=0;
for(int i=0;i<k;i++){
int p,u,v,w;
cin>>p>>u>>v>>w;
if(p==1){
merge(u,v);
res+=w;
}else
edge[cnt++]={u,v,w};
}
sort(edge,edge+cnt);
for(int i=0;i<cnt;i++){
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
if(find(u)!=find(v)){
merge(u,v);
res+=w;
}
}
cout<<res;
return 0;
}
习题5：链接格点：
分析：
二维映射为一维：点阵是二维结构，为了方便使用并查集和图相关算法（如克鲁斯卡尔算法），将二维坐标映射为一维编号。例如，对于一个m行n列的点阵，第i行第j列的点可以映射为编号i×n+j（这里行和列从0开始计数），这样每个点都有唯一的一维编号，便于后续处理边和集合操作。
读入所有已有的边，并用并查集合并：根据输入获取已经存在的边，将边的两个端点在并查集中进行合并操作。并查集是一种数据结构，用于管理元素的集合关系，通过不断合并操作，可以确定哪些点已经处于连通状态。这样在后续构建最小生成树时，就可以避免重复连接已经连通的点。
克鲁斯卡尔算法连接其他的边：在处理完已有边后，对于剩余的可能连接的边（即还未考虑的相邻点之间的边），按照克鲁斯卡尔算法的流程来处理。先将所有这些边按照权值从小到大排序，然后依次选取权值最小的边，如果该边连接的两个点不在同一个连通分量中（通过并查集判断），就将这条边加入到最小生成树中，直到所有点都连通。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=N*N,K=2*M;
typedef struct ed{
int u,v,w;
// bool operator >(const ed &a){
// return w>a.w;
// }
// bool operator <(const ed &a){
// return w<a.w;
// }
//因为我们加入边的时候先加入的是1的，然后才是2的，相当如自动排序了
}ed;
int par[M];
ed edge[K];
int find(int x){
if(x!=par[x])par[x]=find(par[x]);
return par[x];
}
void merge(int x,int y){
int px=find(x);int py=find(y);
if(px==py)return;
par[px]=py;
}
int n,m,id[N][N],cnt=0;
void get_ed(){
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<=2;k+=2)
if(i+dx[k]>=1&&i+dx[k]<=n &&j+dy[k]>=1&&j+dy[k]<=n){
int a=id[i][j];
int b=id[i+dx[k]][j+dy[k]];
edge[cnt++]={a,b,1};
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=3;k+=2)
if(i+dx[k]>=1&&i+dx[k]<=n
&&j+dy[k]>=1&&j+dy[k]<=n){
int a=id[i][j];
int b=id[i+dx[k]][j+dy[k]];
edge[cnt++]={a,b,2};
}
}
int main(){
cin>>n>>m;
for(int i=1,t=1;i<=n;i++)
for(int j=1;j<=n;j++,t++){
id[i][j]=t;
}
for(int i=1;i<=n*n;i++)par[i]=i;
int x1,y1,x2,y2;
while(cin>>x1>>y1>>x2>>y2){
int a=id[x1][y1],b=id[x2][y2];
merge(a,b);
}
get_ed();
int res=0;
for(int i=0;i<cnt;i++){
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
if(find(u)!=find(v)){
res+=w;
merge(u,v);
}
}
cout<<res;
}