[Algorithm] 신장 트리 - 프림 / 크루스칼 알고리즘

* Python을 기준으로 합니다

---

신장 트리 (Spanning Tree) - 프림 / 크루스칼 알고리즘

- 개념

• 신장 트리 : 모든 노드와 연결되어 있으면서 사이클이 존재하지 않는 부분 그래프
  • 이때 간선 개수는 노드의 개수 보다 하나 적음
  • 최소 신장 트리 (Minimum Spanning Tree, MST) : 가중치 합이 최소인 신장 트리
    - 이때 구해지는 최소 신장 트리는 여러 개일 수 있음

• 최소 신장 트리 구하기
  • 공통적으로 그리디 전략을 이용하고, $E$개의 노드 $V$개의 간선에 대해 $O(E \log V)$의 time complexity를 가짐
  • 프림 알고리즘 (Prim Algorithm)
    
    1. 임의의 노드를 선택하여 최소 신장 트리에 추가
    2. 최소 신장 트리와 연결되어 있는 노드 중에서 가장 가중치가 작은 노드를 최소 신장 트리에 추가
       - 이때 cycle이 발생하면 해당 노드를 추가하지 않음
    3. 위 과정을 신장 트리 조건을 만족할 때 까지 반복
  • 크루스칼 알고리즘 (Kruskal Algorithm)
    1. 모든 간선을 가중치 기준으로 오름차순 정렬함
    2. 각 간선에 대하여
       - 가장 낮은 가중치를 가지는 간선 부터 최소 신장 트리에 추가
       - Cycle이 발생하는 경우 추가하지 않음
    3. 위 과정을 신장 트리 조건을 만족할 때 까지 반복

- 구현

1. 프림 알고리즘

• 프림 알고리즘은 우선순위 큐를 활용하여 최소 인접 가중치를 가지는 노드를 추가하는 방식으로 동작

import heapq

def prim(start, graph, mst):
  mst_cost = 0
  visited = [start]

  while len(visited) < len(graph):
    prique = []

    for a in visited:
      for b, cost in graph[a]:
        if b not in visited:
          heapq.heappush(prique, (cost, a, b))

    node = heapq.heappop(prique)
    visited.append(node[2])

    mst_cost +=  node[0] #최소 신장 트리 총 비용
    mst[node[1]] += [(node[2],node[0])] #최소 신장 트리에 추가

  return mst, mst_cost

프림 알고리즘의 동작

• 프림 알고리즘 결과 확인

import collections

#인접리스트 형식 그래프
graph = {
    1:[(2,9),(4,7)],
    2:[(1,9),(3,2),(4,8),(6,5)],
    3:[(2,2),(4,6),(5,4),(6,3)],
    4:[(1,7),(2,8),(3,6),(5,5)],
    5:[(3,4),(4,5)],
    6:[(2,5),(3,3)]
}

mst = collections.defaultdict(list) #최소 신장 트리 초기화

#---------
mst, mst_cost = prim(1, graph, mst)

print(mst_cost) #21
print(mst)
'''
{
  1: [(4, 7)],
  3: [(2, 2), (6, 3)],
  4: [(5, 5)],
  5: [(3, 4)]
}
'''

2. 크루스칼 알고리즘

• 크루스칼 알고리즘은 유니온 파인드를 활용해 최소 가중치를 가지는 간선을 추가하는 방식으로 동작

#유니온 파인드
def find(parent, x):
    if parent[x] == x: #root 노드이면
      return x
  
    #경로압축
    parent[x] = find(parent,parent[x]) #find를 재귀호출하고, parent table의 값을 갱신하는 방식
    return parent[x]

def union(parent, x, y):
    x = find(parent, x)
    y = find(parent, y)

    if x == y: #두 집합이 이미 연결되어 있으면
      return #union하지 않음
  
    #연결되지 않았으면
    if x < y: #더 작은 값을 root로 union함
      parent[y] = x
    else:
      parent[x] = y

#크루스칼 알고리즘
def kruskal(graph, parent, mst):
  edges = []
  mst_cost = 0

  for node in graph:
    for edge, cost in graph[node]:
      edges.append((cost, node, edge)) #간선 배열에 그래프 정보 저장

  edges.sort() #간선 오름차순 정렬

  for cost, a, b in edges: #각 간선에 대해
    if find(parent, a) != find(parent, b): #cycle이 없으면 (두 간선의 root가 다름)
      union(parent, a, b) #union
      mst[a] += [(b,cost)] #최소 신장 트리에 추가
      mst_cost += cost #최소 신장 트리 총 비용
    
  return mst, mst_cost

크루스칼 알고리즘의 동작

• 크루스칼 알고리즘 결과 확인

import collections

#인접리스트 형식 그래프
graph = {
    1:[(2,9),(4,7)],
    2:[(1,9),(3,2),(4,8),(6,5)],
    3:[(2,2),(4,6),(5,4),(6,3)],
    4:[(1,7),(2,8),(3,6),(5,5)],
    5:[(3,4),(4,5)],
    6:[(2,5),(3,3)]
}

parent = [0]*7 #노드개수+1 
for i in range(1, 7): #parent table 초기화
  parent[i] = i 

mst = collections.defaultdict(list) #최소 신장 트리 초기화

#----------
mst, mst_cost = kruskal(graph, parent, mst)

print(mst_cost) #21
print(mst)
'''
{
  1: [(4, 7)],
  2: [(3, 2)], 
  3: [(6, 3), (5, 4)], 
  4: [(5, 5)], 
}
'''