目录
1. 概述
2. 代码实现
3. 代码验证：hdu 4463 Outlets
参考文献
1. 概述
初始化一个数组 U，存储已经遍历的节点(数组U初始化可以为任何一个，一般为v1)，不断的找与“已遍历节点距离最短”的节点加入到数组U中，等到所有的节点都加入到U中，所选择的n-1条“最短边”和n个节点即为该树的最小生成树。
举一个例子，图中有 6 个节点（V1，V2、V3、V4、V5、V6），边上的数字就是节点之间的距离。
数组U初始化为V1、不断的找与“已遍历节点距离最短”的节点加入到数组U中。
第一次找到的是 v3 ， 如b所示。
第二次找到的是 v6 ， 如c所示。
第三次找到的是 v4 ， 如d所示。
第四次找到的是 v2， 如e所示。
第五次找到的是 v5， 如f所示。
2. 代码实现
代码实现需要一个辅助数组: closeedge[]， closeedge[i] 代表的是 起始点到达 点 i 的最短距离，closeedge[i] 初始为起始点到达其他节点的一条边距离，即 a[sta] [] 这一行。
每次找到一个与“已遍历节点距离最短”的节点加入到数组U中，需要去更新辅助数组: closeedge[]，因为添加了一个节点，数组U中的节点可以到达更多的节点，选择更优的道路。解释一下更优的道路：例如节点A到节点B之间的距离为5，新加入一个节点C，节点A到节点C之间的距离为1,节点C到节点B之间的距离为2，1+2<5 , 显然有了一条更优的道路。
// Prim 算法实现
// 时间复杂度：n^2, n 为 节点数#include <stdio.h>
#include <string.h>
#include <limits.h>
#define N 1010// vis 存储每个点是否已经遍历 ，
// dis 从已经遍历过的点 到未遍历点的最短距离
typedef struct point{int vis, dis;
}P;
P closedge[N];// 存储图， a[i][j] 点 i 到点 j 距离
int a[N][N];
const int INF = 1000000007;//n 总点数， sta 为最小生成树的初始点
int lct(int n,int sta) {int lowcost = 0; // 初始最小的花费for(int i=1; i<=n; i++) {if(i != sta) {closedge[i].vis = 0; // 标记未遍历closedge[i].dis = a[sta][i]; // 更新}}closedge[sta].vis = 1;for(int i=2; i<=n; i++) {// minDist 找到最短的一条边的长度， minj 加入最短边的点的标号int minDist = INF, minj;for(int j=1; j<=n; j++) {if(closedge[j].vis == 0 && closedge[j].dis < minDist) {minj = j;minDist = closedge[j].dis;}}lowcost += minDist;closedge[minj].vis = 1;printf("%d\n",minj); // 遍历过程中经过的点for(int j=1; j<=n; j++) {if(closedge[j].vis == 0 && a[minj][j] <= closedge[j].dis) {closedge[j].dis = a[minj][j];}}}return lowcost;
}
int main()
{int n;scanf("%d",&n); // n 个点for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)a[i][j] = INF; // 初始图int x, y, dis;for(int i=1; i<=n; i++) {scanf("%d %d %d",&x,&y,dis);a[x][y] = dis;}printf("%d\n",lct(n, 1));return 0;
}
3. 代码验证：hdu 4463 Outlets
用下面的一道题，验证下代码。
Outlets
Problem Description
In China, foreign brand commodities are often much more expensive than abroad. The main reason is that we Chinese people tend to think foreign things are better and we are willing to pay much for them. The typical example is, on the United Airline flight, they give you Haagendazs ice cream for free, but in China, you will pay $10 to buy just a little cup.
So when we Chinese go abroad, one of our most favorite activities is shopping in outlets. Some people buy tens of famous brand shoes and bags one time. In Las Vegas, the existing outlets can't match the demand of Chinese. So they want to build a new outlets in the desert. The new outlets consists of many stores. All stores are connected by roads. They want to minimize the total road length. The owner of the outlets just hired a data mining expert, and the expert told him that Nike store and Apple store must be directly connected by a road. Now please help him figure out how to minimize the total road length under this condition. A store can be considered as a point and a road is a line segment connecting two stores.
Input
There are several test cases. For each test case: The first line is an integer N( 3 <= N <= 50) , meaning there are N stores in the outlets. These N stores are numbered from 1 to N. The second line contains two integers p and q, indicating that the No. p store is a Nike store and the No. q store is an Apple store. Then N lines follow. The i-th line describes the position of the i-th store. The store position is represented by two integers x,y( -100<= x,y <= 100) , meaning that the coordinate of the store is (x,y). These N stores are all located at different place. The input ends by N = 0.
Output
For each test case, print the minimum total road length. The result should be rounded to 2 digits after decimal point.
Sample Input
42 30 01 00 -1 1 -10
Sample Output
3.41
题意：
n 个 店铺，建路， 找到最小花费， 就是求最小生成树， 不过 第 p, q 个店铺之间必须需建一条路。
代码：
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#define N 100
typedef struct point{int vis;double dis;
}P;
P closedge[N];
double a[N][N], pos[N][2];
const double INF = 1000000007;
int p, q;
double lct(int n,int sta)
{double lowcost = 0;for(int i=1; i<=n; i++){if(i != sta){closedge[i].vis = 0;closedge[i].dis = a[sta][i];}}closedge[sta].vis = 1;closedge[q].vis = 1; //先建 p 到 q 的路lowcost += a[p][q];for(int j=1; j<=n; j++){if(closedge[j].vis == 0 && a[q][j] <= closedge[j].dis){closedge[j].dis = a[q][j];}} //先建 p 到 q 的路for(int i=3; i<=n; i++) // 更新后面 n - 3 个点{double min = INF;int minj;for(int j=1; j<=n; j++){if(closedge[j].vis == 0 && closedge[j].dis < min){minj = j;min = closedge[j].dis;}}lowcost += min;closedge[minj].vis = 1;//printf("%.2f %d\n",min,minj);for(int j=1; j<=n; j++){if(closedge[j].vis == 0 && a[minj][j] <= closedge[j].dis){closedge[j].dis = a[minj][j];}}}return lowcost;
}
int main()
{int n;while(scanf("%d",&n)){if(n == 0) break;scanf("%d %d",&p,&q);for(int i=1; i<=n; i++){scanf("%lf %lf",&pos[i][0],&pos[i][1]);}for(int i=1; i<=n; i++) // 初始 图{for(int j=i; j<=n; j++){if(i == j){a[i][j] = INF;}else{a[i][j] = sqrt(pow((pos[i][0] - pos[j][0]), 2) + pow((pos[i][1] - pos[j][1]), 2));a[j][i] = a[i][j];}}}printf("%.2f\n",lct(n, p)); // 最小生成树的初始点 p}return 0;
}
参考文献
- 数据结构 - 严蔚敏、吴伟民 - 清华大学出版社