Spanning Tree

: 그래프 내의 모든 정점을 포함하는 트리
(신장 트리 = 스패닝 트리)

• 그래프의 최소 연결 부분 그래프
  • 최소 연결 = 간선의 수가 가장 적다
  • n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개
    
    
    

Spanning Tree의 특징

• DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있음
• 하나의 그래프에는 많은 신장 트리가 존재할 수 있음
• 모든 정점들이 연결되어 있어야 하며, 사이클을 포함해서는 안됨

n개의 정점을 정확히 (n-1)개의 간선으로 연결

MST (Minimum Spanning Tree)

: Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

구현 방법

• 크루스칼(Kruskal) 알고리즘 - 정점에 비해 간선이 적은 그래프에서 적합
• 프림(Prim) 알고리즘 - 정점에 비해 간선이 많은 그래프에서 적합

크루스칼(Kruskal) 알고리즘

1. 간선 데이터를 비용에 따라 오름차순 정렬
2. 간선을 하나씩 확인하며 사이클을 발생시키는지 확인
   2-1. 발생하지 않으면 MST에 포함
   2-2. 발생한다면 포함시키지 X
3. 모든 간선에 대하여 2번의 과정을 반복

1. 그래프 간선을 가중치에 따라 오름차순으로 정렬
   
   
   
2. 비용이 최소인 간선을 선택한 후 union
   
   
   
   
   
3. (6, 7)을 선택할 경우 사이클이 발생하므로 연결하지 않는다.
   
   
   
4. 비용이 최소인 간선을 선택한 후 union
   
   
   
   
   

사이클 판단 - Union & Find 활용

• Union&Find 알고리즘을 사용
  • 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
  • union 연산과 find 연산을 사용
    
    
• union - 2개 원소로 이루어진 집합을 하나의 집합으로 합치기
• find - 특정 원소가 속한 집합이 뭔지 알려주는 연산

1. 간선 선택 전, 초기에 각각 서로소 집합 {1}, {2}, {3}, {4}로 표현됨
   

• parent 배열은 각 정점의 root node(부모)를 표현한 배열
• 초기에는 자기 자신이 루트 노드가 되게 초기화됨 parent[i] = i
  
  

2. 간선을 선택
   
   

• 1번과 2번이 같은 집합으로 Union 연산에 의해 합쳐지고, 2번의 부모는 1번이 됨

  서로소 집합 {1, 2}, {3}, {4}

• 그 집합 내에서 제일 작은 숫자가 그 집합에서의 루트 노드가 되게끔 가정
  • 루트 노드가 다르면 Union 연산에 의해 합쳐진다.
    
    

3. 다음으로 간선을 선택
   
   

• 서로 부모가 같으면 Union 연산을 하지 않음 (합친다면 사이클을 형성하게 됨)

# 특정 원소가 속한 집합 찾기 - 부모를 반환
def find(parent, x):
	if parent[x] == x:
    	return x
	parent[x] = find(parent, parent[x])
    return parent[x]
    
# 두 원소가 속한 집합을 합치기 (간선 연결)
def union(parent, a, b):
	rootA = find(parent, a)
    rootB = find(parent, b)
    
    # 제일 작은 숫자가 루트 노드가 되도록
    if rootA < rootB:
    	parent[rootB] = rootA
	else:
    	parent[rootA] = rootB
        
import sys
input = sys.stdin.readline

# v - 노드 개수, e - 간선 개수
v, e = map(int, input().split())
parent = [0] * (v + 1) # 인덱스를 정점 번호로 사용할 수 있도록

edges = []
result = 0

# 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
	parent[i] = i
    
# 모든 간선에 대한 정보를 입력 받기
for _ in range(e):
	a, b, cost = map(int, input().split())
    edges.append((cost, a, b))
    
edges.sort()

for edge in edges:
	cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find(parent, a) != find(parent, b):
    	union(parent, a, b)
        result += cost
        
print(result)

• 시간 복잡도 O(ElogE)

프림(Prim) 알고리즘

1. 시작 단계는 시작 노드만이 MST 집합에 속한다
2. 트리 집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점에 대해 간선과 정점을 집합에 추가

• 사이클을 막기 위하여 연결된 정점이 이미 집합에 속한다면 그 다음 순서를 넣는다.

3. 2번 과정을 집합의 원소 개수 == 그래프의 정점의 개수가 될 때까지 반복

import heapq
import collections
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = map(int,input().split()) # 노드 수, 간선 수
graph = collections.defaultdict(list) # 빈 그래프 생성
visited = [0] * (n+1) # 노드의 방문 정보 초기화

# 무방향 그래프 생성
for i in range(m): # 간성 정보 입력 받기
    u, v, weight = map(int,input().split())
    graph[u].append([weight, u, v])
    graph[v].append([weight, v, u])

def prim(graph, start_node):
    visited[start_node] = 1 # 방문 갱신
    candidate = graph[start_node] # 인접 간선 추출
    heapq.heapify(candidate) # 우선순위 큐 생성
    mst = [] # mst
    total_weight = 0 # 전체 가중치

    while candidate:
        weight, u, v = heapq.heappop(candidate) # 가중치가 가장 적은 간선 추출
        if visited[v] == 0: # 방문하지 않았다면
            visited[v] = 1 # 방문 갱신
            mst.append((u,v)) # mst 삽입
            total_weight += weight # 전체 가중치 갱신

            for edge in graph[v]: # 다음 인접 간선 탐색
                if visited[edge[2]] == 0: # 방문한 노드가 아니라면, (순환 방지)
                    heapq.heappush(candidate, edge) # 우선순위 큐에 edge 삽입

    return total_weight

print(prim(graph,1))