크루스칼 알고리즘(Kruskal algorithm)

크루스칼 알고리즘에 대해 배워보겠습니다. 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 그니깐 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 실제로 여러 개의 도시 연결을 위해 도로 건설 최소 비용을 위해 적용되는 알고리즘 입니다. 

 

그래프 용어를 정리해 보겠습니다. 

노드 = 정점 = node = 도시 : 그래프에서 동그라미

간선 = 거리 = edge = 비용 : 그래프에서 선 

 

이 그림의 노드 개수는 7개이고 간선의 개수는 11개입니다. 즉 7개의 도시, 11개의 도로인거죠.

 

 

크루스칼 알고리즘의 핵심은 다음과 같습니다.

 

정렬 후 비용이 작은 ( 거리가 짧은) 순서대로 그래프에 포함시키자.

 

모든 노드를 최소 비용 연결시키는 게 목적이니 모든 노드를 오름차순으로 정렬하고 낮은 거 부터 연결시키면 최소 비용 신장 트리를 찾을 수 있을 겁니다. 

일단 위와 같이 모든 간선들의 정보를 저장합니다. 이에 대해 오름차순 정렬을 수행하면

 

(1, 7, 12) (4, 7, 13) (1, 5, 17) (3, 5 ,20) (2, 4, 24) (1, 4, 28) (3, 6, 37) (5, 6, 45) (2, 5, 62) (1, 2, 67) (5, 7, 73) 

 

오름차순 정렬이 됩니다.

 

이제 다음 알고리즘에 맞게 그래프를 연결하시면 가장 적은 비용으로 모든 노드를 연결한 그래프인 '최소 비용 신장 트리'가 만들어집니다.

 

1. 정렬된 순서에 맞게 그래프에 포함시킵니다.

2. 포함시키기 전에는 사이클 테이블을 확인합니다. 

3. 사이클을 형성하는 경우 간선을 포함시키지 않습니다.

 

왜 사이클을 형성하는 경우 간선을 포함시키지 않을까요? 사이클이 형성되면 최소 비용 신장 트리가 될 수 가 없습니다. 그림을 보면 간단히 이해가 되실 겁니다.

모든 노드를 연결할 때 사이클이 형성되지 않아야 최소가 됩니다. 모든 노드를 연결하기만 하면 되는데 사이클이 형성될 필요가 없죠. 

 

그렇기 때문에 최소 신장 비용 트리는 간선의 개수가 노드 -1 입니다.

 

사이클이 발생하는지의 여부는 Union-Find 알고리즘을 적용하시면 됩니다. 다음 포스팅을 보시면 쉽게 이해하실 수 있으실 겁니다.

https://com24everyday.tistory.com/117

Union-Find(합집합찾기)

 

아래 그림은 초기 상태입니다.

 

(1, 7, 12) (4, 7, 13) (1, 5, 17) (3, 5 ,20) (2, 4, 24) (1, 4, 28) (3, 6, 37) (5, 6, 45) (2, 5, 62) (1, 2, 67) (5, 7, 73) 

 

 

이제 첫번째 간선부터 쭉 선택하면서 크루스칼 알고리즘을 시작해보겠습니다. 

 

(1, 7, 12) (4, 7, 13) (1, 5, 17) (3, 5 ,20) (2, 4, 24) (1, 4, 28) (3, 6, 37) (5, 6, 45) (2, 5, 62) (1, 2, 67) (5, 7, 73) 

 

두번째 간선을 선택해보겠습니다.

(1, 7, 12) (4, 7, 13) (1, 5, 17) (3, 5 ,20) (2, 4, 24) (1, 4, 28) (3, 6, 37) (5, 6, 45) (2, 5, 62) (1, 2, 67) (5, 7, 73) 

 

 

세번째 간선을 선택해보겠습니다.

(1, 7, 12) (4, 7, 13) (1, 5, 17) (3, 5 ,20) (2, 4, 24) (1, 4, 28) (3, 6, 37) (5, 6, 45) (2, 5, 62) (1, 2, 67) (5, 7, 73) 

네번째 간선을 선택해보겠습니다.

(1, 7, 12) (4, 7, 13) (1, 5, 17) (3, 5 ,20) (2, 4, 24) (1, 4, 28) (3, 6, 37) (5, 6, 45) (2, 5, 62) (1, 2, 67) (5, 7, 73) 

 

다섯번째 간선을 선택해보겠습니다.

(1, 7, 12) (4, 7, 13) (1, 5, 17) (3, 5 ,20) (2, 4, 24) (1, 4, 28) (3, 6, 37) (5, 6, 45) (2, 5, 62) (1, 2, 67) (5, 7, 73) 

여섯번째 간선을 선택해보겠습니다. 근데 1,4를 연결해야하는데 둘의 부모노드가 1로 같습니다. 이 말은 같은 집합 안에 속한다는 거죠. 즉 연결이 되면 사이클이 형성됩니다. 그러니 연결을 하면 안됩니다. 넘어가서 (3, 6, 37) 를 연결합니다.

(1, 7, 12) (4, 7, 13) (1, 5, 17) (3, 5 ,20) (2, 4, 24) (1, 4, 28) (3, 6, 37) (5, 6, 45) (2, 5, 62) (1, 2, 67) (5, 7, 73) 

사이클 테이블을 보면 모든 부모 노드가 동일한 거를 볼 수 있습니다. 그러니 모든 노드가 연결되었습니다. 크루스칼 알고리즘이 끝났습니다. 

 

 

이제 소스코드로 구현해보겠습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
// 부모 노드를 찾는 함수 
int getParent(int parent[], int x){
	if(parent[x]==x) return x; //부모노드가 없을때
	return parent[x] = getParent(parent,parent[x]); 
} 

// 두 부모 노드를 합치는 함수
int unionParent(int parent[], int a, int b){
	a = getParent(parent,a);
	b = getParent(parent,b);
	//인덱스 값이 작은 걸 부모 노드로 정함 
	if(a < b) parent[b] = a; 
	else parent[a] = b;
} 

//같은 부모를 가지는지 확인하는 함수 
int findParent(int parent[], int a,int b){
	a = getParent(parent,a);
	b = getParent(parent,b);
	if(a == b)
		return 1;
	return 0;
} 

//간선 클래스 선언
class Edge{
	public:
		int node[2];
		int distance;
		Edge(int a, int b, int distance){
			this->node[0] = a;
			this->node[1] = b;
			this->distance = distance;
		}
		bool operator <(Edge &edge){
			return this->distance < edge.distance;
			//거리가 작은 거 출력  
		}
}; 

int main(void){
	int n = 7; //노드 갯수 
	int m = 11; //간선 갯수 
	
	vector<Edge> v;
	v.push_back(Edge(1,7,12));
	v.push_back(Edge(1,2,67));
	v.push_back(Edge(1,5,17));
	v.push_back(Edge(1,4,28));
	v.push_back(Edge(2,4,24));
	v.push_back(Edge(2,5,62));
	v.push_back(Edge(3,5,20));
	v.push_back(Edge(3,6,37));
	v.push_back(Edge(4,7,13));
	v.push_back(Edge(5,7,73));
	v.push_back(Edge(5,6,45));
	
	//간선의 비용을 기준으로 오름차순 정렬
	sort(v.begin(),v.end());
	
	//각 정점이 포함된 그래프가 어디인지 저장
	int parent[n];
	for(int i = 0;i < n; i++){
		parent[i] = i;
	} 
	
	int sum = 0;
	for(int i = 0; i < v.size();i++){
		//사이클이 발생하지 않는 경우 그래프에 포함
		//같은 부모를 가지면 안됨 
		if(!findParent(parent,v[i].node[0]-1,v[i].node[1]-1)){
			sum+= v[i].distance;
			unionParent(parent,v[i].node[0]-1,v[i].node[1]-1);
		} 
	}
	printf("%d\n",sum);
} 

 

 

오늘은 크루스칼 알고리즘에 대해 배워보았습니다. 수고하셨습니다. 

 

 

 

 

 

※이 글은 나동빈님 강의 후기를 포스팅했습니다.

https://blog.naver.com/ndb796/221230994142

18. 크루스칼 알고리즘(Kruskal Algorithm)