최소신장트리(MST)

그래프에서 최소 비용 문제

1) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
2) 두 정점 사이의 최소 비용의 경로 찾기

신장 트리

• N개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

최소신장트리(Minimum Spanning Tree)

• 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리
• 연결리스트에 가중치도 같이 저장
• 가중치의 합이 최소가 되려면? 프림, 크루스칼 알고리즘

프림 알고리즘(Prim)

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식 1) 임의 정점을 하나 선택해서 시작
  2) 선택한 정점과 인접하는 정점들 중의 최소 비용이 간선이 존재하는 정점을 선택
  3) 모든 정점이 선택될 때까지 1), 2) 과정을 반복

[Prim 알고리즘 적용 예]

1) 한개의 정점 선택 (MST에 포함)
2) 정점에 연결된 간선 중 비용이 최소인 간선 선택하고, MST에 정점 추가
3) 그 다음 정점에서 연결된 최소 값의 간선 / MST에 포함된 정점과 연결되어 있고 / MST에 아직 포함되지 않은 정점 선택. - 반복(꼭 while문 안써도 정점 개수만큼 for문으로 돌려도 ㄱㅊ)
4) 더이상 없을 때 끝

문제 - 백준 1197 최소 스패닝 트리(골드4)
https://www.acmicpc.net/submit/1197/34894341

코드

# 1197 최소 스패닝 트리 - 골드5 김수
import heapq
import collections
V, E = map(int, input().split())
# 빈그래프 생성 - 리스트를 초기값으로 가지는 딕셔너리
graph = collections.defaultdict(list)
# MSt 포함 여부
visited = [0] * (V + 1)
for _ in range(E):
    a, b, m = map(int, input().split())
    graph[a].append([m, a, b])
    graph[b].append([m, b, a])

def prim(graph, start):
    visited[start] = 1
    # 시작 노드에 연결된 애들이 후보
    candidate = graph[start]
    heapq.heapify(candidate) # 최소힙 - 가중치 기준
    MST = []
    total = 0
    while candidate:
        m, u, v = heapq.heappop(candidate)
        if visited[v] == 0:
            visited[v] = 1
            MST.append((u, v))
            total += m
            # 다음 정점에 연결된 애들
            for edge in graph[v]:
                if visited[edge[2]] == 0:
                    heapq.heappush(candidate, edge)
    return total

print(prim(graph, 1))