[알고리즘] 최소 스패닝 트리 알고리즘 | 크루스칼/프림 알고리즘

~목차~

스패닝 트리란?

크루스칼 알고리즘

프림 알고리즘

---

 

(최소) 스패닝 트리란?

 최소 스패닝 트리 알고리즘을 설명하기 이전에 스패닝 트리(Spanning Tree)란 무엇인가 알아보도록 하겠습니다.

 

스패닝 트리는 어떤 그래프에서 모든 노드를 연결하며 사이클이 없는 부분 그래프를 의미합니다

 

그림으로 이해해보겠습니다

왼쪽과 같은 초기 그래프가 있을 때 오른쪽 그래프는 스패닝 트리입니다.

그럼 아래 그래프는 스패팅 트리 일까요?

아닙니다. 오른쪽 그래프는 사이클이 발생했고, 오른쪽 그래프는 모든 노드를 연결하지 않고 있습니다.

 

그렇다면 아래 그래프는 신장(스패닝) 트리일까요?

그렇습니다. 신장 트리 중 최소 신장 트리입니다.

 

최소 신장(스패닝) 트리는 신장 트리 중 가장 적은 비용을 갖는 그래프입니다.

모든 노드를 연결하고 있으므로 간선의 개수는 '(노드 개수) - 1' 입니다

최소 스패닝 트리

 

최소 스패닝 트리를 구하는 대표적인 방법으로 크루스칼(kruskal) 알고리즘과 프림(prim) 알고리즘이 있습니다

두 알고리즘은 조건에 만족하는 간선 중 가장 적은 비용을 갖는 간선부터 연결해 나가므로 그리디 알고리즘에 속합니다.

 

 

 

 

크루스칼 알고리즘 | Kruskal

그렇다면 최소 스패닝 트리를 어떤 방식으로 구할 수 있을까요?

그 대표적인 방법 중 하나인 크루스칼 알고리즘에 대해서 살펴보겠습니다.

 

남아 있는 간선 중 가장 작은 간선부터 사이클이 발생하지 않으면 연결해 나갑니다.

각 노드가 같은 집합에 속했는지 확인하기 위해서 서로소 집합 개념을 사용할 수 있습니다.

 

최소 스패닝 트리를 구하는 크루스칼 알고리즘의 기본 구현 코드

import sys
input = sys.stdin.readline # 입력 속도 향상을 위한 처리

parent = [i for i in range(V+1)]  # 각 노드가 어떤 집합에 속해있는지 정보
result = 0

def find_parent(x):  # x노드에 대해서 어떤 집합에 속했는지 반환
    if parent[x] != x:
        parent[x] = find_parent(parent[x])  # 집합 노드 업데이트
    return parent[x]

def union_parent(a, b):  
    a = find_parent(a)  # a의 집합
    b = find_parent(b)  # b의 집합
    if a < b:  # 작은 노드 번호로 통합
        parent[b] = a
    else:
        parent[a] = b

V, E = map(int, input().split())  # 노드 수, 간선 수 
edges = []  # 간선 정보 저장할 리스트

for i in range(E):
    a, b, w = map(int, input().split())
    edges.append((w, a, b))  # (비용, 노드a, 노드b)

edges.sort()  # 비용 기준으로 오름차순 정렬

for w, a, b in edges:  # 작은 간선부터 순차적으로
    if find_parent(a) != find_parent(b):  # 사이클이 발생하지 않으면
        union_parent(a, b)  # 집합 통합
        result += w  # 간선 비용 계산

print(result)

 

 

문제 풀이

2023.05.23 - [📁문제 풀이/🧩Baekjoon] - [Python] 백준 1197 최소 스패닝 트리

2023.05.28 - [📁문제 풀이/🧩Baekjoon] - [Python] 백준 1922 네트워크 연결 | 크루스칼 알고리즘

2023.05.29 - [📁문제 풀이/🧩Baekjoon] - [Python] 백준 14621 나만 안되는 연애 | 크루스칼 알고리즘

 

 

 

 

 

프림 알고리즘 | Prim

최소 스패닝 트리를 구하는 프림 알고리즘입니다.

우선순위 큐를 이용하여 구현할 수 있습니다. 스패닝 트리에 노드가 포함됐는지 여부는 set 을 이용합니다

 

왼쪽 위부터 오른쪽 아래까지 순서대로 보면

 

1. 시작 노드와 연결된 간선을 최소힙으로 생성 & 시작 노드를 연결

2. 최소 비용을 갖는 노드를 선택하여 연결되지 않았다면 연결 & 해당 노드와 연결된 간선 힙에 삽입

3. 2 반복

 

 

 

프림 알고리즘 기본 구현 코드

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
connected = set()  # 스패닝 트리에 속한 노드
graph = [[] for _ in range(n+1)]  # 각 노드별 연결된 노드들
startNode = (INF, 0)  # (길이, 노드)
result = 0

for _ in range(m):  # 간선
    a, b, w = map(int, input().split())
    # 무방향 그래프이므로 두 노드에 대해서 모두 연결
    graph[a].append((w, b))
    graph[b].append((w, a))
    startNode = (w, a) if startNode[0] > w else startNode  # 가장 작은 간선을 가지는 노드

q = graph[startNode[1]]
heapq.heapify(q)  # 시작 노드에 연결된 모든 노드들 최소 힙 변경

connected.add(startNode[1])  # 시작 노드 연결

while q:
    w, b = heapq.heappop(q)  # 접근 가능한 간선 중 가장 적은 비용
    if b not in connected:  # 연결되지 않았다면
        connected.add(b)  # 노드 연결
        result += w  # 간선 비용 계산
        
        for w2, a2 in graph[b]:  # 연결된 노드와 연결된 간선들
            if a2 not in connected:  # 이미 연결되어 있지 않다면
                heapq.heappush(q, (w2, a2))  # 최소 힙에 삽입

print(result)

 

 

 

 

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

---

REFERENCE

<이것이 취업을 위한 코딩테스트다 with Python> 서적

https://velog.io/@syc1013/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EC%86%8C%EC%8B%A0%EC%9E%A5%ED%8A%B8%EB%A6%AC-Minimum-Spanning-Trees#prim-algorithm