Prim算法是对点集的操作
首先做一个struct Node{
int key;//保存当前点与下一个点的最短距离
int v;//当前点的编号
friend bool operator <(Node a,Node b)
{
return a.key>b.key;
}//用来处理优先队列
}
Node vx[ MAXN ];//用来保存所有点的元素
priority_queue<Node> q;
visit [ MAXN ];///来标记是否访问
最一开始 初始化所有信息
void Prim()
{
for(int i=1;i<=n;i++)
{
visit[i]=0;
vx[i].key=INF;
vx[i].v=i;
}
q.push(vx[1]);
while(!q.empty())
{
Node tmp=q.top();
q.pop();
int st=tmp.v;
if(visit[st]==1)//如果这个点访问过 就不遍历
continue;
visit [ st ]=1;
for( int j=1;j<=n;j++)
{
if(j!=st && G[ st ][ j ]<tmp.key && visit[j]==0)
{
tmp.key=G[ st ] [ j ];
q.push( vx[ j ] );
}
}
}
}
最后将vx[ ]中的key相加 就是ans
就是每个点与相邻点的最小的距离的和
Kruskal是对边集的计算
根据边的weight来从小到大排序
每条边判断两个端点是不是一个根节点
如果不是加入
并查集函数
int FIND(int x)
{
if(parent[x] ==-1)
return x;
else
return FIND( parent [x] );
}
void kruskal() { ans=0; for(int i=0;i<m;i++) { int t1=Find(e[i].from); int t2=Find(e[i].to); if(t1!=t2) { ans+=e[i].w; parent[t2]=t1; } } }
