Kruskal

1. 정의 및 구현 방법��2. Situation��3. Steps��4. Result�

Index

- 탐욕적인(greedy) 방법을 이용��- 지금 이 순간에 최적인 답을 선택하여 결과를 도출하자��- 순환이 안 생기도록 주의��- 연결된 정점이 속한 그룹 단위로 관리. 그룹과 그룹이 연결되면 하나의 그룹으로, 그룹 내에서 같은 요소 연결 불가능 => Disjoint set으로 구현 가능

정의 및 구현 방법

Situation

0

1

2

3

4

5

5

10

5

5

25

10

0

1

2

3

4

5

5

10

5

5

25

10

제시된 그래프

얻고자 하는 MST

How to get?

13

13

Step1

0

1

2

3

4

5

5

10

5

5

25

10

최단 코스트 경로를 임의로 선택합니다.

Total Cost = 5 + = 5

13

Step2

0

1

2

3

4

5

5

10

5

5

25

10

최단 코스트 경로를 임의로 선택합니다.

Total Cost = 5 + 5 = 10

13

Step3

0

1

2

3

4

5

5

10

5

5

25

10

최단 코스트 경로를 임의로 선택합니다.

Total Cost = 5 + 5 + 5 = 15

13

Step4

0

1

2

3

4

5

5

10

5

5

25

10

그다음 최단 코스트 경로 10 중 하나를 선택

Total Cost = 5 + 5 + 5 = 15

사이클 발생! => MST 조건에 부합하지 않음

13

Step5

0

1

2

3

4

5

5

10

5

5

25

10

사이클이 발생하지 않기 위해서 예외 처리 필요

이를 DisjointSet을 이용해서 해결 가능하다

• 정점을 하나의 그룹으로 생각하기

​

• 정점과 정접을 잇는 것은 소속 그룹의 DisjointsSet Merge를 의미함

​

• 경로를 선정할 때 정점a와 정점b가 다른 그룹일 때만 선택 가능

13

Step6

0

1

2

3

4

5

13

5

10

5

5

25

10

사이클이 발생하지 않기 위해서 예외 처리 필요

이를 DisjointSet을 이용해서 해결 가능하다

• 정점2와 정점5은 같은 그룹내 연결 이므로 연결 불가능

​

• 정점 1과 정점2는 다른 그룹간의 연결 이므로 연결 가능

그룹 c

그룹 a

Step7

0

1

2

3

4

5

13

5

10

5

5

25

10

세번째 최단 거리 13이면서 그룹외부 결합인 정점0, 정점1 연결

그룹 c

Total Cost = 5 + 5 + 5 + 10 + 13 = 38

Step8

0

1

2

3

4

5

13

5

10

5

5

25

10

네번째 최단 거리 25인 정점0,정점2는 그룹 내부 연결 이므로 무시

그룹 c

Total Cost = 5 + 5 + 5 + 10 + 13 = 38

Result

0

1

2

3

4

5

13

5

10

5

5

최소 스패닝 트리

Total Cost = 5 + 5 + 5 + 10 + 13 = 38