最小生成树之Prim贪心算法
设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。
代码：
C++
#include<iostream>??
#include<fstream>??
using??namespace std;??
??
#define MAX 100??
#define MAXCOST 0x7fffffff??
??
int graph[MAX][MAX];??
??
int prim(int graph[][MAX], int n)??
{??
????int lowcost[MAX];??
????int mst[MAX];??
????int i, j, min, minid, sum = 0;??
????for (i = 2; i <= n; i++)??
????{??
????????lowcost[i] = graph[1][i];??
????????mst[i] = 1;??
????}??
????mst[1] = 0;??
????for (i = 2; i <= n; i++)??
????{??
????????min = MAXCOST;??
????????minid = 0;??
????????for (j = 2; j <= n; j++)??
????????{??
????????????if (lowcost[j] < min && lowcost[j] != 0)??
????????????{??
????????????????min = lowcost[j];??
????????????????minid = j;??
????????????}??
????????}??
????????cout << "V" << mst[minid] << "-V" << minid << "=" << min << endl;??
????????sum += min;??
????????lowcost[minid] = 0;??
????????for (j = 2; j <= n; j++)??
????????{??
????????????if (graph[minid][j] < lowcost[j])??
????????????{??
????????????????lowcost[j] = graph[minid][j];??
????????????????mst[j] = minid;??
????????????}??
????????}??
????}??
????return sum;??
}??
??
int main()??
{??
????int i, j, k, m, n;??
????int x, y, cost;??
????ifstream in("input.txt");??
????in >> m >> n;//m=顶点的个数，n=边的个数??
????//初始化图G??
????for (i = 1; i <= m; i++)??
????{??
????????for (j = 1; j <= m; j++)??
????????{??
????????????graph[i][j] = MAXCOST;??
????????}??
????}??
????//构建图G??
????for (k = 1; k <= n; k++)??
????{??
????????in >> i >> j >> cost;??
????????graph[i][j] = cost;??
????????graph[j][i] = cost;??
????}??
????//求解最小生成树??
????cost = prim(graph, m);??
????//输出最小权值和??
????cout << "最小权值和=" << cost << endl;??
????system("pause");??
????return 0;??
}本文参与?腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-05-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读