yuanyuelang

常用链接

统计

最新评论

最小生成树之Kruskal算法

最小生成树是图论的一个重要部分，解决这个问题的算法主要有Kruskal算法和Prim算法。

最小生成树:顾名思义是一棵树，该树是图中权值和最小的。

我们先来介绍Kruskal算法，Prim算法请参阅最小生成树之Prim算法

该算法的基本思路：贪心，如何贪心呢？
它的贪心准则是：
1.每次从剩下的边中选择一个不会产生环路而且权值最小的边加入到已经选择好的边的集合中。
2.它需要e步的操作，e表示图的边数，我们可以按权值排好序后，对每一条边进行选择，如果加入到已经选择好的边中会产生回路的现象，就不要了。。。否则加入到已经选择好的边中。
3.我们还需用到并查集的思想，有关并查集的介绍，请查看我的另一篇博文 不相交集合数据结构
4.复杂度：O(ElgE)，其中E为图的边数

接下来我们引用POJ上的一个经典题目来分析，题目网址http://acm.pku.edu.cn/JudgeOnline/problem?id=1861

题目大意是：题目给出的是图的顶点和所有边的集合，要求输出的是最小生成树的边

我们来看下源码啦：
#include<iostream>
using namespace std;
#include<algorithm>
#include <memory.h>

#define MAXEDGE 15001//最大边数
#define MAXNODE 1001 //最大节点数

int p[MAXNODE],rank[MAXNODE];//用于不相交集合
int start[MAXEDGE],end[MAXEDGE],weight[MAXEDGE],VNum,ENum;//分别为边的起点，终点，权重，节点数和边数
int result_s[MAXEDGE],result_e[MAXEDGE];//分别为存储最小生成树的起点，终点
int max_weight,id[MAXEDGE];

void make_set(int x)
{
    p[x]=x;
    rank[x]=0;
}

int find_set(int x)
{ 
    if(p[x]!=x)
        p[x]=find_set(p[x]);
    return p[x];
}

void Union(int x,int y)
{
    x=find_set(x);
    y=find_set(y);
    if(rank[x]>rank[y])
        p[y]=x;
    else if(rank[x]<rank[y])
        p[x]=y;
    else if(rank[x]==rank[y])
    {
        p[x]=y;
        rank[y]++;
    }
}

bool cmp(int i,int j)//用于sort函数
{
    return weight[i]<weight[j];
}
void Kruskal()
{
    int i,min,index=0,count=0,k=0;
    
    max_weight=0;
        for(i=1;i<=VNum;i++)
          make_set(i);
    
        sort(id,id+ENum,cmp);//对所有边进行排序，注意id数组的妙用
    while(true){
      min=id[index++];
      if(find_set(start[min])!=find_set(end[min])){ //对每条边进行处理，如果起点和终点不在同一集合合并之
        Union(start[min],end[min]);
        result_s[k]=start[min];//保存结果
                result_e[k++]=end[min];
                count++;
        if(max_weight<weight[min])
                max_weight=weight[min];
       }
      
        if(count==VNum-1) break;//当边数等于节点数-1的时候表示已经完成
    }
}





int main()
{
    int i;
    cin>>VNum>>ENum;
    for(i=0;i<ENum;i++){
        cin>>start[i]>>end[i]>>weight[i];
        id[i]=i;
    }
        Kruskal();
        cout<<max_weight<<endl<<VNum-1<<endl;
        for(i=0;i<VNum-1;i++)
       cout<<result_s[i]<<" "<<result_e[i]<<endl;
   
        return 0;
}

posted on 2009-09-13 21:18 原语饿狼 阅读(685) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理