贪心算法-最小生成树
最小生成树
1.Prim算法(O(n^2))
策略: 每次都选择到下一顶点权最小的边
#include<iostream> #include <cstring> using namespace std; #define N 100 #define Max 9999 void Prim(int n,int c[][N]) { int lowcost[N],closest[N]; bool s[N]; s[1]=true; //从第一个点开始 //初始化 for(int i=2;i<=n;i++) { lowcost[i]=c[1][i]; //记录到当前节点i最小距离 closest[i]=1; //记录到当前节点i最小距离的节点1 s[i]=false; //未更新 } for(int i=1;i<n;i++) { //找最小距离,一个一个把点加进去 int min=Max; int j=1; //找到距离最小的点j(第一步是和1最小的点) for(int k=2;k<=n;k++) { if((lowcost[k]<min)&&(!s[k])) { min=lowcost[k]; j=k; } } cout<<closest[j]<< <<j<<endl; //标记j已被找到 s[j]=true; //在这里, lowcost[k]为结点k的最小距离, //有可能是之前的点,也可能是新加入的结点j //所以这里需要更新 for(int k=2;k<=n;k++) { if((c[j][k]<lowcost[k])&&(!s[k])) { lowcost[k]=c[j][k]; closest[k]=j; } } } } int main() { int point,edgenum,x,y,len,c[N][N]; memset(c,Max,sizeof(c)); cin>>point>>edgenum; for(int i=1;i<=edgenum;i++) { cin>>x>>y>>len; c[x][y]=len; c[y][x]=len; } Prim(point,c); return 0; }
2. Kruskal
#include <iostream> #include <cstdlib> #define MAXN 10000 + 10 using namespace std; int par[MAXN], Rank[MAXN]; typedef struct { int a, b, price; }Node; Node a[MAXN]; //排序 int cmp(const void*a, const void *b) { return ((Node*)a)->price - ((Node*)b)->price; } //初始化 void Init(int n) { for(int i = 0; i < n; i++) { Rank[i] = 0; par[i] = i; } } //找到x的根 int find(int x) { int root = x; while(root != par[root]) //par[]保存集体老大 root = par[root]; while(x != root) { int t = par[x]; par[x] = root; x = t; } return root; } void unite(int x, int y) //把x和y加到一起 { x = find(x); y = find(y); if(Rank[x] < Rank[y]) par[x] = y; else { par[y] = x; if(Rank[x] == Rank[y]) Rank[x]++; } } //n为边的数量,m为村庄的数量 int Kruskal(int n, int m) { int nEdge = 0, res = 0; //将边按照权值从小到大排序 qsort(a, n, sizeof(a[0]), cmp); for(int i = 0; i < n && nEdge != m - 1; i++) { //判断当前这条边的两个端点是否属于同一棵树 if(find(a[i].a) != find(a[i].b)) { unite(a[i].a, a[i].b); res += a[i].price; //res保存权值之和 nEdge++; //nEdge保存加入的边数 cout<<a[i].a+1<<" "<<a[i].b+1<<endl; } } //如果加入边的数量小于m - 1,则表明该无向图不连通,等价于不存在最小生成树 if(nEdge < m-1) res = -1; return res; } int main() { int n, m; cin>>m>>n; Init(m); for(int i = 0; i < n; i++) { cin>>a[i].a>>a[i].b>>a[i].price; //将村庄编号变为0~m-1(这个仅仅只是个人习惯,并非必要的) a[i].a--; a[i].b--; } cout<<Kruskal(n, m)<<endl; return 0; }
下一篇:
最小生成树和贪心算法