youl

youl

푸하하-자아자 ˘◡˘

[Data Structure] 최소 신장 트리 알고리즘(MST / Minimum Spanning Tree)

2 분 소요

🙋‍♀️MST(Minimum Spanning Tree)

신장 트리: 사이클이 형성되지 않는 그래프

최소 신장 트리: 신장 트리의 모든 간선의 가중치 합이 최소인 그래프

🙂 지금부터 대표적인 최소 신장 트리 구현 알고리즘인 크루스칼과 프림 알고리즘을 빠르게 살펴보고자 한다!


🙋‍♀️ 크루스칼 알고리즘

가중치를 기준으로 간선을 정렬한 후 MST가 될 때까지 간선을 하나씩 선택하는 방식

  • 그리디 알고리즘의 일종이다.
    • 순간마다 가중치 합이 최소인 것을 탐색하기 때문이다.
  • 순서
    • 가중치를 기준으로 간선들을 오름차순 정렬한다.
    • N-1개 간선이 선택될 때까지 다음의 과정을 반복한다. (MST가 될 때까지)
      • 가중치가 가장 낮은 간선을 탐색한다.
      • union-find 알고리즘을 통해 사이클이 형성되는지 판단한다.
      • 사이클이 형성되지 않을 경우 간선을 선택한다.

🧐 Union-Find 알고리즘

두 개의 노드의 루트를 확인해 서로 같은 그래프에 속하는지를 판별하는 알고리즘

  • union
    • 두 개의 집합을 하나의 집합으로 합치는 연산
    • 즉, 두 집합의 루트를 동일하게 만드는 연산이다!
  • find
    • 원소의 루트를 반환한다.
    • 두 개의 집합의 노드가 서로 같은지를 판단할 수 있다!

🙄 아마 코드를 통해 과정을 살펴본다면 이해가 잘 될 것이다!

🧐 크루스칼 알고리즘 with 파이썬

graph = [(2, 4, 13), (1, 3, 12)...] # (정점1, 정점2, 가중치)
graph.sort(key = lambda x: x[2]) # 가중치로 오름차순 정렬

mst = []
n = 7 # 정점 개수
p = [0] # 각 노드의 루트를 표시

for i in range(1,n+1):
  P.append(i) # 처음, 정점들의 루트는 자기 자신

def find(u): # find 연산
  if u != p[u]:
    p[u] = find(p[u])
  return p[u]

def union(u, v): # union 연산
  r1 = find(u)
  r2 = find(v)
  p[r2] = r1 # 루트를 동일하게 만듬(임의로 r1을 r2의 부모로 설정)

edges = 0 # 간선의 수
cost = 0 # 가중치의 합

while 1:
  if edges == n-1:
    break
  u, v, c = graph.pop(0)
  if find(u) != find(v):
    union(u, v)
    mst.append((u, v))
    cost += c
    edges += 1

print(mst, cost) # 최소 신장 트리, 가중치


🙋‍♀️ 프림 알고리즘

하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식

  • 크루스칼 알고리즘과 마찬가지로 그리디 알고리즘의 일종이다.
  • 순서
    • 하나의 시작 정점을 선택하여 시작 정점만 포함된 MST 집합을 만든다.
    • N개의 정점이 모두 선택될 때까지 다음의 과정을 반복한다.
      • MST 집합에 포함된 정점에 인접하고, 방문되지 않은 정점 중 최소 비용 간선으로 연결된 정점을 선택한다.
      • 해당 정점을 MST 집합에 포함시킨다.

🧐 프림 알고리즘 with python

from collections import defaultdict
from heapq import *

def prim(start, edges):
  mst = []
  adjacent_edges = defaultdict(list)
  for n1, n2, weight in edges:
    adjacent_edges[n1].append((weight, n1, n2))
    adjacent_edges[n2].append((weight, n2, n1))

  connected_nodes = set(start)
  candidate = adjacent_edges[start]
  heapify(candidate)

  while candidate:
    weight, n1, n2 = heappop(candidate)
    if n2 not in connected_nodes:
      connected_nodes.add(n2)
      mst.append((weight, n1, n2))
      for edge in adjacent_edges[n2]:
        if edge[2] not in connected_nodes:
          heappush(candidate, edge)


🙋‍♀️ 크루스칼 vs 프림

  • 시간 복잡도
  • 사용
    • 정점 수 > 간선 수 (희소 그래프) => 크루스칼 알고리즘 적합
    • 정점 수 < 간선 수 (밀집 그래프) => 프림 알고리즘 적합


🙇‍♀️ 부족한 부분이 있다면 말씀해주세요! 감사합니다!

📃참고

댓글남기기

참고