prim算法求最小生成树
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：V
new = {x}，其中x为集合V中的任一节点（起始点），E
new = {},为空；
3).重复下列操作，直到V
new = V：
a.在集合E中选取权值最小的边<u, v>，其中u为集合V
new中的元素，而v不在V
new
集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合V
new中，将<u, v>边加入集合E
new中；
4).输出：使用集合V
new和E
new来描述所得到的
最小生成树。
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <iomanip>
using namespace std;
string s[2005];
int w[2005][2005],n;
int compare(string a,string b)
{
int len=0;
for(int i=0;i<7;i++)
if(a[i]!=b[i])len++;
return len;
}
int prim()
{
int inf=20;
int zx[2005];
memset(zx,0,sizeof(zx));
int low_dis[2005];
memset(low_dis,inf,sizeof(low_dis));
int len=0,sum=1;
int len1,p;
int s=0;
zx[s]=1;
while(sum!=n)
{
len1=inf;
for(int j=1;j<n;j++)
{
if(!zx[j]&&w[s][j]<low_dis[j])
{
low_dis[j]=w[s][j];
}
if(!zx[j]&&len1>low_dis[j])
{
len1=low_dis[j];
p=j;
}
}
s=p;
zx[s]=1;
sum++;
len+=len1;
}
return len;
}
int main()
{
while(cin>>n&&n!=0)
{
for(int i=0;i<n;i++)
cin>>s[i];
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
w[i][j]=w[j][i]=compare(s[i],s[j]);
cout<<"The highest possible quality is 1/"<<prim()<<'.'<<endl;
}
return 0;
}
