/ C

알고리즘 정복하기 with C (4)Kruskal's Algorithm

알고리즘 정복하기 with C (4)Kruskal’s Algorithm

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 알고리즘은 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 알고리즘을 코딩하면서 공부하기로 했습니다.

Kruskal’s Algorithm

탐욕적인 방법(Greedy Approach) 을 이용하여 가중치를 간선에 할당한 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 알고리즘입니다. 처음부터 끝으로 유지하며 트리가 만들어지는 Prim 알고리즘과는 다르게 가중치를 기준으로 트리를 만들기 때문에 사이클이 생길 수 있어 이를 검사해주는 부분이 필요합니다.

Greedy Approach

  • 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것
  • 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다.
  • Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다.
  • MST(최소 비용 신장 트리) 가 최소 비용의 간선으로 구성되고 사이클을 포함하지 않는 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 합니다.

Kruskal’s Algorithm pseudo code

Kruskal’s Algorithm 의 pseudo code

void kruskal(int n, int m, set_of_edges E, set_of_edges& F) {
  index i, j;
  set_pointer p, q;
  edge e;
  
  sort the m edges in E by weight in nondecreasing order;
  F=;
  initial(n); //서로소로 초기화
  while(number of edges in F is less than n-1) {
    e = edges with least weight not yet considered;
    i, j= indices of verticies connected by e;
    p = find(i); //vi가 속한 집합을 찾음
    q = find(j); //vj가 속한 집합을 찾음
    if(!equal(p,q)) {  //p와 q, 즉 두 정점의 루트가 같은지 비교
      merge(p,q);  //다르면 합침
      add e to F;
    }
  }
}

Kruskal’s Algorithm 시간 복잡도

  1. sort the m edges in E by weight in nondecreasing order; => O(mlogm)
  2. initial(n); => O(n)
  3. while(number of edges in F is less than n-1) => O(m)
    • while문에서 find(n), find(m)의 n 과 m의 상관관계를 찾습니다.

따라서 시간 복잡도는 O(mn) = O(n^2)

Kruskal’s Algorithm 구현

입력데이터

소스코드

#include <stdio.h>
#include <stdbool.h>

#define vnum 6
#define enum 9

typedef struct edgeList {
	int weight;
	int first_vertex;
	int second_vertex;
}edgeList;

typedef struct nodetype {
	int parent;
	int depth;
}universe;

void kruskal(int n, int m, edgeList* E, edgeList* F);
void makeset(universe* U, int i);
int find(universe* U, int i);
void merge(universe* U, int p, int q);
bool equal(int p, int q);
void initial(universe* U, int n);
void makeNode(int vertex1, int vertex2, int w);

edgeList set_of_edges[enum];
int index = 0;
int f = 0;

int main()
{
	edgeList F[enum];

	makeNode(1, 2, 7);
	makeNode(1, 3, 11);
	makeNode(1, 6, 5);
	makeNode(2, 3, 3);
	makeNode(2, 4, 6);
	makeNode(3, 4, 10);
	makeNode(3, 5, 15);
	makeNode(4, 5, 7);
	makeNode(5, 6, 9);

	kruskal(vnum, enum, set_of_edges, F);

	for (int i = 0; i < f; i++) {
		printf("%d - %d -> 가중치: %d\n", F[i].first_vertex, F[i].second_vertex, F[i].weight);
	}

	return 0;
}

void kruskal(int n, int m, edgeList* E, edgeList* F)
{
	universe U[vnum + 1];

	for (int i = 0; i < m - 1; i++) {
		for (int j = 0; j < m - 1 - i; j++) {
			if (E[j].weight > E[j+1].weight) {
				edgeList temp = E[j];
				E[j] = E[j+1];
				E[j+1] = temp;
			}
		}
	}

	for (int i = 0; i < m; i++) {
		F[i].first_vertex = 0;
		F[i].second_vertex = 0;
		F[i].weight = 0;
	}

	for (int i = 1; i <= vnum; i++) {
		U[i].parent = 0;
		U[i].depth = 0;
	}

	initial(U, vnum);

	int index = 0, count = 0;
	while (count != 1) {
		count = 0;
		int i, j, p, q;
		edgeList e = E[index];

		i = e.first_vertex;
		j = e.second_vertex;

		p = find(U, i);
		q = find(U, j);

		if (!equal(p, q)) {
			merge(U, p, q);
			F[f] = e;
			f++;
		}	

		for (int i = 1; i <= enum; i++) {
			if (U[i].parent == i)
				count++;
		}
		index++;
	}
}

void makeset(universe* U, int i)
{
	U[i].parent = i;
	U[i].depth = 0;
}

int find(universe* U, int i)
{
	int j;
	j = i;

	while (U[j].parent != j) {
		j = U[j].parent;
	}
	return j;
}

void merge(universe* U, int p, int q)
{
	if (U[p].depth == U[q].depth) {
		U[p].depth += 1;
		U[q].parent = p;
	}
	else if (U[p].depth < U[q].depth)
		U[p].parent = q;
	else
		U[q].parent = p;
}

bool equal(int p, int q)
{
	if (p == q)
		return true;
	else
		return false;
}

void initial(universe* U, int n)
{
	for (int i = 1; i <= n; i++)
		makeset(U, i);
}

void makeNode(int vertex1, int vertex2, int w)
{
	set_of_edges[index].first_vertex = vertex1;
	set_of_edges[index].second_vertex = vertex2;
	set_of_edges[index].weight = w;
	index++;
}

결과

Kruskal 알고리즘과 출력을 구현했습니다. 결과가 잘 나옵니다.

알고리즘 진행 과정 손계산

알고리즘의 진행과정을 직접 계산하여 결과를 비교해보았습니다. 결과가 동일하게 나옵니다.