最小生成樹:使用堆和并查集的kruskal算法
頭文件：
Code#include <queue>
#include <functional>
#include <vector>
并查集：
Codeclass UFset
{
public :
vector<int> parent;
UFset(int n);
int Find( int );
void Union( int , int );
} ;
UFset::UFset(int n)
{
parent.resize(n);
}
int UFset::Find( int x)
{
if (parent[x] <= 0 )
return x;
else
{
parent[x] = Find(parent[x]);
return parent[x];
} // 壓縮路徑
}
void UFset::Union( int x, int y)
{
int pX = Find(x);
int pY = Find(y);
int tmp;
if (pX != pY)
{
tmp = parent[pX] + parent[pY]; // 加權合并
if (parent[pX] > parent[pY])
{
parent[pX] = pY;
parent[pY] = tmp;
}
else
{
parent[pY] = pX;
parent[pX] = tmp;
}
}
}
#include <queue>
#include <functional>
#include <vector>
kruskal算法:
Codestruct Edge
{
double dis;
int v,w;
bool operator<(const Edge &e1)const
{
return dis<e1.dis;
}
bool operator>(const Edge &e1)const
{
return dis>e1.dis;
}
Edge(int vv,int ww,double diss)
{
v=vv;
w=ww;
dis=diss;
}
};
priority_queue<Edge,vector<Edge>,greater<Edge>> e;//邊集
priority_queue<Edge,vector<Edge>,less<Edge>> te;//生成樹的邊集
int p;//頂點數
UFset u(p+1);
int k=0;
while(e.size()&&k<p-1)
{
Edge x=e.top();
e.pop();
int a=u.Find(x.w);
int b=u.Find(x.v);
if (a!=b)
{
te.push(x);
u.Union(a,b);
}
}
浙公網安備 33010602011771號