[Algorithm] 크루스칼 알고리즘(Kruskal Algorithm)이란?

 

 

 

 

현실은 복잡하다. 수많은 싸이클이 존재하고 비효율이고 무질서하다.  그러므로 우리는 싸이클을 제거하고 효율높은 질서를 찾아야 한다.

 

그래프는 여러 개의 신장트리(Spanning Tree)를 갖는다.

 

신장트리(Spanning Tree)란?

모든 노드가 연결되면서 사이클이 존재하지 않는 그래프를 의미한다. 여러 신장 트리 중 가장 비용이 적은 신장트리를 최소신장트리라고 부르는데, 최소신장트리를 구하는 대표적인 알고리즘이 크루스칼 알고리즘(Kruskal Algorithm)이다.

 

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

 

크루스칼 알고리즘은 두 가지 조건이 충족되어야 한다.

 

1) 최소비용이어야 한다. ( 정렬을 활용한 그리디 알고리즘 )

2) 싸이클이 존재하면 안 된다.  ( Union-Find 알고리즘으로 싸이클 판별 )

[Algorithm] 무방향그래프에서 싸이클 찾기

 

 

 

 

위 그래프에서 최소신장트리를 찾을거다. 원리는 간단하다. 간선을 정렬하여 최소비용인 간선부터 하나씩 추가한다. 단, 싸이클을 형성하는 간선은 제외한다. 자료구조부터 하나씩 살펴보자.

 

 

◎ 자료구조 

 

- 간선 테이블

1-2	1-4	2-4	2-5	4-5	4-3	5-3
13	7	23	30	45	19	57

 

- 서로소-집합 테이블 ( UNION-FIND 알고리즘 )

노드	1	2	3	4	5
부모	1	2	3	4	5

 

처음에는 정렬되지 않은 간선테이블과 자기자신을 부모로 갖는 서로소-집합테이블이 있다.

 

 

◎ 알고리즘

 

1) 정렬하기 ( 오름차순 )

 

- 정렬된 간선 테이블

1-4	1-2	4-3	2-4	2-5	4-5	5-3
7	13	19	23	30	45	57

 

2) 간선 추가

 

- [ 1-4 ] 간선 추가

 

노드 1의 부모는 1이다.

노드 4의 부모는 4이다.

 

부모가 서로 다르므로 간선이 추가되어도 싸이클을 형성하지 않는다.

그러므로 간선을 추가한다. 

 

 

 

 

❖ 총 비용 : 7

 

- 서로소-집합 테이블 ( UNION-FIND 알고리즘 )

노드	1	2	3	4	5
부모	1	2	3	1	5

 

일반적으로 값이 작은 노드를 부모로 따른다. 자세한 원리는 아래 링크에 나와 있으니 참고바란다.

[Algorithm] Union-Find 알고리즘이란? ( with 서로소 집합 자료구조 )

 

 

- [ 1-2 ] 간선 추가

 

노드 1의 부모는 1이다.

노드 2의 부모는 2이다.

 

부모가 서로 다르므로 간선이 추가되어도 싸이클이 형성되지 않는다.

그러므로 간선을 추가한다. 

 

 

 

❖ 총 비용 : 20 ( 7 + 13 )

 

- 서로소-집합 테이블 ( UNION-FIND 알고리즘 )

노드	1	2	3	4	5
부모	1	1	3	1	5

 

 

- [ 4-3 ] 간선 추가 

 

노드 4의 부모는 1이다.

노드 3의 부모는 3이다.

 

부모가 서로 다르므로 간선이 추가되어도 싸이클이 형성되지 않는다.

그러므로 간선을 추가한다. 

 

 

❖ 총 비용 : 39 ( 7 + 13 + 19 )

 

- 서로소-집합 테이블 ( UNION-FIND 알고리즘 )

노드	1	2	3	4	5
부모	1	1	1	1	5

 

- [ 2-4 ] 간선 추가

 

노드 2의 부모는 1이다.

노드 4의 부모는 1이다.

 

부모가 서로 같은므로 간선이 추가되면 싸이클이 형성된다.

그러므로 간선을 추가하지 않는다.

 

- [ 2- 5 ] 간선 추가

 

노드 2의 부모는 1이다.

노드 5의 부모는 5이다.

 

부모가 서로 다르므로 간선이 추가되어도 싸이클이 형성되지 않는다.

그러므로 간선을 추가한다.

 

 

 

 

❖ 총 비용 : 69 ( 7 + 13 + 19 + 30 )

 

- 서로소-집합 테이블 ( UNION-FIND 알고리즘 )

노드	1	2	3	4	5
부모	1	1	1	1	1

 

- [ 4-5 ] 간선 추가

 

노드 4의 부모는 1이다.

노드 5의 부모는 1이다.

 

부모가 서로 같은므로 간선이 추가되면 싸이클이 형성된다.

그러므로 간선을 추가하지 않는다.

 

- [ 5-3 ] 간선 추가

 

노드 5의 부모는 1이다.

노드 3의 부모는 1이다.

 

부모가 서로 같은므로 간선이 추가되면 싸이클이 형성된다.

그러므로 간선을 추가하지 않는다.

 

3) 결과 

 

 

❖ 총 비용 : 69 ( 7 + 13 + 19 + 30 )

 

이로써, 크루스칼 알고리즘( Kruskal Algorithm)으로 복잡했던 그래프에서 최소신장트리를 추출했다. 시간복잡도는 정렬 알고리즘 + Union-Find 알고리즘 인데, 정렬의 시간복잡도가 훨씬 크므로, O(ElogE)이다. (E : 간선의 개수)

 

 

◎ 코드 (Python)

#FIND
def find_root(parent,x) :
  if parent[x] != x : parent[x] = find_root(parent,parent[x]) 
  return parent[x]
#UNION
def union_parent(parent,a,b) :
  a_root = find_root(parent,a)
  b_root = find_root(parent,b)

  if a_root > b_root : parent[a_root] = b_root
  else : parent[b_root] = a_root


n,e = map(int,input().split()) #n:노드의 개수, e:간선의 개수
parent = [0] * (n+1) #서로소-집합테이블 생성

edges = [] #간선테이블 생성
result = 0 #총비용

#서로소-집합 테이블 초기화
for i in range(1,n+1) :
  parent[i] = i 

#간선테이블 초기화
for _ in range(e) :
  a,b,cost = map(int,input().split())
  edges.append((cost,a,b))

#간선테이블 정렬
edges.sort()

#크루스칼 알고리즘 
for edge in edges :
  cost,a,b = edge # 간선 정보
  if find_root(parent,a) != find_root(parent,b) : #간선 추가시, 싸이클을 형성하지 않는경우
    union_parent(parent,a,b) # 합치기
    result += cost # 비용계산

print(result)

 

- 입력

7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25

 

-출력

159

 

 

---

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서