Advanced Algorithm - MST(Prim's Algorithm)(4)

1. 프림 알고리즘이란?

- 대표적인 최소신장 알고리즘 중 하나이다.(Kruskal's Algorithm & Prim's Algorithm)

 

a) 크루스칼 알고리즘과 프림 알고리즘의 비교

• 크루스칼 알고리즘은 전체 간선을 가중치 기준으로 오름차순 정렬하여, 낮은 가중치를 가진 간선이면서 동시에 사이클이 발생하지 않는 노드를 연결시켜 MST(최소신장트리)를 구하는 알고리즘이다. 
• 프림 알고리즘은 어떤 노드와 인접한 노드의 간선만을 대상으로 하여, 인접노드 중에서 간선의 가중치가 가장 작은 간선을 선택하여 해당 인접노드를 연결하는 방식으로 MST를 구한다.
• 두 알고리즘 모두 탐욕 알고리즘을 기반하고 있다.(당장을 위한 최소비용을 선택하여 결과적으로 최적의 솔루션을 찾음)

 

b) 프림 알고리즘의 로직

1. 임의의 노드를 선택하여 '연결된 노드 집합' 이라는 리스트에 삽입한다. 
   
   
2. 1단계에서 선택된 노드에 연결된 간선들을 '간선' 리스트에 삽입한다. 
   
   
3. '간선' 리스트에서 최소 가중치를 가지는 간선부터 추출한다. (간선이 추가될 때마다 가중치를 기준으로 내림차순 정렬)
   - '간선' 리스트에서 추출된 노드가 '연결된 노드 집합' 리스트에 이미 존재한다면 스킵한다.(사이클 방지)
   - 반대로, 존재하지 않는다면 해당 노드의 간선정보를 '최소신장트리'에 삽입한다. 
   
   
4. 선택된 간선은 '간선' 리스트에서 제거한다. 
   
   
5. '간선' 리스트에 더 이상 간선이 없을 때까지 3, 4번 과정을 반복수행한다. 
   
   

(아래 그림에서 파란색 요소들은 '연결된 노드 집합'에 삽입되었음을 의미한다.)

(아래 그림에서 빨간색 요소들은 '간선' 리스트에 삽입되었음을 의미한다.)

 

---

2. 코드구현 하기전에 꿀Tips!!!

- 이전까지 우선순위 큐를 만들 때, heapq 라이브러리를 사용하여 heappush()와 heappop() 함수를 이용하여 우선순위 큐에 데이터를 삽입 및 추출을 사용했다. 이 코드는 다음과 같다. (아래 사진참고)

- 위의 코드를 살펴보면, for 반복문을 이용하여 그래프(test_graph)에 들어있는 간선의 정보를 heappush() 함수를 이용하여 하나씩 삽입하는 것을 볼 수 있다. 하지만 이와는 다르게, 코드의 효율성을 높이기 위해, 데이터 삽입 작업을 한번에 할 수 있는 함수가 존재한다. 

 

a) heapify() 함수

- heapify() 함수는 heappush() 함수와 달리, 한방에 리스트를 heap 구조로 만드는 함수다. 코드는 다음과 같다.

# heapify() 함수 

import heapq

queue = []
test_graph = [[2,'A'],[7,'B'],[3,'C']] #정렬이 되지 않은 상태

heapq.heapify(test_graph)
    
for index in range(len(test_graph)):
    print(heapq.heappop(test_graph))

 

[결과]

 

 

b) Collections 라이브러리의 defaultdict() 함수

- defaultdict() 함수를 사용하면, 일반적인 딕셔너리의 형태인 {key : value}의 기본 값(value)를 설정 할 수 있다.

- 다시말해, 딕셔너리의 value를 어떤 자료구조를 기본값으로 할당할지 설정할 수 있다.  

- 즉, key나 value가 초기화 되지 않아도 defaultdict(자료구조)에 설정한 자료구조가 반환된다. 

- 다음의 예시를 참고하면서 이해해보자. 

 

- 위의 사진과 같이, 딕셔너리 자료구조를 초기화하지 않은 상태에서는  특정 key 또는 value를 호출하면 오류가 발생한다.

 

 

- 그러나 collections 라이브러리의 defaultdict() 함수를 사용하면, 잘못된 호출이 발생하더라도 defaultdict() 함수로 설정해놓은 자료구조를 반환한다. 위의 예제에 나온 dict 이외에도 다른 자료구조를 사용할 수 있다. 

 

예시 1) defaultdict() 함수를 list로 초기화 하면, 잘못된 호출이 발생하더라도 비어있는 리스트 자료구조가 반환된다. 

 

예시 2) defaultdict() 함수에는 데이터 타입도 명시될 수 있다.

int

 

float

 

set - 집합

 

* 참고로 파이썬의 collections.defaultdict() 와 typing.DefaultDict()는 동일한 라이브러리다.

 - typing.DefaultDict()를 살펴보면 collections.DefaultDict()의 alias라는 것을 확인할 수 있다.