알고리즘 - 크루스칼

- Kruskal

- 탐욕적인 방법(greedy method), 간선 선택 기반  

- 간선들을 가중치의 오름차순으로 정렬, 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가

- 시간복잡도 

- union-find 연산 (사이클, 집합)

  

#define MAX_VERTECS 100

int parent[MAX_VERTECS]; // 부모 노드
int num[MAX_VERTECS]; // 각 집합의 크기

// 초기화
void set_init(int n)
{
	int i;
	for(i=0; i<n; i++) {
		parent[i] = -1;
		num[i] = 1;

	}
}

// vertext가 속하는 집합을 반환한다.
int set_find(int vertex)
{
	int p, s, i = -1;
	for(i = vertex; (p=parent[i])>=0; i=p) // 루트 노드까지 반복
		;
	s = i; // 집합의 대표 원소(최상위 부모노드)
	for(i = vertex; (p=parent[i])>=0; i=p)
		parent[i] = s; // 집합의 모든 원소들의 부모를 s로 설정
	return s;
}

// 두 개의 원소가 속한 집합을 합친다.
void set_union(int s1, int s2)
{
	// 연산량을 줄이기 위해 정점의 개수가 적은 트리의 루트가 큰 트리의 루트를 가리키도록 함
	if(num[s1] < num[s2]) { 
		parent[s1] = s2;
		num[s2] += num[s1];
	}
	else {
		parent[s2] = s1;
		num[s1] += num[s2];
	}
}