알고리즘 ] 크루스칼 알고리즘

정의

---

크루스칼(Kruskal) 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다. 

즉, 최소 신장 트리를 만들기 위한 대표적인 알고리즘이다.

 

트리(tree) ]
사이클이 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프

신장 트리(spanning tree) ]
간선의 수가 가장 적게 연결한 그래프
n개의 정점을 가지는 그래프에 (n-1)개의 간선을 가지는 그래프

최소 시장 트리(MST, minimum spaning tree) ]
가중치, 무방향 그래프의 신장트리에서 간선들의 가중치 합이 최소인 그래프

 

 

시간 복잡도

---

 

크루스칼 알고즘은 정렬을 한 후, union-find 알고리즘을 진행하는 과정을 거친다. 

그러므로 시간복잡도는 정렬알고리즘과 union-find 알고리즘의 시간복잡도를 더한 것과 같다.

union-find은 압축의 과정을 거치면 O(1), 거치지 않으면 O(logN)의 시간 복잡도를 가지므로, 결국 정렬알고리즘을 어떤 걸 사용하느냐에따라 크루스칼 알고리즘의 시간복잡도가 달라지게 된다. 

 

javascript 의 sort()는 퀵정렬을 이용하므로 O(NlogN)의 시간복잡도를 가진다.

곧, 크루스칼 알고리즘은 O(NlogN)의 시간복잡도를 가진다.

 

 

알고리즘 실행 순서

---

크루스칼 알고리즘은 그래프에서 비용이 적은 간선들을 차례로 그려나간다. 그 중에 사이클을 생성하는 간선은 건너뛰고 진행한다. 그러면 비용이 적은 간선들로 이어져있는 신장트리를 얻게 된다.

동작과정을 자세히 살펴보자.

1. 데이터를 초기화 한다.
    1) 그래프를 간선의 가중치기준 오름차순 정렬한다.
    2) 각 노드의 집합을 자기 자신으로 초기화 한다.
        (노드를 간선으로 연결하면 하나의 집합으로 묶어서 사이클이 발생하는지 확인하는 용도로 사용)

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인하고,
   발생시키지 않으면 최소 신장 트리에 포함시킨다.
   (같은 집합에 있는 노드를 연결하면 사이클이 발생한다)

3. 모든 간선에 대해 2번의 과정을 반복한다.

 

---

다음의 그래프에서 최소 신장 트리를 찾아보자.

노드의 수가 총 6개이므로 5개의 간선으로 최소의 값을 낼 수 있는 간선들을 분홍색 선으로 표현하였다.

분홍색 선만 따로 떼서 트리를 만들어 보면 최소 신장 트리가 된다.

---

Javascript 크루스칼 알고리즘 구현 방법

---

// 그래프
const edges = [
	['A', 'B', 3],
	['A', 'D', 11],
	['A', 'C', 5],
	['B', 'C', 9],
	['B', 'E', 1],
	['C', 'D', 13],
	['C', 'F', 15],
	['E', 'F', 7],
];

 

1) 데이터를 초기화 한다.

// 1) 그래프를 간선의 가중치기준 오름차순 정렬한다.
function kuruskal() {
	edges.sort((a, b) => a[2] - b[2]);

}

// 2) 각 노드의 집합을 자기 자신으로 초기화 한다.
const parent = {
	A: 'A',
	B: 'B',
	C: 'C',
	D: 'D',
	E: 'E',
	F: 'F',
};

edges 가 다음과 같이 정렬된다.
[
  [ 'B', 'E', 1 ],
  [ 'A', 'B', 3 ],
  [ 'A', 'C', 5 ],
  [ 'E', 'F', 7 ],
  [ 'B', 'C', 9 ],
  [ 'A', 'D', 11 ],
  [ 'C', 'D', 13 ],
  [ 'C', 'F', 15 ]
]

 

 

2) 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인하고, 발생시키지 않으면 최소 신장 트리에 포함시킨다.

// union-find 알고리즘


// node가 속한 집합을 찾는다.
function getParent(x) {
	if (parent[x] === x) return x;
	return getParent(parent[x]);
}

// 두 노드를 연결한다
function union(x, y) {
	const a = getParent(x);
	const b = getParent(y);

	if (a < b) {
		parent[b] = a;
	} else {
		parent[a] = b;
	}
}

// 두 노드의 집합이 같은지 다른지 확인한다.
function find(x, y) {
	const a = getParent(x);
	const b = getParent(y);

	return a === b;
}

function kuruskal() {
	edges.sort((a, b) => a[2] - b[2]);

	let result = 0;

    // 정렬된 간선들을 하나씩 확인한다.
	edges.forEach((a) => {
		const [x, y, cost] = a;

		// 두 노드의 집합이 서로 같지 않으면
		if (!find(x, y)) {
			// 두 노드를 연결한다
			union(x, y);
			
			// 노드를 연결한 비용을 계산한다.
			result += cost;
		}
	});

	return result;
}

 

그림으로 위의 알고리즘을 확인해보면, 연결하려고 하는 집합이 같으면 최소신장트리에 추가하지 않음을 볼 수 있다.

순서1 ]
집합 : { A: 'A', B: 'B', C: 'C', D: 'D', E: 'E', F: 'F' }
node B, node E 연결 => 비용 1

순서2 ]
집합 : { A: 'A', B: 'B', C: 'C', D: 'D', E: 'B', F: 'F' }
node A, node B 연결 => 비용 3

순서3 ]
집합 : { A: 'A', B: 'A', C: 'C', D: 'D', E: 'B', F: 'F' }
node A, node C 연결 => 비용 5

순서4 ]
집합 : { A: 'A', B: 'A', C: 'A', D: 'D', E: 'B', F: 'F' }
node E, node F 연결 => 비용 7

순서5 ]
집합 : { A: 'A', B: 'A', C: 'A', D: 'D', E: 'B', F: 'A' }
node B, node C 사이클 발생

순서6 ]
집합 : { A: 'A', B: 'A', C: 'A', D: 'D', E: 'B', F: 'A' }
node A, node D 연결 => 비용 11

순서7 ]
집합 : { A: 'A', B: 'A', C: 'A', D: 'A', E: 'B', F: 'A' }
node C, node D 사이클 발생

순서8 ]
집합 : { A: 'A', B: 'A', C: 'A', D: 'A', E: 'B', F: 'A' }
node C, node F 사이클 발생

 

전체 코드

---

const edges = [
	['A', 'B', 3],
	['A', 'D', 11],
	['A', 'C', 5],
	['B', 'C', 9],
	['B', 'E', 1],
	['C', 'D', 13],
	['C', 'F', 15],
	['E', 'F', 7],
];

const parent = {
	A: 'A',
	B: 'B',
	C: 'C',
	D: 'D',
	E: 'E',
	F: 'F',
};

function getParent(x) {
	if (parent[x] === x) return x;
	return getParent(parent[x]);
}

function union(x, y) {
	const a = getParent(x);
	const b = getParent(y);

	if (a < b) {
		parent[b] = a;
	} else {
		parent[a] = b;
	}
}

function find(x, y) {
	const a = getParent(x);
	const b = getParent(y);

	return a === b;
}

function kuruskal() {
	edges.sort((a, b) => a[2] - b[2]);
	console.log(edges);

	let result = 0;

	edges.forEach((a) => {
		console.log('집합 : ', parent);
		const [x, y, cost] = a;
		if (!find(x, y)) {
			union(x, y);
			result += cost;
			console.log(`node ${x}, node ${y} 연결 => 비용 ${cost}`);
		} else {
			console.log(`node ${x}, node ${y} 사이클 발생`);
		}
	});

	return result;
}

console.log(kuruskal());