算法的基本思想
算法设计
算法构造过程
编码实现
#include<iostream>
using namespace std;
void Prim(int n,int u0,int C[6][6]){
//定点个数n,开始顶点u0,带权邻接矩阵
bool s[n];//s[i]=true,表明顶点i已加入最小生成树的定点集合U,否则顶点i属于集合V-U
int closest[n];//closet[j]表示V-U中的顶点j在集合U中的最近邻接顶点
double lowcost[n];//lowcost[j]表示V-U中的顶点j到U中的所有顶点的最短边的权值
s[u0]=true; //初始时，集合U中只有一个元素，即顶点U
int flag[6];
int m=0;
flag[m++]=u0;//用于存放加入到集合U的下标，该数组可按顺序输出加入点的顺序
for(int i=0;i<n;i++){
if(i!=u0){
lowcost[i]=C[u0][i];
closest[i]=u0;
s[i]=false;
}
}
for(int i=0;i<n;i++){//在集合V-U中寻找距离集合U最近的顶点并且更新lowcost和closest
double temp=100;
int t=u0;
for(int j=0;j<n;j++){//在集合V-U中寻找距离集合U最近的顶点t
if((!s[j])&&(lowcost[j]<temp)){
t=j;
temp=lowcost[j];
}
}
if(t==u0) break; //找不到t,跳出循环
s[t]=true;//否则，将t加入到集合U
flag[m++]=t;
for(int j=0;j<n;j++){//更新lowcost和closest
//?????????????????????, 这里开始不懂，后来懂了
//就是每次加入顶点时，不是在V-U中所有未加入的顶点中找一个顶点离刚加入的顶点最近
//而是在V-U中 所有未加入的顶点中找一个顶点离所有已加入的顶点最近
if((!s[j])&&C[t][j]<lowcost[j]){//更新lowcost和closest
lowcost[j]=C[t][j];
closest[j]=t;
}
}
}
for(int i=0;i<n;i++){
//输出V中加入顶点的次序，输出的数字代表该定点的下标，即顶底编号减去1
cout<<flag[i]<<" ";
}
cout<<endl;
int sum=0;
for(int i=0;i<n;i++){
sum+=lowcost[i];
}
cout<<sum; //输出最小生成树的权值
}
int main(){
int n=6;
int u0=0;
int C[6][6]={{0,6,1,5,100,100},{6,0,5,100,3,100},{1,5,0,5,6,4},{5,100,5,0,100,2},{100,3,6,100,0,6},{100,100,4,2,6,0}};
Prim(n,u0,C);
}
