Kruskal's Algorithm using Disjoint Set

Kruskal’s Algorithm using Disjoint Sets

• Consider edges in the same connected sub-graph as forming a set
• If the vertices of the next edge are in different sets, take the union of the two sets
• Do not add an edge if both vertices are in the same set

Example:

{B,C} creates a cycle (B and C are already in the same disjoint set)

Analysis

Worst Case:

• Checking if two vertices are in the same set is \(O(\lg(\lvert V\rvert))\)
• Taking the union of two disjoint sets is \(O(\lg(lvert V\rvert))\)
• Thus, checking and building the minimum spanning tree is now \(O(\lvert E\rvert \lg(\lvert V\rvert))\) Sorting the edges takes \(O(\lvert E\rvert \lg(\lvert E\rvert))= O(\lvert E\rvert \lg(\lvert V\rvert))\) The overall complexity: \(O(\lvert E\rvert \lg(\lvert V\rvert))\)

Coding: Kruskal

#include <cstio>
#include <algorithm>

class Edge{
public:
  int a, b;
  int weight;

  bool operator< (const Edge &_y) const{//operator overloading
    return(this-> weight<_y.weight);
  }
};

class Disjoin_Set{
public:
  int n;
  int *parent;
  int *height;

  Disjoint_Set(){}
  Disjoint_Set(int _n){
    this->n =_n;
    parent= new int [n];
    height= new int [n];

    for(int x=0; x<n; i++){
      parent[x]=x;
      height[x]=0;
    }  
  }

  int Find_Set(int _x){
    while(parent[_x] !=_x){
      _x = parent[_x];
    }
    return _x;
  }

  bool Union_Set(int _x, int _y){
    _x= Find_Set(_x);
    _y= Find_Set(_y);

    if(_x==_y){
      return false;
    }

    if(height[_x]>height[_y]){
      parent[_y]=_x;
    }
    else if(height[_x]<height[_y]){
      parent[_x]=_y;
    }
    else{
      parent[_y]=_x;
      height[_x]++;
    }
    return true;
  }
};

void Kruskal(Graph &_g){
  //_g.Print_Edges();
  //printf("\n");

  std::sort( &(_g.edges[0]), &(_g.edges[_g.nE]));
  //_g.Print_Edges();
  //printf("\n");

  Disjoint_Set ds(_g.nV);
  for(int i=0; i<_g.nE; i++){
    printf("%c %c %2d ", edges[i].a + 'A', edges[i].b + 'A', edges[i].weight);

    bool check = ds.Union_Set( _g.edges[i].a, _g.edges[i].b);
    if(check){
      printf(" O \n");
    }
    else{
      printf(" X \n");
    }
  }
}

int main(int argc, char **argv){
  Graph g;
  g.Init(argv[1]);

  Kruskal(_g);
  return 1;
}

class Graph{
public:
  int nV, nE;
  Edge *edges;

  void Init(const char *_filename){
    FILE *input = fopen(_filename, "r");
    fscanf(input, "%d", &nV);
    fscanf(input, "%d", &nE);
    edges= new Edge [nE];
    for(int i=0; i<nE; i++){
      char x, y; int w;
      fscanf(input, "%c %c %d", &x, &y, &w);
      edges[i].a=(int)(x-'A');//A=0, B=1, ....
      edges[i].b=(int)(y-'A');
      edges[i].weight=w;
    }
    fclose(input);
  }
  void Print_Edges(){
    for(int i=0; i<nE; i++){
      printf("%c %c %2d\n", edges[i].a + 'A', edges[i].b + 'A', edges[i].weight);
    }
  }
};

source “K-MOOC 허재필 교수님의 <인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고> 강좌의 12-2 서로소 집합과 크루스칼 알고리즘 중(http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2020_T1)”

back next

Comments

Post comment

Loading...