[이론] 크루스칼 알고리즘

0. 학습 목적

1. 크루스칼 알고리즘의 목적과 작동원리를 이해한다.
2. 최소 스패닝 트리가 무엇인지 이해한다.
3. 트리와 그래프의 차이점을 이해한다.

1. 크루스칼 (Kruskal) 알고리즘이란?

주어진 그래프 내에서 최소 스패닝 트리를 찾는 알고리즘이다.
그리디한 방식을 진행되며, 내부에서 트리 구성원 여부를 가리기 위해 유니온 파인드를 활용한다.

(1) 그래프와 트리의 차이

둘 다 간선과 정점으로 이루어져 있지만, 다음 항목에서 차이를 보인다.

구분	그래프	트리
사이클의 여부	사이클이 존재할 수 있다.	사이클이 없다.
간선의 개수	간선의 개수를 특정할 수 없다.	정점이 N개라면 간선의 개수는 N-1개이다.

(2) 최소 스패닝 트리란?

그래프 내에 트리의 조건을 만족하면서도 가중치 비용이 최소 비용인 부분집합을 의미한다.
여기서 트리의 조건은 무사이클, 간선의 개수가 N-1 개를 들 수 있다.

왼쪽이 주어진 그래프, 오른쪽이 해당 그래프에서 나온 최소 스패닝 트리이다.

2. 크루스칼 동작 과정

(0) 준비물

1. 간선 리스트
   : (정점1, 정점2, 가중치) 형식으로 이루어진 간선 리스트를 만든다.
   모든 간선을 저장한 후에 가중치가 작은 순으로 정렬한다.

2. 유니온파인드 용 배열
   : 간선 리스트를 순회하며 (A,B,가중치) 형태의 객체를 마주할 때, 정점 A와 정점 B가 이미 같은 트리의 구성원인지 확인하는 용도이다.

(1) 동작

1. 간선리스트에 (정점A, 정점B, 가중치) 형태로 데이터를 저장한다.

2. 간선리스트를 가중치가 작은 순으로 정렬한다.

3. 간선리스트를 순회하며 다음을 반복한다.

   • 간선 객체의 정점 A와 정점 B가 유니온 파인드 상 같은 집합에 속하는지 확인한다.

   • 만약 같은 집합에 속하면 이미 최소 스패닝 트리의 일원이므로 현 간선을 이으면 안된다. 따라서 넘어간다. ( 현재 간선을 이으면 순환이 생기므로 트리의 정의에서 벗어남)

   • 만약 같은 집합에 속하지 않으면 둘을 잇는다. (Union(A,B) 실행 및 가중치 더하기)

(2) 예시

기본 형태는 위와 같을 것이다.

첫번째 간선에 대한 작업 수행

두 번째 간선에 대한 작업 수행

세 번째 간선에 대한 작업 수행
(1,4,3)을 이으면, 순회가 생겨서 더 이상 트리가 아니게 되므로 해당 간선은 넘어간다.

네번째 작업을 수행

5번째 작업 수행

6번째 작업 수행.
(2,5,5) 또한 연결하면 순환이 생기므로, 넘어간다.
순환은 아직 두 정점을 UNION으로 연결하지도 않았는데, 둘의 조상이 겹치는 경우에 존재하는 것으로 간주 가능하다.

7번째 작업 수행
이번 작업을 끝으로 트리의 간선 N-1 개를 모두 찾았음으로 더 이상 그 뒤의 계산을 진행할 필요가 없다.

3. 핵심 요약

1. 크루스칼 알고리즘 이란 그래프에서 최소 스패닝 트리를 찾는 알고리즘이다.
2. 최소 스패닝 트리란 트리의 규칙 (무 사이클, N-1개의 간선)을 지키면서도 그래프 내의 최소 가중치로 만들어진 트리를 의미한다.
3. 크르수칼 알고리즘의 동작 원리는 선택한 정점 확인을 위한 유니온 파인드*와 가중치가 작은 간선부터 하나씩 확인하여, 순환이 아니면 뽑아 쓰는 *그리디 알고리즘 방식으로 이루어져 있다.

---

부록

A. 모르는 것 정리

B. 참고 문서

• 최소 스패닝 트리 (MST): 크루스칼 알고리즘

C. 관련 글

TABLE without id file.inlinks AS "BackLink"
WHERE file.path = this.file.path