TIL #24 : Minimum Spanning Tree

📝 Spanning Tree

👇 아래 조건을 만족하는 그래프
◾ 연결 그래프의 부분 그래프로 모든 노드를 포함!
◾ 모든 노드가 서로 연결되어 있어야 함
◾ 트리의 속성을 만족 ➜ 사이클이 존재 X

📝 최소 신장트리

Minimum Spanning Tree, MST라고 불리며,
가능한 Spanning Tree 중, 간선의 가중치 합이 최소인 Spanning Tree

📝 대표 알고리즘

📌 kruskal 알고리즘

1. 모든 정점을 독립적인 집합으로 만듬.
2. 모든 간선: 비용 기준으로 정렬 ➜ 비용이 적은 간선부터 양 끝 정점 비교
3. 사이클을 생기지 않으면, 두 정점을 연결!
   👉 모든 정점이 연결될 때까지, 2-3번 과정 반복

• make_set() : 모든 정점이 개별 집합을 이루도록 초기화
• find_paret() : 해당 노드의 루트 노드를 리턴
• union() : 두개의 개별 집합을 하나로 합침 (= 두 개의 트리를 하나로 합침)
  • union_by_rank 기법 으로 두 개 트리의 높이가
    ❓ 다른 경우, 높이가 큰 트리에 높이가 작은 트리를 붙임
    ❓ 같은 경우, 한 쪽 트리의 높이를 1 증가시켜주고, 다른 쪽 트리를 해당 트리에 붙임

parent = dict()
rank = dict()

def make_set(node):
    parent[node] = node
    rank[node] = 0

def find_parent(v1):
    if v1 != parent[v1]:
        parent[v1] = find_parent(parent[v1])
    return parent[v1]

def union(v1, v2):
    root_v1 = find_parent(v1)
    root_v2 = find_parent(v2)

    if rank[root_v1] > rank[root_v2]:
        parent[root_v2] = root_v1
    else:
        parent[root_v1] = root_v2
        if rank[root_v1] == rank[root_v2]:
            rank[root_v2] += 1

def kruskal(graph):
    mst = list()

    for node in graph['vertices']:
        make_set(node)

    edges = graph['edges']
    edges.sort()

    for edge in edges:
        w, v1, v2 = edge
        if find_parent(v1) != find_parent(v2):
            union(v1, v2)
            mst.append(edge)

    return mst

👏 데이터 입력 예시

graph = {
    'vertices' : ['A','B','C','D','E','F','G'],
    'edges' : [
        (7, 'A', 'B'),
        (5, 'A', 'D'),
        (9, 'B', 'D'), 
        (8, 'B', 'C'), 
        (7, 'E', 'B'),
        (5, 'C', 'E'), 
        (9, 'G', 'E'),
        (8, 'F', 'E'), 
        (11, 'F', 'G'), 
        (6, 'F', 'D'), 
        (7, 'E', 'D')
    ]
}

kruskal(graph)

📌 prim 알고리즘

1. 시작 정점 선택
2. 정점에 인접한 간선 중 최소 비용의 간선으로 연결된 정점 선택
3. 해당 정점에서 다시 2번 과정 반복하며 최소 신장 트리를 확장해나감!

• adjacent_edges : 모든 간선 정보를 저장할 리스트
• connected_nodes : 선택된 정점들을 저장할 리스트
• candidate_edges : 선택된 정점에 연결된 간선들을 삽입할 리스트
  • 최소 가중치를 가지는 간선부터 추출!
    • ❗ 해당 간선에 연결된 정점이 connected_nodes 안에 포함되어져 있으면 연결 시, 사이클이 생기므로 SKIP!

from collections import defaultdict
from heapq import *

def prim(start_node, edges):
    mst = list()
    adjacent_edges = defaultdict(list)

    for w, v1, v2 in edges:
        adjacent_edges[v1].append((w, v1, v2))
        adjacent_edges[v2].append((w, v2, v1))

    connected_nodes = set(start_node)
    candidate_edges = adjacent_edges[start_node]
    heapify(candidate_edges)

    while candidate_edges:
        w, v1, v2 = heappop(candidate_edges)
        if v2 not in connected_nodes:
            connected_nodes.add(v2)
            mst.append((w, v1, v2))

            for edge in adjacent_edges[v2]:
                if edge[2] not in connected_nodes:
                    heappush(candidate_edges, edge)

    return mst

👏 데이터 입력 예시

edges = [
    (7, 'A', 'B'), (5, 'A', 'D'),
    (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'),
    (5, 'C', 'E'),
    (7, 'D', 'E'), (6, 'D', 'F'),
    (8, 'E', 'F'), (9, 'E', 'G'),
    (11, 'F', 'G')
]

prim('A', edges)

📝 kruskal 과 prim 비교

• 둘 다, 탐욕 알고리즘을 기초로 하고 있음.
• kruskal : 가장 가중치가 작은 간선부터 선택하면서 MST를 구함.
• prim : 특정 점점에서 시작하여 해당 정점에 연결된 가장 가중치가 작은 간선을 선택 후, 해당 간선에 연결된 정점의 인접 간선 중에서 가장 가중치가 작은 간선을 선택하는 방식으로 MST를 구함.