[APS] 15. Prim 알고리즘 파이썬(Python)으로 구현하기

• 신장트리

  : n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

• MST (Minimum Spanning Tree)

  : 신장트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

1. Prim 알고리즘

2. Kruskal 알고리즘

3. Dijkstra 알고리즘

---

첫 번째로 Prim 알고리즘에 대해서 알아보려고 한다.

1. Prim 알고리즘의 기본 원리

---

• 하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 MST를 만들어 나간다.
  1. 임의 정점을 하나 선택해서 시작한다.
  2. 선택한 정점과 인접한 정점들 중 최소 비용의 간선이 존재하는 간선을 선택한다.
  3. 모든 정점이 선택 될 때까지 1~2를 반복한다.

• 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지한다.
  1. 트리 정점들(tree vertices) : MST를 만들기 위해 선택된 정점들
  2. 비트리 정점들(nontree vertices) : 선택되지 않은 정점들

2. 실습

---

출처 : Hee’s development Blog

3. 코드로 구현해보기

---

1. 먼저 간선과 가중치가 주어진다고 할 때, 이것을 인접행렬에 저장하는 방법을 알아야 한다.
   • 예로 들자면, 노드 번호는 0부터 V까지, V+1 개가 존재하고, 간선은 E개 존재한다고 한다.
   • E줄만큼 n1, n2, w (각각 시작노드, 끝 노드, 가중치) 가 주어진다고 한다.

6 11 # V, E
0 1 32 # 아래로 E 줄만큼 n1, n2, w 가 주어진다고 할 때
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51

adjM = [[0]*(V+1) for _ in range(V+1)]
for _ in range(E):
	n1, n2, w = map(int, input().split())
	adjM[n1][n2] = w
	adjM[n2][n1] = w # 무방향 이므로 양쪽 다 저장해야 한다.

# output
# [[0, 32, 31, 0, 0, 60, 51], [32, 0, 21, 0, 0, 0, 0], [31, 21, 0, 0, 46, 0, 25], [0, 0, 0, 0, 34, 18, 0], [0, 0, 46, 34, 0, 40, 51], [60, 0, 0, 18, 40, 0, 0], [51, 0, 25, 0, 51, 0, 0]]

2. 다음으로는 Prim 함수를 정의해보자

def Prim(r,V) : # r은 시작점, V는 노드번호 끝이다. (문제 상황에 따라 맞게 변형하기)
	MST = [0] * (V+1) # MST 에 포함되었는지 여부를 확인하기 위한 check 배열
	key = [10000] * (V+1) # 가중치를 최대값으로 초기화. 문제에 따라 적당히 큰 값으로 설정한다.
	# key[v] => v가 MST에 속한 점과 연결될 때의 최소 가중치
	key[r] = 0 # 시작점의 key값

	for i in range(V):
		# MST에 포함되지 않은 점 중에서 key가 최소인 것을 찾아 떠난다.
		# MST[i] == 0 => MST에 포함되지 않은 점을 의미한다.
		u = 0
		minV = 10000
		
		# 다음으로 이동할 노드 구하기 (u)값 구하기
		# u로 가는 간선의 값이 제일 작을 때, u를 선택한다.
		for j in range(V+1):
			if MST[j] == 0 and key[j] < minV:
				u = j
				minV = key[j]
		MST[u] = 1 
		
		# key 값 갱신하기 (현재 있는 값과 이동할 수 있는 값 중에 선택)
		for v in range(V+1):
			if MST[v] == 0 and adj[u][v] > 0:
				key[v] = min(key[v], adjM[u][v])

	return sum(key)

Uploaded by N2T