[SW정글 23일차] 크루스칼 알고리즘 & 프림 알고리즘

그래프 기초를 공부하다 보면 크루스칼 알고리즘 & 프림 알고리즘이라는 생전 처음 본 알고리즘을 만나게 된다. 이들을 알기 위해서는 먼저 최소 신장 트리에 대해 알아야 한다.

최소 신장 트리란

신장 트리란, 연결 그래프의 부분 그래프로, 모든 정점과 간선의 부분 집합으로 구성되는 트리를 말한다. 포인트는! 그래프에 사이클이 형성되어서는 안된다.
이어서 최소 신장 트리란(Minimum cost Spanning Tree : MST), 트리를 구성하는 간선들의 가중치를 합한 것이 최소가 되는 신장 트리이다.

이 최소 신장 트리(MST)를 찾아내는 방법이 바로, 크루스칼 알고리즘, 프림 알고리즘이다.

알고 가면 좋은 기본적인 것은, n개의 정점을 가지는 그래프에서 최소 신장 트리를 구하려면 n-1개의 간선을 선택해야 한다.

크루스칼 알고리즘

1. 그래프의 모든 간선들을 오름 차순으로 정렬한다.
2. 가장 가중치가 작은 간선부터 하나씩 확인한다.
   2_1. 확인하는 현재 간선이 사이클을 발생시키는지 확인한다.
3. 사이클이 발생하지 않는다면 최소 신장 트리에 포함시키고, 사이클이 발생한다면, 다음 간선으로 넘어간다.
4. 2번부터의 과정을 반복한다.

구현

import sys
# 점 개수, 간선 개수
v, e = map(int, sys.stdin.readline().split()) 	

parent = [0] * (v+1)
for i in range(1, v+1):
	parent[i] = i

def find_parent(parent, x):
	if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]
 
def union_parent(parent, a, b):
	a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
    	parent[b] = a
    else:
    	parent[a] = b

edges = []
total_cost = 0

# 비용 기준으로 간선 정렬
for _ in range(e):
	a, b, cost = map(int, sys.stdin.readline().split())
    edges.append((c, a, b)) 
edges.sort()
for i in range(e):
    c, a, b = edges[i]
    if find_parent(parent, a) != find_parent(parent, b):
    	union_parent(parent, a, b)
        total_cost += c

print(total_cost)

프림 알고리즘

1. 그래프의 임의의 점을 택하여 빈 트리 T에 넣는다.
2. T에 있는 노드(점)와 T에 포함되지 않은 노드 사이의 간선 중 가중치가 최소인 간선을 택한다.
3. 찾은 간선이 연결하는 두 노드 중, T에 없던 노드를 T에 포함시킨다.
4. 모든 노드가 T에 포함될 때까지 2번부터의 과정을 반복한다.

구현

import sys, heapq, collections
sys.setrecursionlimit(10**6)

v, e = map(int, sys.stdin.readline().split()) 
graph = collections.defaultdict(list)   # 빈 그래프 생성
visited = [0] * (n+1)

for i in range(e):
	u, v, weight = map(int, sys.stdin.readline().split()) 
    graph[u].append([weight, u, v])
    graph[v].append([weight, v, u])

def prim(graph, start_node):
	visited[start_node] = 1
    candidate = graph[start_node] # 인접 간선 추출
    heapq.heapify(candidate) # 우선순위 큐 생성 : 가중치 적은 순
    mst = []
    total_weight = 0 # 전체 가중치
    
    while candidate:
    	weight, u, v = heapq.heappop(candidate)
        if visited[v] == 0:
        	visited[v] = 1
            mst.append((u, v))
            total_weight += weight
            
            for edge in graph[v]:
            	if visited[edge[2]] == 0:
                	heapq.heappush(candidate, edge)
                    
	return total_weight
    
print(prim(graph, 1))

---

오늘의 나는

그래프 알고리즘을 공부하고 문제를 풀다 보니 관련 알고리즘이 많이 나와서 팀원과 각자 알고리즘을 나눠서 공부하고 서로에게 설명해 준 것을 정리해보았다. 설명해 줘야 한다 생각하니 각 잡고 공부하게 되어 다시 한번 효율적인 공부법이라 느껴졌다.

내일은 하고 싶은 것을 다하면서 성장할 수 없고, 포기하는 만큼 얻게 된다는 것을 잊지 말고, stay calm!

참고. 프림 알고리즘