[알고리즘] 최소 신장 트리(MST)

권나연·2025년 1월 27일
알고리즘

알고리즘_개념

목록 보기
7/9
post-thumbnail

신장 트리란?

모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프

  • 아래 그래프 3개가 신장 트리이다.

최소 신장 트리란?

신장 트리 중 간선의 가중치 합이 최소면 최소신장트리(MST)라 한다.

  • 경우에 따라 MST는 하나가 아닐 수도 있다.
  • 최소 신장 트리를 구하는 대표적인 그리디 알고리즘은 프림 알고리즘과 크루스칼 알고리즘이다.

프림 알고리즘

프림 알고리즘의 과정

  1. 임의의 정점을 하나 선택해서 MST에 추가한다.
  2. ST와 연결되어 있는 정점 중 가장 가중치가 적은 정점을 MST에 추가한다. (이 부분이 그리디적!) 단, 순환을 형성하지 않는 정점을 추가해야 한다.
  3. 과정 2를 신장 트리 조건에 만족할 때까지 반복.

프림 알고리즘의 예시

  • 초기 상태로 정점(=노드)는 서로 연결되어 있지 않다.

  • 정점과 연결된 간선을 하나씩 추가하면서 MST를 만든다.

  • 프림 알고리즘은 시작 정점을 정해 우선 순위 큐에 넣는다.

  • 우선 순위 큐에는 (정점, 가중치) 형식으로 저장되며, 첫 시작은 (시작 정점, 0)으로 넣는다.

그리고 우선순위 큐가 빌 떄까지 아래를 반복한다.

  1. 우선 순위 큐에서 하나를 꺼낸다. 꺼낸 정점을 v라고 하겠다.
  2. v가 이미 MST에 포함됐다면 과정 1로 돌아간다. 그렇지 않다면 아래를 진행한다.
  3. v와 연결된 간선을 모두 살핀다. 간선 (w, cost)는 v와 정점 w 사이 연결된 간선이며 cost 가중치를 가진다. 만약 w를 방문하지 않았다면 우선순위 큐에 추가한다.

  • 왼쪽 표 : 각 정점에 이어진 간선을 저장한 표이다.
  • visit : boolean 배열로 각 정점을 방문했는지 체크한다.
    - 정점을 방문 했다면 이미 MST에 포함된 정점이다.
  • 우선 순위 큐 : (정점, 가중치) 형태로 저장된다.

시작 정점은 1로 정했으므로 우선순위 큐에 (1, 0)을 저장한다.

과정 1

우선순위 큐에서 하나를 꺼낸다. (1, 0)

정점 1은 아직 방문하지 않았으므로 방문 체크를 한다. 이제 정점 1은 MST에 속해있다. 이후 정점 1과 연결된 간선을 모두 살핀다.

  • (3, 3) 우선 순위 큐에 추가
    - 정점 3은 아직 방문하지 않았다. 따라서 우선 순위 큐에 추가한다.
  • (4, 8) 우선 순위 큐에 추가
  • (2, 10) 우선 순위 큐에 추가

과정 2

우선순위 큐에서 하나를 꺼낸다. (3, 3)

정점 3은 아직 방문하지 않았으므로 방문 체크를 한다. MST에 정점 3과 가중치 3이 추가된다. 이후 정점 3과 연결된 간선을 모두 살핀다.

  • (1, 3) 우선 순위 큐에 추가 X
    - 정점 1은 이미 방문했다. 즉, 이미 MST에 포함된 정점이므로 우선 순위 큐에 추가하지 않는다.
  • (2, 13) 우선 순위 큐에 추가
    - 정점 2은 아직 방문하지 않았다. 따라서 우선 순위 큐에 추가한다.

과정 3

우선순위 큐에서 하나를 꺼낸다. (4, 8)

정점 4은 아직 방문하지 않았으므로 방문 체크를 한다. MST에 점정 4와 가중치 8이 추가된다.

  • (1, 8) : 우선순위 큐 추가 (x)
  • (5, 9) : 우선순위 추가.

과정 4

우선순위 큐에서 하나를 꺼낸다. (5, 9)

정점 5는 아직 방문하지 않았으므로 방문 체크를 한다. MST에 정점 5와 가중치 9가 추가된다. 이후 정점 5와 연결된 간선을 모두 살핀다.

  • (2, 14) : 우선 순위 큐에 추가
  • (4, 9) : 우선 순위 큐에 추가 X

과정 5

우선순위 큐에서 하나 꺼낸다 (2, 10)

정점 2는 아직 방문하지 않았으므로 방문 체크. MST에 정점 2와 가중치 10이 추가 됨.

현재 정점 2와 연결된 노드들은 모두 visit했으므로 우선순위 큐에 포함하지 않는다.

신장 트리 조건에 만족했으므로 우선순위 큐가 빌때까지 모든 과정을 건너 뛴다.

최종

우선순위 큐가 비었으므로 MST 완성. 총 가중치는 30이다.

프림 알고리즘 구현 - 파이썬

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 PrimMST(start):
    visited[start] = 1 # 방문 갱신
    candidate = graph[start] # 인접 간선 추출
    heapq.heapify(candidate) # 우선순위 큐 생성
    mst = [] # mst
 
    while candidate:
        weight, u, v = heapq.heappop(candidate) # 가중치가 가장 적은 간선 추출
        if visited[v] == 0: # 방문하지 않았다면
            visited[v] = 1 # 방문 갱신
            mst.append((u,v,weight)) # mst 삽입
 
            for edge in graph[v]: # 다음 인접 간선 탐색
                if visited[edge[2]] == 0: # 방문한 노드가 아니라면, (순환 방지)
                    heapq.heappush(candidate, edge) # 우선순위 큐에 edge 삽입
 
    return mst
 
start_node = int(input())
print(PrimMST(start_node))

  • graph 변수에 무방향 그래프를 인접 리스트 형태로 저장한다.

  • 간선은 [가중치, 시작 노드, 끝 노드] 형태로 저장된다.

  • 임의의 시작 노드에서 출발하여 MST를 확장.
    - candidate : 현재 확장 가능한 간선들은 담는 우선순위 큐

    • mst : 최소 신장 트리를 저장할 리스트

  • heapq가 비지 않을 때까지, 가장 가중치가 적은 간선을 선택하면서 방문하지 않은 노드로 확장.
    - 가장 가중치가 작은 간선을 선택

    • 선택된 간선의 끝 노드가 방문되지 않았다면 MST에 추가
    • 끝 노드에서 확장 가능한 간선을 다시 우선순위 큐에 추가.

크루스칼 알고리즘

크루스칼 알고리즘의 과정

  1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.
  2. 가중치가 낮은 간선부터 MST에 하나씩 추가한다. (이 부분이 그리디적!) 단, 순환은 형성하지 않아야 함
  3. 과정 2를 신장 트리 조건에 만족할 때까지 반복.

크루스칼 알고리즘의 예시

  • 초기 상태로 정점(=노드)는 서로 연결되어 있지 않다.

  • 간선을 하나씩 추가하면서 MST를 만든다.

  • 크루스칼 알고리즘을 수행하고 완성된 그래프는 최소 신장 트리이다. - 간선을 추가하는 방식은 다음과 같다.

  1. 크기가 가장 작은 간선부터 모든 간선을 살핀다. 이때 간선은 가중치에 대해 오름차순으로 정렬되어 있다.

  2. 간선을 그래프에 포함 했을 때, MST에 사이클이 생기지 않으면 추가한다. 이 과정은 유니온 파인드 알고리즘을 이용한다.
    정점 v와 정점 w를 잇는 간선 e가 있을 때, 정점 v와 정점 w가 같은 부모 노드를 가진다면 간선 e는 MST에 추가하지 않는다.

초기 상태는 위와 같은 무방향 그래프가 있다고 가정하자.

과정 1

(v, w, cost) = (1, 3, 3)

find(1) = 1, find(3) = 3

  • 사이클 유무 체크 : 부모 노드가 다르므로 이 간선을 MST에 추가했을 때 사이클이 생기지 않는다. 따라서 이 간선을 MST에 추가한다.
  • 정점 1과 정점 3을 union(1, 3)을 수행하여 같은 MST에 속해있도록 한다.

과정 2

(1, 4, 8)

find(1) = 1, find(4) = 4

  • 위와 동일한 이유로 간선을 추가한다.

과정 3

(4, 5, 9)

find(4) = 1, find(5) = 5

과정 4

(1, 2, 10)

find(1) = 1, find(2) = 2

과정 5 & 6

  • 아래 두개 가중치들은 parent가 동일하므로 추가하지 않는다.

최종 모습

크루스칼 알고리즘 파이썬 구현

G = { 
    'vertices' : [],
    'edges': []
}
 
parent = dict() 
rank = dict() 
 
def initial(node):
  parent[node] = node 
  rank[node] = 0 
 
def find(node):
  if parent[node] != node: 
    parent[node] = find(parent[node]) 
  return parent[node]
 
def union(node_a, node_b):
  root_a = find(node_a)
  root_b = find(node_b)
  if rank[root_a]>rank[root_b]:
    parent[root_b] = root_a
  else:
    parent[root_a] = root_b
    if rank[root_a] == rank[root_b]:
      rank[root_b]+=1
 
 
def KruskalMST(G):
  mst = []
  for node in G['vertices']:
    initial(node)
  e = G['edges']
  e.sort(key=lambda x : x[2])
 
  for edge in e:
    node_a, node_b, weight = edge
    if find(node_a) != find(node_b):
      union(node_a,node_b)
      mst.append(edge)
 
  return mst
 
v, e = map(int,input().split()) 
for i in range(v):
  G['vertices'].append(i)
 
for i in range(e):
  u, v, weight = map(int, input().split())
  G['edges'].append((u,v,weight))
 
KruskalMST(G)

  • initial(node):
    각 정점을 독립 집합으로 초기화하고, 자신을 부모로 가지며, 랭크는 0으로 초기화한다.

  • find(node) :
    재귀적으로 부모를 찾아 최상위 노드를 반환한다.

  • union(node_a, node_b) :
    - 두 정점의 루트를 비교해 랭크가 낮은 트리를 높은 트리에 붗인다.
    - 랭크가 같으면 임의의 하나를 부모로 설정하고 랭크를 증가한다.

프림 알고리즘 vs 크루스칼 알고리즘

profile
권나연
백엔드 개발자 지망생 🍎
이전 포스트

[알고리즘] 플로이드-워셜 알고리즘

다음 포스트

[알고리즘] 유니온 파인드

0개의 댓글