Disjoint Sets

Data Structures for Disjoint Sets

 

• Partition

      – A partition of a set X is a set of non-empty subsets of X such that every element x in X is

         in exactly one of these subsets.

      – Example: X = {1, 2, 3, 4, 5, 6} → { {1, 3, 5}, {2}, {4, 6} }

 

• Disjoint-set data structure (union-find data structure)

      – Used to effectively manage a collection of subsets that partition a given set of elements.

 

• Basic operations on disjoint sets

      – Makeset(x)

            • Make a set containing only the given element x.

      – S = Find(x)

            • Determine which set the particular element x is in.

                  – Typically return an element that serves as the subset’s representative.

                  – May be used to determine if two elements are in the same subset.

                  – Union(x, y) (or Merge(x, y))

            • Merge two subsets into a single subset.

 

 

예를 들어서 X = {a, b, c, d, e} 에 대해서 Makeset, Find, Union 에 대한 것을 살펴본다.

(1)  X에 속한 모든 원소들에 대하여 부모가 자기 자신을 가르키도록 한다.

       for(int x : X)   Makeset(x);   =>   {a}, {b}, {c}, {d}, {e}

(2) a, c에 대한 집합을 묶으려고 할 때 Union(a, c) 를 호출하면 다음과 같다.

      => Union(a, c);   :  {a, c}, {b}, {d}, {e} 

(3)  a에 속한 집합의 모든 원소는 Find(a) 를 호출하여 알 수 있다.

      => Find(a) = {a, c}

 

 

Union 을 구현하는데 있어서 두가지 방법이 존재한다.

 

 

 

단순히 시간복잡도 관점에서만 바라보도록 하자. 

O(n) : Tree의 depth가 n에 가깝게 증가하게 될 경우로 worst case 관점에서 바라본다면 O(n) 이 걸린다.

O(logn) : Tree의 depth가 logn에 가깝게 될 수록 O(logn) 이 걸린다.

 

Union by rank

• Always attach the smaller tree to the root of the larger tree.

• The rank increases by one only if two trees of the same rank are merged. 

      ✓ The rank of a one-element tree is zero.

• The Union and Find operations can be done in O(log n) in the worst case.

      ✓ The number of elements in a tree of rank r is at least 2^r. (Proof by induction)

      ✓ The maximum possible rank of a tree with n elements is O(log n).

 

rank, parent 변수를 이용하여 Union - find 를 구현해보도록 하자.

 

int parent[1000001], rank[1000001];

void Makeset(int x)
{
	parent[x] = x;
	rank[x] = 0;
}

int Find(int x)
{
	while (x != parent[x])
		x = parent[x];
	return x;
}

void Union(int x, int y)
{
	int x0, y0;
	x0 = Find(x);
	y0 = Find(y);
	if (x0 == y0)
		return;
	if (rank[x0] > rank[y0])
		parent[y0] = x0;
	else {
		parent[x0] = y0;
		if (rank[x0] == rank[y0])
			rank[y0] = rank[y0] + 1;
	}
}

 

시간 복잡도에 대한 분석

Makeset :  O(1)

Find : O(logn)

Union : O(2logn + 1) = O(logn)

 

int Find(int x)
{
	if (x == parent[x])
		return x;
	return Find(parent[x]);
}

 

Find 함수는 위와 같이 수정이 가능하다.

 

 

Disjoint set의 Path compression 연산

 

 

 

 

path compression 연산을 이용하여 왼쪽 사진을 오른쪽 사진과 같이 Set 를 이룰 수 있다.

이에 대한 코드를 확인해보도록 한다.

 

int Find(int x)
{
	if (x == parent[x])
		return x;
	return (parent[x] = Find(parent[x]));
}

 

 

Kruskal's Algorithm

 

크루스칼 알고리즘을 활용하여 MST 를 구현해보도록 하자.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Edge {
	int src, dest, weight;
};

struct Graph {
	int V, E;
	struct Edge* edge;
};

struct Graph* createGraph(int V, int E){
	struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
	graph->V = V;
	graph->E = E;
	graph->edge = (struct Edge*)malloc(graph->E * sizeof(struct Edge));
	return graph;
}

struct subset {
	int parent;
	int rank;
};

int find(struct subset subsets[], int i) {
	if (subsets[i].parent != i)
		subsets[i].parent = find(subsets, subsets[i].parent);
	return subsets[i].parent;
}

void Union(struct subset subsets[], int x, int y) {
	int xroot = find(subsets, x);
	int yroot = find(subsets, y);
	if (subsets[xroot].rank < subsets[yroot].rank)
		subsets[xroot].parent = yroot;
	else if (subsets[xroot].rank > subsets[yroot].rank)
		subsets[yroot].parent = xroot;
	else {
		subsets[yroot].parent = xroot;
		subsets[xroot].rank++;
	}
}

int myComp(const void* a, const void* b) {
	struct Edge* a1 = (struct Edge*) a;
	struct Edge* b1 = (struct Edge*)b;
	return a1->weight - b1->weight;
}

void KruskalMST(struct Graph* graph) {
	int V = graph->V;
	struct Edge* result;
	result = (struct Edge*)malloc((V - 1) * sizeof(struct Edge));
	int e = 0;
	int i = 0;
	qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
	struct subset* subsets = (struct subset*)malloc(V * sizeof(struct subset));
	for (int v = 0; v < V; v++) {
		subsets[v].parent = v;
		subsets[v].rank = 0;
	}
	while (e < V - 1) {
		struct Edge next_edge = graph->edge[i++];
		int x = find(subsets, next_edge.src);
		int y = find(subsets, next_edge.dest);
		if (x != y) {
			result[e++] = next_edge;
			Union(subsets, x, y);
		}
	}
	printf("Following are the edges in the constructed MST\n");
	for (i = 0; i < e; i++)
		printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
	return;
}

int main()
{
	int V = 4;
	int E = 5;
	struct Graph* graph = createGraph(V, E);

	graph->edge[0].src = 0;
	graph->edge[0].dest = 1;
	graph->edge[0].weight = 10;

	graph->edge[1].src = 0;
	graph->edge[1].dest = 2;
	graph->edge[1].weight = 6;

	graph->edge[2].src = 0;
	graph->edge[2].dest = 3;
	graph->edge[2].weight = 5;

	graph->edge[3].src = 1;
	graph->edge[3].dest = 3;
	graph->edge[3].weight = 15;

	graph->edge[4].src = 2;
	graph->edge[4].dest = 3;
	graph->edge[4].weight = 4;

	KruskalMST(graph);
	
	return 0;
}