최소 스패닝 트리(MST)

1. 스패닝 트리 / 신장 트리

- 그래프 내의 모든 정점을 포함하고 그래프의 일부 간선을 선택해서 만든 트리

- 스패닝 트리는 노드가 N개, 간선이 N-1개가 됨

- Spanning Tree는 모든 정점들이 연결 되어 어야 하고 사이클을 포함해서는 안된다. Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다.

 

2. 최소 스패닝 트리(MST)

- 간선의 가중치의 합이 최소인 스패닝 트리

- 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우에 사용됨

- 알고리즘 : 크루스칼, 프림 (둘 다 그리디 기반 알고리즘)

 

3. 알고리즘1 : 프림

- https://www.fun-coding.org/Chapter20-prim-live.html

파이썬과 컴퓨터 사이언스(고급 알고리즘): 최소 신장 트리 (Prim's algorithm) - 잔재미코딩

- 정점 선택 기반 알고리즘 

- 시작 정점을 선택하여 트리에 넣고, 인접한 간선 중 최소 간선으로 연결된 정점을 선택해서 트리에 넣음. 해당 방식으

로 트리에 포함된 정점과 연결된 다른 노드 중, 최소 간선으로 연결된 노드를 선택 ( 노드 선택 기반 )

- 우선순위 큐의 heapdict으로 구현 가능

- visited, 우선순위큐, 단방향 그래프 정보 필요

#프림 알고리즘
#프림 알고리즘은 a -> b값이 주어지면  b->a값도 넣어야 함
# visited & 우선순위 큐 필요
#input = sys.stdin.readline

import heapq  #프림 
import sys
from collections import defaultdict #빈 리스트를 생성 
input = sys.stdin.readline

def solution(V,edges):
	mst = list() #최소신장트리
	visited = [False] * (V+1) #방문 확인 리스트
	answer = 0
#1번 노드부터 탐색시작
	visited[1] = True
	hq = edges[1] 
	heapq.heapify(hq) #1번 노드에 연결된 정보를 우선순위 큐로 바꿈

	while hq:
		cost,a,b = heapq.heappop(hq)
		#방문한 적이 없는 노드면 mst에 추가 
		if visited[b] == False:
			visited[b] = True
			mst.append( (a,b) )
			answer += cost
		#방금 추가한 노드의 간선 정보 추가 
			for edge in edges[b]:
				if visited[edge[2]] == False:
					heapq.heappush(hq,edge)
	return answer

if __name__ == "__main__":
    
	V,E = map(int,input().split())
	edges = defaultdict(list) #빈 그래프 생성 
	for _ in range(E):
		a,b,c = map(int,input().split())
		edges[a].append( [c,a,b] )
		edges[b].append( [c,b,a] )
	
	answer = solution(V,edges)
	print(answer)

 

 

 

4. 알고리즘2: 크루스칼(union-find 사용)

- 간선 선택 기반 알고리즘

- 간선을 오름차순으로 정렬 후, 간선을 확인하며 현재 간선이 사이클을 발생시미지 않는다면 최소 신장트리에 포함시킴

- union-find 기반 구현. 단 두 원소를 합치기 전에 find(a) != find(b)를 확인해야 함 

# 최소 스패닝 트리, MST
# 최소스패닝 트리는 어차피 순서가 없으므로 a,b = c랑 b,a = c를 굳이 따로 저장할 필요 없음

#특정 원소가 속한 집합 찾기
#union-by-rank: 각 트리에 대해 높이를 기억. 두 트리의 높이가 다르면 높이가 작은 트리를 큰 트리에 붙임(높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되도록 함)
parent = []

def find(x):
    global parent
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

#두 원소가 속한 집합을 합치기 (간선을 연결)
def union(a,b):
    global parent 
    roota = find(a)
    rootb = find(b)
    
    if roota < rootb:
        parent[rootb] = roota 
    else:
        parent[roota] = rootb

#크루스칼 알고리즘 사용 	  
def solution(V,edges):
    answer = 0
    global parent
    parent = list( range(V+1) )#부모를 자기 자신으로 초기화 
    edges.sort() #비용순으로 오름차순 정렬

    #union 연산 수행
    for edge in edges:
        cost,a,b = edge
    #사이클이 발생하지 않는 경우--부모원소가 같지않은 경우-- 집합에 포함
        if find(a) != find(b):
            union(a,b)
            answer += cost
    return answer 


if __name__ == "__main__":
    V,E = map(int,input().split())
    edges = []

    for _ in range(E):
        a,b,c = map(int,input().split())
        edges.append( (c,a,b))
    
    answer = solution(V,edges)
    print(answer)