[그래프] 크루스칼-최소신장트리 MST(Minimum Spanning Tree)

최소신장트리(MST)

그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로 하는 트리

 

알고리즘 종류

• 크루스칼
• 프림

주요 특징

• 사이클이 포함되면 가주치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 엣지의 갯수는 항상 N-1개 이다.

[그래프]

８　　５ ① ─ ② ─ ⑤ │3    │ 4／2 ③ ─ ④ 　13

 

[엣지리스트]

엣지	①	②	③	④	⑤	⑥
노드1	null	null	null	null	null	null
노드2	null	null	null	null	null	null
가중치	null	null	null	null	null	null

 

[유니온파인드리스트]

①	②	③	④	⑤	⑥
null	null	null	null	null	null

 

---

<핵심이론>

 

Step 01) 엣지 리스트로 그래프를 구현 및 유니온파인드 리스트 초기화

최소신장 트리는 데이터를 노드가 아닌 `엣지 중심` 으로 저장하므로 인접리스트가 아닌 `엣지리스트`의 형태로 저장한다.

이 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다.

사이클 처리를 위한 유니온 파인드 리스트도 함께 초기화 한다.

(→ 리스트 인덱스를 해당 자리 값으로 초기화 한다.)

 

[엣지리스트]

엣지	①	②	③	④	⑤	⑥
노드1	1	2	1	3	2	4
노드2	2	5	3	4	4	5
가중치	8	5	3	13	4	2

 

[유니온파인드리스트]

①	②	③	④	⑤
1	2	3	4	5

 

 

Step 02)그래프 데이터를 가중치 기준으로 정렬

엣지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬 한다.

:) 오름차순 정렬은 input 데이터의 순서 조정을 통해 높은 자유도로 정렬 가능 (실전문제에서)

 

[가중치 기준 엣지 리스트 오름차순 정렬]

엣지	①	②	③	④	⑤	⑥
노드1	4	1	2	2	1	3
노드2	5	3	4	5	2	4
가중치	2	3	4	5	8	13

 

 

Step 03) 가중치가 낮은 엣지부터 연결 시도 (연결 성공시 Count 1증가)

이때 바로 연결하지 않고 해당 엣지를 연결했을 때 그래프에 사이클 생성 유무를 find연산을 이용해 확인 후 사이클이 형성되지 않을 때만 UNION 연산을 이용해 두 노드를 연결한다.

(사이클이 생긴다는 것은 이미 현재 엣지보다 가중치가 낮은 엣지들로 연결되어있음을 의미한다.)

1. 가중치가 낮은 엣지부터 차례대로 연결을 시도한다.
   - 엣지 ①
2. find(4), find(5) 연산을 수행해 선택된 두 노드의 대표노드가 서로 다를 경우만 연결
   (대표노드가 같다면 두 노드를 연결했을 대 사이클이 만들어 진다.)
   - 처음에는 연결이 되지 않았으므로 4, 5
   즉, 대표노드가 서로 다르므로 UNION연산 수행
3. UNION(4, 5) 연산을 수행해 선택된 두 노드를 연결한다.
   - 유니온파인드리스트의 ⑤의 5를 4로 Update
   - 성공 count 1증가
   

   ①	②	③	④	⑤
   1	2	3	4	5 4

   두 노드 연결

   ⑤ 　 ／2    ④

Step 04) 과정 3 반복

①	②	③	④	⑤
1	2	3	4	4

 

엣지②

노드 ①,  ③ find연산 수행

find(1) = 1 / find(3) = 3

1 ≠ 3 서로다름 =≫ UNION(1, 3)

성공 count 1증가

두 노드 연결

① 　  　⑤ │3      ／2 ③ 　④

 

유니온파인드리스트의 ③의 3을 1로 Update

①	②	③	④	⑤
1	2	3 1	4	4

 

엣지③ 

노드 ②, ④ find연산 수행

find(2) = 2 / find(4) = 4

2 ≠ 4 서로다름 =≫ UNION(2, 4)

성공 count 1증가

두 노드 연결

① 　 ② 　 ⑤ │3    │4 ／2 ③ 　 ④

 

유니온파인드리스트의 ④의 4를 2로 Update

①	②	③	④	⑤
1	2	1	4 2	4

 

엣지④  

노드 ②, ⑤ find연산 수행

find(2) = 2 / find(5) = 4 → 2

(find연산시 리스트의 값에 해당하는 위치를 찾아감)

2 == 2 서로같음 =≫ UNION연산 수행하지 않음

성공 count 증가하지 않음

두 노드 연결X

① 　 ② ─ ⑤ │3    │4 ／2 ③ 　 ④

 

엣지⑤   

노드 ①, ② find연산 수행

find(1) = 1 / find(2) = 2

1 ≠ 2 서로다름 =≫ UNION(2, 4)

두 노드 연결

8 ① ─ ② 　 ⑤ │3    │4 ／2 ③ 　 ④

유니온파인드리스트의 ⑤의 4를 2로 Update

①	②	③	④	⑤
1	2 1	1	2	4

 

Step 05) 총 엣지 비용 출력

엣지의 갯수가 N-1이 되면 알고리즘을 종료하고 완성된 최소 신장 트리의 총 엣지 비용을 출력한다.

2 + 3 + 4 + 8 = 17 출력

Step 01) ~ Step 05) 과정은 MST의 크루스칼 알고리즘 원리이다.

단점
① 엣지리스트 이용으로 구현이 까다로울 수 있음 (생소함)
② 유니온 파인드 알고리즘을 내부에 구현해야 함

∴ 최소 신장 트리는 다른 그래프 알고리즘과는 달리 엣지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있다.
그 이유는 엣지를 기준으로 하는 알고리즘이기 때문이다.
또한 사이클이 존재하면 안되는 특징을 지니고 있기 때문에 사이클 판별 알고리즘인 유니온 파인드 알고리즘을 내부에 구현해야 한다.