[Algorithm/Python] MST(최소 신장 트리) 알고리즘 + 크루스칼(Kruskal), 프림(Prim) 알고리즘 정리

신장 트리(Spanning Tree)란?

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미

 

1. 모든 정점을 포함해야 한다.

2. 연결 그래프이자 부분 그래프여야 한다.

3. 사이클이 존재하지 않아야 한다.

 

최소 비용 신장 트리(Minimum Cost Spanning Tree)란?

그래프에서 모든 노드를 연결할 때 간선의 가중치 합이 최소가 되는 경우의 신장 트리

 

최소 비용 신장 트리에는 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 존재한다.

 

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

그리디 알고리즘을 통해 최소 신장 트리를 구하는 알고리즘이다.

• 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
• 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
  • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
  • 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
• 모든 간선에 대하여 하나씩 확인하며 두번째 과정을 반복한다.

크루스칼 알고리즘의 핵심 원리는 가장 거리가 짧은 간선부터 차례대로 집합에 추가하면 된다.(사이클 발생 여부 확인)

 

크루스칼 알고리즘을 구현하기 위한 과정에는 Union-Find 알고리즘 또한 이용되니 알아두자.

[Algorithm/Python] Disjoint Set(서로소 집합)이란? Union-Find 알고리즘 정리

# 특정 원소가 속한 집합을 찾기(Find)
def find_parent(parent, x):
	# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기(Union)
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
        
# 노드의 개수와 간선(union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블 상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 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_parent(parent, a) != find_parent(parent, b):
		union_parent(parent, a, b)
		result += cost
        
print(result)

 

프림 알고리즘 (Prim Algorithm)

 

프림은 간선이 중심이었던 크루스칼과 다르게 정점을 중심으로 최소 신장 트리를 만들어나간다.

1. 임의의 시작점 선택
2. 선택한 정점과 인접하는 정점들 중에서 최소 비용의 간선을 가지는 정점을 선택
3. 모든 정점이 선택될 때까지 반복

우선순위 큐를 이용한 최소 힙을 통해 구현한다. 다익스트라와 비슷!

 

import heapq
 
v, e = map(int,input().split())
visited = [0] * (v+1)
graph = [[] for _ in range(v+1)]
 
for i in range(e):
    u, v, weight = map(int,input().split())
    graph[u].append([weight, u, v])
    graph[v].append([weight, v, u])
 
 
def prim(start):
    visited[start] = 1
    candidate = graph[start]
    heapq.heapify(candidate)
    mst = []
 
    while candidate:
        weight, u, v = heapq.heappop(candidate)
        if visited[v] == 0: 
            visited[v] = 1
            mst.append((u,v,weight))
 
            for edge in graph[v]: 
                if visited[edge[2]] == 0: 
                    heapq.heappush(candidate, edge)
 
    return mst
 
start_node = int(input())
print(prim(start))

 

Kruskal => 간선을 중심으로 간선 정렬하면서 최소 비용의 간선을 가진 정점을 고르며 시작

Prim => 정점을 중심으로 시작 정점을 정하여 최소 비용을 가진 간선의 정점을 고르며 시작