Kruskal 알고리즘

Programmers의 Greedy Kits 중 [섬 연결하기] 문제를 풀다가 좋은 방법이 없을까? 해서 찾게된 알고리즘.

​

Kruskal 알고리즘이란?

Greedy method를 이용하여 가중치를 간선에 할당한 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해를 구하는 알고리즘

​

👉 Greedy method: 결정을 해야 할 때마다, 그 순간에 가장 좋다고 생각하는 것을 선택하며 최종적인 해답에 도달하는 것. 반드시 검증이 필요하다.

👉 최소 비용 신장트리 만드는 법: 1) 최소 비용의 간선으로 구성되며, 1) 사이클을 포함하지 않음의 조건에 근거해서 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택.

​

Kruskal 알고리즘의 동작

1. 그래프들의 간선들을 가중치의 오름차순으로 정렬

2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택

- 즉, 가장 낮은 가중치를 먼저 선택

- 사이클을 형성하는 간선은 제외 (사이클 형성하는지는 어떻게 알지? 🤷🏻‍♀️)

3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가

​

🤷🏻‍♀️ 사이클을 생성하는지는 어떻게 체크할까? 🤷🏻‍♀️

- 추가할 새로운 간선의 양 끝 정점이 같은 집합에 속해 있으면 사이클이 형성된다.

- union-find 알고리즘을 이용

​

---

union-find 알고리즘

union-find 알고리즘을 알기 위해서는 먼저 Disjoint Set이라는 자료구조를 먼저 알아야 한다.

​

Disjoint Set이란?

서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조. (서로소 집합 자료구조)

​

union-find란?

집합을 트리구조를 이용하여 구현.

아래의 세 가지 연산을 이용하여 Disjoint Set을 표현한다.

● make-set(x): 초기화. x를 유일한 원소로 하는 새로운 집합을 생성.

● union(x, y): 합치기. x가 속한 집합과 y가 속한 집합을 합친다.

● find(x): 찾기. x가 속한 집합의 루트 노드 값을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산

​

​

union-find의 기본적인 구현 방법

/* 초기화 */ 
int root[MAX_SIZE]; 
for (int i = 0; i < MAX_SIZE; i++) 
	parent[i] = i; 
    
/* find(x): 재귀 이용 */ 
int find(int x) { 
	if (root[x] == x) { 
    	return x;
    } else { 
    	return find(root[x]); 
    }
} 

/* union(x, y) */ 
void union(int _x, int _y){ 
	int x = find(_x); 
    int y = find(_y); 
    root[y] = x; 
}

위의 구현 방법은 기본 적인 구현 방법이며, 최적화를 위해서는 아래와 같은 코드를 사용한다.

​

​

find 연산 최적화

경로를 압축. 시간 복잡도는 O(logN)의 값을 가진다.

int find(int x) { 
	if (root[x] == x) { 
    	return x; 
    } else { 
    // find 하면서 만난 모든 값의 부모 노드를 root로 만든다. 
    	return root[x] = find(root[x]); 
    }
}

union 연산 최적화

rank에 트리의 높이를 저장한 후, 항상 높이가 더 낮은 트리를 높은 트리 밑에 넣는다.

void union(int x, int y){ 
	x = find(x); 
    y = find(y); 
    
    // 두 값의 root가 같으면(이미 같은 트리) 합치지 않는다. 
    if(x == y) 
    	return; 
        
    // 항상 높이가 더 낮은 트리를 높이가 높은 트리 밑에 넣는다. 즉, 높이가 더 높은 쪽을 root로 
    if(rank[x] < rank[y]) { 
    	root[x] = y; // x의 root를 y로 변경 
    } else { 
    	root[y] = x; // y의 root를 x로 변경 
        
    if(rank[x] == rank[y]) 
    	rank[x]++; // 만약 높이가 같다면 합친 후 (x의 높이 + 1) 
    }
}

​