ufset.c

完全由C语言实现的图的相关操作

#include "stdafx.h"
Status InitUFSet(UFSet* set,int n)
{//初始化并查集
  int i; 
  for( i=0;i<n;i++)
  {
      set[i].parent =-1;/* 开始每个节点单独构成一个集合 */
      set[i].rank = 0;/* 权值视具体情况付初值 */
  }
  return OK;
}

int UFSetFind(UFSet* set,int x)
{//初始条件：存在并查集set，和要查找的元素x，x一定在某个集合中
//操作结果：返回该元素所属于的集合
  int i,temp;
  for(i=x;set[i].parent>0;i=set[i].parent);//查找到根i
  /* 压缩路径以提高以后检索效率 */
  while(x!=i)     
  {
      temp=set[x].parent;
      set[x].parent=i;
      x=temp;
  }
  return i;
}


int Union(UFSet* set,int a,int b)
{//初始条件：存在并查集set,集合a,集合b
//操作结果：合并集合a，b
  int fa =UFSetFind(set,a); //a的根结点
  int fb =UFSetFind(set,b); //b的根结点
  if(fa==fb) return 0;
  if(set[fa].parent<=set[fb].parent)
  {
      set[fa].parent+=set[fb].parent;
      set[fb].parent =fa;

  }
  else
  {
      set[fb].parent+=set[fa].parent;
      set[fa].parent =fb;
  }
  return 0;
}