- 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]; } }


'Algorithm' 카테고리의 다른 글

알고리즘 - 다익스트라  (0) 2015.11.14
알고리즘 - 프림  (0) 2015.11.13
알고리즘 - 너비 우선 탐색  (0) 2015.11.13
알고리즘 - 깊이 우선 탐색  (0) 2015.11.13
알고리즘 - 정렬 알고리즘 비교  (2) 2015.11.12

+ Recent posts