[알고리즘] 신장트리(크루스칼 알고리즘)

Hyo Kyun Lee·2022년 1월 25일

신장트리 알고리즘 크루스칼 알고리즘

알고리즘

목록 보기

37/45

1. 신장트리

Spanning Tree, 그래프가 모든 노드가 연결되어 있으면서 사이클이 존재하지 않는 그래프를 의미한다.

모든 노드가 연결되어있지만 cycle이 존재하지 않는다는 점에서 tree라 명명하고, 전체 graph에서 부분적으로 신장트리를 도출해낼 수도 있다.

2. 최소신장트리

이때 한 graph에서 최소한의 비용으로 모든 도로를 연결하고 싶을때, 단 cycle이 발생하지 않도록 tree 형태로 graph를 구성하고자 할 때 최소신장트리를 구성하는 방법을 활용할 수 있다.

즉 최소한의 비용으로 신장트리를 구성하는 것이고, N개의 노드가 있을때 각 노드 간 간선을 놓아 전체 도시가 연결될 수 있도록 구성한다.

이를 구현할 수 있는 과정이 최소신장트리, 다른 말로 크루스칼 알고리즘이라 일컫는다.

3. 크루스칼 알고리즘

최소신장트리를 구성하기 위한 가장 대표적인 구현 방법이다.

간선 간 가장 적은 비용을 중심으로 사이클을 확인하고, 사이클이 없을때 최소신장트리를 구성하는 과정을 반복하므로 그리디 알고리즘의 일종이다.

간선 데이터를 비용에 따라 오름차순으로 정렬한다.
최소 비용 순으로 간선 정보를 확인해가면서,
※ 사이클이 발생할 경우엔 최소신장트리에 포함하지 않는다.
※ 사이클이 발생하지 않았을 경우엔 최소신장트리에 포함한다.
모든 과정을 반복한다.

위 그래프에서 각 간선에 연결된 노드와 간선비용이 나열되어있다고 할때, 크루스칼 알고리즘을 처리하는 순서는 비용이 적은 순서대로 진행한다.

간선(3,4) - 비용7 : 현재 서로소 집합이므로 union 하고, 서로 잇는다.
간선(4,7) - 비용 13 : 현재 서로소 집합이므로 union 하고, 서로 잇는다.
...
간선(6,7) - 비용 25 : 6과 7은 이미 같은 부모노드를 향하는 합집합으로, union을 진행하지 않고 넘어간다(union 진행 시 사이클이 발생한다).
..

같은 집합에 속한다면 서로 잇지 않고, 다음 비용의 간선으로 넘어가서 처리한다.
이 과정을 모두 진행한 후, 각 그래프는 최소비용으로 구성된 최소신장트리이다.

#unionfind를 활용하여 최소신장트리를 구성한다.
def findParent(parent, x):
    if parent[x] != x:
        parent[x] = findParent(parent, parent[x])
    return parent[x]

def unionParent(parent, a, b):
    a = findParent(parent, a)
    b = findParent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

import sys
#노드 개수와 간선(union 연산) 개수 입력 받기
v, e = map(int, sys.stdin.readline().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, sys.stdin.readline().split())
    #a, b노드가 이어진 간선의 비용은 c이다.
    edges.append((cost, a, b))
edges.sort() #오름차순 정렬

#크루스칼
for edge in edges:
    cost, a, b = edge
    #사이클 발생하지 않을때 union
    if findParent(parent, a) != findParent(parent, b):
        unionParent(parent, a, b)
        result = result + cost
    else:
        continue

print(result)