小根堆 并查集实现Kruskal算法.doc

//kruskal算法,VC++
//kruskal用于无向图的最小生成树
//稀疏图
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
//并查集的实现
//---------------------------------------------------------------------
const int MAXNUM=101;
int parent[MAXNUM]; //parent[i]=j表示j是i的父母
int rank[MAXNUM]; //rank[i]是i的高度的一个上界
void make_set(int x) //建立单元素集合,父结点为自己,秩为0
{
parent[x]=x;
rank[x]=0;
}
//find_set是一种两趟方法,一趟是沿查找路径上升,直至找到根
//第二趟是沿查找路径下降,以便更新每个结点,使之直接指向根
//此为带路径压缩的查找
int find_set(int x)
{
if(x!=parent[x])
parent[x]=find_set(parent[x]);
return parent[x];
}
//合并x所属的集合和y所属的集合为一个集合
void union_set(int x,int y)
{
x=find_set(x);
y=find_set(y);
if(rank[x]>rank[y]) //让较高的秩作为父结点
{
parent[y]=x;
}
else
{
parent[x]=y;
if(rank[x]==rank[y]) //如果秩相等,怎任选一方作为父结点,同时秩升1
++rank[y];
}
}
//---------------------------------------------------------------------
//9*9,图的路径
int MAP[MAXNUM][MAXNUM]={
{INT_MAX, 2,INT_MAX,INT_MAX,INT_MAX, 9, 15,INT_MAX,INT_MAX},
{ 2,INT_MAX, 4,INT_MAX,INT_MAX,INT_MAX, 6,INT_MAX,INT_MAX},
{INT_MAX, 4,INT_MAX, 2,INT_MAX,INT_MAX,INT_MAX,INT_MAX, 15},
{INT_MAX,INT_MAX, 2,INT_MAX, 1,INT_MAX,INT_MAX,INT_MAX, 1},
{INT_MAX,INT_MAX,INT_MAX, 1,INT_MAX, 6,INT_MAX, 3,INT_MAX},
{ 9,INT_MAX,INT_MAX,INT_MAX, 6,INT_MAX,INT_MAX, 11,INT_MAX},
{ 15, 6,INT_MAX,INT_MAX,INT_MAX,INT_MAX,INT_MAX, 15, 2},
{INT_MAX,INT_MAX,INT_MAX,I