设G（V，E）是无向；联通带权图，对图中每一条边（u，v）的权威c[u][v] ， 表示联通u与v的代价，如果G的子图T是一颗包含G的所有顶点的树，则称T为G的生成树，生成树上的权总和成为该生成树的耗费，在G的所有生成树中耗费最小的生成树成为G的最小生成树。 一般来说krukskal算法比较简单且适合稠密图，而prim适合稀疏图
krukskal算法 算法实现：首先将G的n个顶点看成是n个孤立的连通分量，将所有边的权值从小到大排序，然后从第一条边开始，依边递增查看，若看到第i条边（u，v）时，如果端点属于不同的连通分量中的顶点时（用到并查集），就用当前的边（u，v）将其连接起来，当只剩下一个联通分量的时候，该连通分量就为G的一颗最小生成树。 模板： #include <cstdio> #include <algorithm> using namespace std ; const int N = 2e5 + 5 ; int s[N] ; struct node { int x , y , w ; }; node egde[N] ; bool cmp(node a , node b){ return a.w < b.w ; } int find(int x){ if (x != s[x]) s[x] = find(s[x]) ; return s[x] ; } int main(){ int n , m ; scanf ("%d%d",&n,&m) ; for (int i = 1 ; i <= n ; ++ i) s[i] = i ; for (int i = 1 ; i <= m ; ++ i) scanf ("%d%d%d",&egde[i].x,&egde[i].y,&egde[i].w) ; sort(egde+1,egde+1+m,cmp) ; int cost = 0 ; for (int i = 1 ; i <= m ; ++ i){ int a = find(egde[i].x) , b = find(egde[i].y) ; if (a != b){ s[a] = b ; n -- ; cost += egde[i].w ; } if (n == 1){ printf ("%d\n",cost) ; return 0 ; } } if (n > 1) printf ("orz\n") ; return 0 ; }详解移步大佬：prim解说 主要就是从未选择的点中选择权值最小的边所对的点加入生成树，直到全部点都加入了生存树。
#include <cstdio> #include <vector> using namespace std ; const int N = 5005 ; const int INF = 1e6 ; int low[N] , graph[N][N] ; bool done[N] ; int n , m ; void prim(int u){ //起点u int sum = 0 ; for (int i = 1 ; i <= n ; ++ i){ low[i] = graph[u][i] ; //寻找与起点u 相连的边的权值 done[i] = false ; } done[u] = true ; int j = 1 ; for (int i = 1 ; i < n ; ++ i){ //处理其他n-1个顶点 int min = INF ; //在low数组中找未加入生成树的最小值 for (int k = 1 ; k <= n ; ++ k) { if ((low[k] < min) && (!done[k])){ min = low[k] ; j = k ; } } //加入结点j done[j] = true ; sum += low[j] ; for (int k = 1 ; k <= n; ++ k){ if (low[k] > graph[j][k] && (!done[k])){ low[k] = graph[j][k] ; //更新与j相连的权值 } } } printf ("%d\n",sum) ; } int main(){ scanf ("%d%d",&n,&m) ; for (int i = 1 ; i <= n ; ++ i){ //初始化 for (int j = 1 ; j <= m ;++ j){ if (i == j) graph[i][j] = 0 ; else graph[i][j] = INF ; } } while(m--){ //建图 int u , v , w ; scanf ("%d%d%d",&u,&v,&w) ; //路径重复时选择权值小的保存 graph[u][v] = graph[u][v] < w ? graph[u][v] : w ; graph[v][u] = graph[u][v] ; } prim(1) ; return 0 ; }不过以上的prim做法时间复杂度较大，可以用堆优化降低时间复杂度
#include <cstdio> #include <vector> #include <queue> using namespace std ; const int N = 5005 ; const int INF = 1e6 ; struct edge{ int to , w ; edge(int a , int b){to = a ; w = b ;} ; }; struct node{ int id , dis ; node(int a , int b){id = a ; dis = b ;} ; bool operator < (const node &c) const { return dis > c.dis ; } }; int d[N] ; bool done[N] ; int n , m , cnt ; vector<edge> e[N] ; void prim(int u){ //起点 int sum = 0 ; for (int i = 1 ; i <= n ; ++ i){ d[i] = INF ; done[i] = false ; } priority_queue<node> q ; d[u] = 0 ; q.push(node(u,0)) ; while(!q.empty() && cnt<n){ int head = q.top().id ; q.pop() ; if (done[head]) continue ; done[head] = true ; ++ cnt ; sum += d[head] ; for (int i = 0 ; i < e[head].size() ; ++ i){ edge t = e[head][i] ; if (done[t.to]) continue ; if (d[t.to] > t.w){ d[t.to] = t.w ; q.push(node(t.to,d[t.to])) ; } } } if (cnt == n) printf ("%d\n",sum) ; else printf ("orz\n") ; } int main(){ scanf ("%d%d",&n,&m) ; while(m --){ int u , v , w ; scanf ("%d%d%d",&u,&v,&w) ; e[u].push_back(edge(v,w)) ; e[v].push_back(edge(u,w)) ; } prim(1) ; }