최소 신장 트리(MST)

최소 신장 트리

무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

신장 트리란?

그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미함, 하나의 그래프엔 많은 신장트리가 존재함

특징

• 신장 트리 중 가중치의 합이 가장 최소인 신장 트리
• 간선의 수가 가장 적다, 최소 간선의 개수 n-1

사례

• 도로 건설 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
• 전기 회로 단자들을 모두 연결하면서 전선의 기리가 최소가 되도록 하는 문제
• 통신 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제

Code

최소 스패닝 트리

import heapq
import sys
input = sys.stdin.readline

def bfs(start):
    global total
    q=[*G[start]]
    visited[start]=1
    heapq.heapify(q)

    while q:
        w,s = heapq.heappop(q)

        if visited[s]==0:
            visited[s]=1
            total +=w

            for w, next in G[s]:
                if visited[next]==0:
                    heapq.heappush(q,(w,next))



v,e = map(int,input().split())
G=[[] for _ in range(v+1)]
visited=[0]*(v+1)
total =0

for _ in range(e):
    n1,n2,w = map(int,input().split())
    G[n1].append((w,n2))
    G[n2].append((w,n1))

bfs(1)
print(total)