최소 비용 트리

비용 트리 Spanning Tree

그래프가 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 무방향 그래프

조건

1. 해당 그래프의 모든 노드를 포함해야 한다.
2. 그 노드들이 서로 연결되어 있어야 한다.
3. "사이클이 존재하지 않는다"는 트리의 속성을 만족해야한다.
4. n개의 정점과 n-1개의 간선으로 이루어져야 한다.

최소 비용 트리

간선에 가중치가 있을 때, 연결된 간선의 가중치 합이 최소인 비용 트리

응용

통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간

관련 알고리즘

Kruskal 알고리즘

• 간선을 선택
• 탐욕 알고리즘을 사용한다. : 가장 비용이 적은 것부터 선택하기

동작

1. 모든 정점을 독립적인 집합으로 만듦
2. 비용을 기준으로 정점을 정렬하기
3. 비용이 작은 간선부터 선택하기
4. 해당 간선의 두 정점 비교
5. 두 정점의 최상위 정점 확인
6. 다를 경우 두 정점을 연결 -> 사이클이 발생하지 않음

Union-Find 알고리즘

간선 선택시 사이클이 생기는지 안생기는지 확인하는 법

• Disjoint Set을 표현시 사용하는 알고리즘
  • Disjoint Set?
    서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
    공통 원소가 없는 상화 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조를 의미한다.
    "서로소 집합 자료구조"
• 노드들 중 연결된 노드를 찾거나 노드를 서로 연결할 때 사용

동작

1. 초기화 : n개의 원소가 개별 집합으로 이뤄지도록 초기화
2. Union (연결)
   두 개별 집합을 하나의 집합으로 합침
3. Find (사이클 유무)
   여러 노드가 존재할 때, 두 노드를 선택해 현재 노드가 서로 같은 그래프에 속하는 지 판별하기 위해 각 그룹의 최상단 원소 즉 루트 노드를 확인
   • 루트 노드가 동일 : 이미 연결, 부분 집합 ➡️ 사이클 발생

고려할 점

• union 순서에 따라 성능이 바뀜 (Find시 루트 노드 찾아가는 데 중요함)
• 그래서 union-by-rank, path compression 기법을 사용하게 됨

1. union-by-rank
   높이 rank를 저장해두고, 두 트리의 높이가 다르면 높이가 작은 것을 큰 것에 붙임.
   rank를 모드 0이게 집합에 저장해둠.
   시간 복잡도가 O(n)에서 O(logN)으로 낮출 수 있음

2. path compression

• find를 실행한 노드에서 거쳐간 노드를 루트로 바로 연결하는 법

➡️ 위 두 알고리즘을 사용하면 O(MlogN)이 됨

코드

parent = dict()
rank = dict()


def find(node):
    # path compression 기법
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]


def union(node_v, node_u):
    root1 = find(node_v)
    root2 = find(node_u)
    
    # union-by-rank 기법
    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1
    
    
def make_set(node):
    parent[node] = node
    rank[node] = 0

def kruskal(graph):
    mst = list()
    
    # 1. 초기화
    for node in graph['vertices']:
        make_set(node)
    
    # 2. 간선 weight 기반 sorting
    edges = graph['edges']
    edges.sort()
    
    # 3. 간선 연결 (사이클 없는)
    for edge in edges:
        weight, node_v, node_u = edge
        if find(node_v) != find(node_u):
            union(node_v, node_u)
            mst.append(edge)
    
    return mst

Prim 알고리즘

• 노드를 선택
• 탐욕 알고리즘을 기초로
• 정점 선택 후 인접 간선 중 최소 간선으로 연결된 정점 선택 후 이를 반복하면서 최소 신장 트리를 확장해 나가는 방식

동작

1. 임의의 정점 선택, 연결된 노드 집합에 삽입
2. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입
3. 간선 리스트에서 최소 가중치를 가지는 간선 고르기
4. 해당 간선에 연결된 인접 정점이 이미 연결된 노드 집합에 포함돼있다면 스킵 (cycle 방지)
5. 1이 아니라면 간선 선택 후 해당 간선을 최소 신장 트리에 삽입
   ➡️ 최소 힙 구조 사용하여 최소 가중치를 갖는 간선 뽑는 효율성을 챙기기
6. 선택된 간선을 간선 리스트에서 제거
7. 간선 리스트가 빌 때까지 3~4를 반복

고려할 점

• collections 라이브러리의 defaultdict 함수 활용하기
  defaultdict 함수를 사용해 key에 대한 value를 지정하지 않으면 빈 리스트로 초기화
• heapq 라이브러리 이용해 우선순위 큐 사용하기

코드

from collections import defaultdict
from heapq import *

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

    connected_nodes = set(start_node)
    candidate_edge_list = adjacent_edges[start_node]
    heapify(candidate_edge_list)
    
    while candidate_edge_list:
        weight, n1, n2 = heappop(candidate_edge_list)
        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_list, edge)

    return mst

➡️ 최악의 경우 while 구문에서 모든 간선을 반복함. 최소 힙이므로 O(ElogE)

개선된 코드

• 노드를 중심으로 우선순위 큐 적용
  1. 초기화 : (정점:key) 구조를 만들어두고, 특정 정점의 key는 0으로 이외 정점의 key는 무한대로. 모든 (정점:key) 값을 우선순위 큐에 넣어둠
  2. 가장 key 값이 적은 세트를 추출 후 (pop)
  3. 해당 정점의 인접한 정점에 대해 key값과 연결된 가중치 값을 비교하여 key 값이 작으면 해당 정점 세트 값으로 갱신. 루트노드에는 최소 key 값을 갖는 (정점:key)가 올라가야 함.
• 우선 순위 쿠조에서 이미 들어가있는 데이터 값 변경 시 최소값을 가지는 데이터가 루트노드로 올라가도록 하는 재구성 기능이 필요
  ➡️ 구현 복잡도를 줄이기 위해 heapdict 라이브러리를 통해 기능 구현

from heapdict import heapdict

def prim(graph, start):
    mst, keys, pi, total_weight = list(), heapdict(), dict(), 0
    for node in graph.keys():
        keys[node] = float('inf')
        pi[node] = None
    keys[start], pi[start] = 0, start

    while keys:
        current_node, current_key = keys.popitem()
        mst.append([pi[current_node], current_node, current_key])
        total_weight += current_key
        for adjacent, weight in mygraph[current_node].items():
            if adjacent in keys and weight < keys[adjacent]:
                keys[adjacent] = weight
                pi[adjacent] = current_node
    return mst, total_weight