是什么：

• 一個有 n 個結(jié)點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結(jié)點，并且有保持圖連通的最少的邊。

kruskal算法：

#include<iostream> #include<vector> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; struct node {int x,y,t; }; int n,m,fa[100001]; int mincost; bool cmp(node a,node b) {return a.t<b.t; } int find(int x) {if(fa[x]==x) return x;else return find(fa[x]); } int main() {while(cin>>n) {if(n==0) return 0;mincost=0;memset(fa,0,sizeof(fa));vector<node> g;cin>>m;for(int i=1; i<=n; i++) fa[i]=i;int x,y,t;for(int i=1; i<=m; i++) {cin>>x>>y>>t;g.push_back((node) {x,y,t});}sort(g.begin(),g.end(),cmp);for(int i=0; i<g.size(); i++) {int u=g[i].x;int v=g[i].y;double w=g[i].t;if(find(u)!=find(v)) {mincost+=w;fa[find(u)]=find(v);}}cout<<mincost<<endl;} }

時間復(fù)雜度：O(mlogm) m為邊數(shù)

prim算法：

#include<iostream> #include<cstring> using namespace std; bool vis[101]; int n,x,y,z,ans=0,d[101]={1,},g[101][101]; int prim(int s){int index=s;vis[s]=true;for(int i=1;i<=n;i++)d[i]=g[s][i];for(int i=1;i<n;i++){int minn=99999999;for(int j=1;j<=n;j++){if(!vis[j]&&d[j]<minn){minn=d[j];index=j;}}vis[index]=true;ans+=minn;for(int j=1;j<=n;j++){if(!vis[j]&&d[j]>g[index][j]){d[j]=g[index][j];}}} } int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>g[i][j];}}prim(1);cout<<ans;return 0; }

時間復(fù)雜度：O(n^2)
主要用于稠密圖，尤其是完全圖的最小生成樹

拓展：次小生成樹

普及版：

#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int inf=1e9; struct node{int u,v,w,vis; }e[20010]; vector<int> g[2005]; int n,m,fa[2005],len[2005][2005]; int minn,nd; bool cmp(node a,node b) {if(a.w!=b.w)return a.w<b.w;if(a.u!=b.u)return a.u<b.u;return a.v<b.v; } int find(int x) {if(x!=fa[x])return fa[x]=find(fa[x]);return fa[x]; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);}sort(e+1,e+m+1,cmp);for(int i=0;i<=n;i++){g[i].clear();g[i].push_back(i);fa[i]=i;}minn=0;for(int i=1;i<=m;i++){int x=find(e[i].u);int y=find(e[i].v);if(x!=y){e[i].vis=1;minn+=e[i].w;int a=g[x].size();int b=g[y].size();for(int j=0;j<a;j++)for(int k=0;k<b;k++)len[g[x][j]][g[y][k]]=len[g[y][k]][g[x][j]]=e[i].w;fa[x]=y;int cpy[110];for(int j=0;j<b;j++)cpy[j]=g[y][j];for(int j=0;j<a;j++)g[y].push_back(g[x][j]);for(int j=0;j<b;j++)g[x].push_back(cpy[j]);}}nd=inf;for(int i=1;i<=m;i++)if(!e[i].vis)nd=min(nd,minn+e[i].w-len[e[i].u][e[i].v]);printf("%d\n",nd);return 0; }

提高版：

嚴格次小生成樹

博客

Boruvka算法：

博客

時間復(fù)雜度：O((n+m)logn)

常用于解決這類問題：給你n個點，每個點有點權(quán)，任意兩個點之間有邊權(quán)，邊權(quán)為兩個點權(quán)用過某種計算方式得出，求最小生成樹。

題目
題解

總結(jié)

以上是生活随笔為你收集整理的MST(最小生成树)的构造的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。