kruskal 算法

发表于 更新于 分类于 阅读次数：

  kruskal算法的主要思想就是从当前路径中选择一个不能构成环的最小边加入

for (int i=1;i<n;i++)
{
int mi=1000000,k;
for (int j=0;j<m;j++)
{
if ((v[e[j].x] + v[e[j].y]==1 || i==1 ) && e[j].d<mi){ mi=e[j].d; k=j; } } result.push_back(k); v[e[k].x]=1; v[e[k].y]=1; if (mi>ma) ma=mi;
}

因为此算法本质上是一个贪心策略，可以通过并查集进行优化，现将其从小到大排序

int kruskal()//返回最小生成树的和
{
int ans=0;
qsort(e,e+n,cmp);//cmp是将其按d值从小到大排序
for (int i=0;i<m;i++)//m is the number of edges
{
if (find(e[i].x)!=find(e[i].y)) {//判断边的两个端点是否在一个集合
result.push_back(i);
ans+=e[i].d;
}
}
return ans;
}

poj 1861

#include
#include
#include
#include
using namespace std;
struct P{
    int x,y,d;
};
P e[15100];
vector result;
int ma=-1;
int v[1002]={0};
int main()
{
    int n,m;
    scanf(“%d%d”,&n,&m);
    for (int i=0;i<m;i++)
        scanf(“%d%d%d”,&e[i].x,&e[i].y,&e[i].d);
    for (int i=1;i<n;i++)
    {
        int mi=1000000,k;
        for (int j=0;j<m;j++)
        {
            if ((v[e[j].x] + v[e[j].y]==1 || i==1 ) && e[j].d<mi){                 mi=e[j].d;                 k=j;             }         }         result.push_back(k);         v[e[k].x]=1;         v[e[k].y]=1;         if (mi>ma) ma=mi;
    }
    cout<<ma<<endl;
    cout<<result.size()<<endl;
    for (int i=0;i<result.size();i++)
    {
        cout<<e[result[i]].x<< “ “<<e[result[i]].y<<endl;
    }
    return 0;
}