首页分享最小生成树算法解析

最小生成树算法解析

来源：花匠小妙招时间：2024-12-20 19:02

求最小生成树，两种算法，求输出权值的和。第一行n,m，n为顶点数，小于等于20，m边数，后面m行，每行一个边的信息，每行三个数，i j c，起点i，终点j，权值c，i，j大于等于1，无向图。

/*求最小生成树，，求输出权值的和。第一行n,m，n为顶点数，小于等于20，m边数，后面m行，每行一个边的信息，每行三个数 i j c，起点i，终点j，权值c，i，j大于等于1，无向图。*/ #include <iostream> #include <cstring> using namespace std; #define mai 1001 int i,j,k; int arr[mai][mai]; int prim(int arr[][mai],int n)//加点法 { //vis数组用来记录这个点是否已经加入最小生成树 int vis[mai] = {0}; //dis数组表示当前最小生成树（集体）的可以到达的非最小生成树的点的最小距离 int dis[mai] = {0}; memset(vis,0,sizeof(vis)); int sum = 0,min = mai,number; for(i = 2;i <= n;i++) dis[i] = arr[1][i];//从1开始，dis数组初始化 vis[1] = 1; //从第二次访问开始（并不是第二个点），控制一共访问n次，所有的点已访问 for(i = 2;i <= n;i++) { min = mai;number = -1;//每次访问新点时重新赋值min for(j = 1;j <= n;j++) { if(vis[j] == 0 && dis[j] < min) { min = dis[j]; number = j;//number记录当前最小权值的下标，方便vis标记 } } //这个for执行完之后就可以找到dis数组里面的最小权值是min，对应的点是j sum += min; vis[number]=1;//将j点标记为已加入 for(j = 1;j <= n;j++) if(vis[j] == 0 && arr[number][j] < dis[j]) dis[j] = arr[number][j]; } return sum; } int main() { int n,m,i,j,c; cin >> n >> m; for(i = 0;i <= n;i++) for(j = 0;j <= n;j++) arr[i][j] = mai; for(i = 0;i < m;i++) { cin >> i >> j >> c; arr[i][j] = c; arr[j][i] = c; } int small = prim(arr,n); cout << small << endl; return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define INF 0x3f3f3f3f typedef long long ll; using namespace std; int cost[1020][1020];//cost[u][v]表示边e=(u,v)的权值（不存在的情况下设为INF） int mincost[1020];//从集合X出发的边到每个顶点的最小权值 bool used[1020];//顶点i是否包含在集合X中 int prime(); int n,m,i,j,c; int main() { cin >> n >> m; memset(cost,INF,sizeof(cost)); for(int i = 0;i < m;i++) { cin >> i >> j >> c; cost[i][j] = min(c,cost[i][j]); cost[j][i] = min(c,cost[j][i]); } cout<<prime()<<endl; return 0; } int prime() { for(int i = 1;i <= n;i++) { mincost[i] = INF; used[i] = false; } mincost[1] = 0; int res = 0; while(true) { int v = -1;//从不属于X的顶点中选取从X到其权值最小的顶点 for(int u=1;u <= n;u++) { if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u; } if(v == -1)break; used[v] = true;//把顶点v加入X res += mincost[v];//把边的长度加到结果里 for(int u = 1;u <= n;u++) mincost[u] = min(mincost[u],cost[v][u]); } return res; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455