首页 > 代码库 > E - Agri-Net (最小生成树) -- prim算法
E - Agri-Net (最小生成树) -- prim算法
http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=193#problem/E
prim算法 思想和步骤总结 （自己所写）
dis【】，map【】【】，vis【】，pos ，min，ans（主要定义的变量）
首先，prim算法用于计算图边径长度已知的图，它所求的是将图中所有顶点相连接，所需要的最短路径的长度，prim算法适合计算稠密图，它的主要思想是贪心思想，贪心准则为每次选择未加入树中且距离树最小的顶点，并用dis【】数组不断更新各个顶点到树的距离，由于顶点数有N个，所以要加入N次，初始化一个顶点，先将一个顶点加入树中，剩余的将进入n-1次循环逐步加入树中。再加入树中后，需要进行松弛操作，更新dis【】数组，使dis【】数组中的数值始终是未加入树中的顶点到生成的树的最短距离。
具体步骤以及需要注意点
1.在未加入边之前先将图初始化，将图中点与点之间的距离初始化为无穷，点本身的距离为0.
2. 根据题目要求输入边的长度，不要忘记判断现有长度和新加入的边的长度进行比较，只有新加入边的长度小于现有边的长度才更新它
3.先随机选择一个点加入树中，（判断点是否加入树中，需要借助vis【】，数组，若vis【1】 = 1，表明 1号节点已加入树中）
4.下一步将进行n-1次循环，选择n-1个点加入树中，每次通过 j循环遍历所有的点判断距离，找出最短距离，加入树中。
5.将最短距离加入 ans上 ans += min；
6.进行松弛操作 ，也需要遍历所有的点，只有该节点未被访问并且该节点到新加入的节点 pos 的距离小于到树的距离 ，则更新之。
if(!vis[j] && dis[j]>map[pos][j])
dis[j] = map[pos][j];
#include <stdio.h>#include <string.h>#define INF 1<<20int map[101][101];int dis[101];int vis[101];long long ans;void prim(int n){ int i,j; memset(dis,INF,sizeof(dis)); vis[1] = 1; dis[1] = 0; for(i = 1;i<=n;i++) { dis[i] = map[1][i]; } int min,pos; for(i = 1;i<=n-1;i++) { min = INF; for(j = 1;j<=n;j++) { if(!vis[j] && dis[j]<min) { min = dis[j]; pos = j; } } vis[pos] = 1; ans += min; for(j = 1;j<=n;j++) { if(!vis[j] && dis[j]>map[pos][j]) dis[j] = map[pos][j]; } }}int main(){ int n; int i,j; while(scanf("%d",&n)!=EOF) { memset(vis,0,sizeof(vis)); for(i = 1;i<=n;i++) { for(j = 1;j<=n;j++) { scanf("%d",&map[i][j]); } } prim(n); printf("%lld\n",ans); ans = 0; } return 0;}