思想
对图G(V ,E)设置集合S来存放已经被访问的顶点,然后执行下面两个步骤,共执行n次。
a、每次从集合V-S中选择与集合S最近的一个顶点u(所谓最近,是指集合S中某一顶点v到V-S中的顶点u之间的边权最小,则u作为离S最近的顶点),访问u并加入集合S,同时把这条离集合S最近的边加入最小生成树中。
b、令顶点u作为集合S与集合V-S连接的接口,优化从u能到达的未访问的顶点v与集合S的最短距离。
具体实现:1、类比Dijkstra算法,使用一个bool类型的数组visit[]表示顶点是否已被访问。visit[i]==true表示顶点的Vi已被访问,为false时表示未被访问。
2、令int型数组d[]来存放顶点Vi与集合S的最短距离。初始时除了起点s的d[s]=0,其余顶点用INF来表示不可达。
3、每次从d[]中选则最小的,记录下标为minNum,标记已被访问,并且将d[minNum]累加到sum(边权值之和)中,然后对从minNum出发的所有顶点v,如果使u作为中介点,可以使得d[v]更小。则优化d[v]。
一、基于邻接矩阵
int prim_Matrix() { //默认从0号顶点开始求最小生成树
fill(d, d + MAX, INF);
d[0] = 0;
int sum = 0;//最小生成树边权之和
for (int i = 0; i < n; ++i) {
int minNum = -1, minDistance = INF;
for (int j = 0; j < n; ++j) {
if (visit[i] == false && d[i] < minDistance) {//选择最小的d[j]
minNum = i;
minDistance = d[i];
}
}
if (minNum == -1) return -1;
visit[minNum] = true;//minNum加入S
sum += d[minNum];
for (int v = 0; v < n; ++v) {
if (visit[v] == false && G[minNum][v] != INF && d[v] > G[minNum][v]) {
d[v] = G[minNum][v];//更新d[v]
}
}
}
return sum;
}
二、基于邻接表
struct Node {
int v, dis;//v为目标顶点,dis为边权
};
vector<Node> Adj[MAX];//邻接表
int prim_Adj() { //默认从0号顶点开始
fill(d, d + MAX, INF);
d[0] = 0;
int sum = 0;
for (int i = 0; i < n; ++i) {
int minNum = -1, minDistance = INF;
for (int j = 0; j < n; ++j) {
if (visit[j] == false && d[j] < minDistance) {
minNum = j;
minDistance = d[j];
}
}
if (minNum == -1) return -1;
visit[minNum] = true;
sum += d[minNum];
for (int j = 0; j < Adj[minNum].size(); ++j) {
int v = Adj[minNum][j].v;
if (visit[v] == false && Adj[minNum][v].dis < d[v])
d[v] = Adj[minNum][v].dis;
}
}
return sum;
}