最小生成树：对于一张连通图来说，能够是原图保持联通并且各边权值和最小的极小连通子图称为最小生成树。这里简单说一下使用prim算法求最小生成树。
首先在图中任取一点s,把与s相连的边中权值最小的边及顶点加入生成树，然后再从这两个点发出的所有边中取权值最小的边和顶点加入生成树，然后再从所有与生成树相连的边中选出权值最小的边和顶点加入生成树，以此类推，直至所有点加入生成树。这个生成树便是最小生成树。下面用图演示下。
首先我们任意选择一个点，比如A点，然后找出与A点相连的所有点中权值最小的边，并把它（权值最小的边）和顶点加入生成树，我们发现与A相连的边中权值最小的边为与B相连的权值为1的边，所以我们把这条边和B点加入生成树，此时变成了：（红色部分为生成树）
此时我们找出所有与生成树相连权值最小的边，我们发现是与D相连且权值为2的边。所以我们把边和D点加入生成树，此时生成树变成了：
此时我们找出所有与生成树相连权值最小的边，我们发现是与D点相连的F点，我们将边和D点加入生成树，此时变成了：
此时我们发现权值最小的边是与F点相连的C点，我们将C点和边加入生成树，此时变成了：
最后我们将与A点相连的E点加入生成树，就得到了最小生成树。
如果有两条权值相同且权值均为最小的边，可任选一条加入，并不影响最终结果的正确性。关于正确性证明，感兴趣的读者可以自行百度（鄙人数学过于渣）。
最后说一下代码实现。一般使用邻接表，vector和优先队列来实现，每次取出优先队列最头部的点，判断该边和点是否在生成树中，如果不在，就将该点加入有限队列。否则不加入。推荐一道板子题，传送门 洛谷 2080 局域网 下边上一下鄙人的代码：
#include<bits/stdc++.h>
using namespace std;
const int MAX=100+5;
struct edge{
edge(int y,int cost){ this->y=y; this->cost=cost; }
edge(){};
int y,cost;
friend bool operator<(const edge &a,const edge &b){
return a.cost>b.cost;
}
};
std::vector<edge> vec[MAX*MAX];
std::priority_queue<edge> que;
int vis[105];
inline void init(){
for(int q=0;q<105;q++)
vis[q]=0;
}
int n,k;
int prim(){
int sum=0;
vis[1]=1;
for(int q=0;q<vec[1].size();q++)
que.push(vec[1][q]);
while(!que.empty()){
edge front;
front=que.top();
que.pop();
if(vis[front.y]) continue;
vis[front.y]=1;
sum+=front.cost;
for(int q=0;q<vec[front.y].size();q++) {
que.push(vec[front.y][q]);
}
}
return sum;
}
int main(){
cin>>n>>k;
int u,v,val,sum1=0,sum2=0;
init();
for(int q=0;q<k;q++){
cin>>u>>v>>val;
sum1+=val;
vec[u].push_back(edge(v,val));
vec[v].push_back(edge(u,val));
}
int k=prim();
cout<<sum1-k<<endl;
return 0;
}
京公网安备 11010502036488号