크루스칼 알고리즘이란? (+ 최소신장트리 란?)

신장트리 란?

 

크루스칼 알고리즘 이란?

• 크루스칼 알고리즘 구현

 

관련 백준 문제

 

---

신장 트리(Spanning Tree) 란?

그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프

n 개의 정점이 있다면 신장 트리의 간선 수는 n-1 개

 

최소 신장 트리(Minimum Spanning Tree)는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리

가중치는 거리, 비용, 시간 등 여러가지로 응용 가능

 

최소 신장 트리의 대표적인 알고리즘은 프림(Prim),  솔린(Sollin), 크루스칼(Kruskal) 알고리즘이 존재

 

Prim 알고리즘

최초 선택된 정점에 연결된 간선들 중에서 작은 가중치를 가지는 간선을 선택하여 만드는 알고리즘

간선의 개수 N, 노드의 개수가 E 시간복잡도 O(N^2) 또는 힙을 이용한다면 O(ElogN)

 

Sollin 알고리즘

각 정점에 대해서, 정점에 연결된 가장 가중치 낮은 간선을 선택하여 단계별로 진행하여 만드는 알고리즘

간선의 개수가 N개 일 때 시간복잡도 O(NlogN)

 

 

크루스칼 (Kruskal) 알고리즘 이란?

사이클을 생성하지 않은 간선들 중에 가장 작은 가중치를 가지는 간선을 선택하여 만드는 알고리즘

그리디 알고리즘으로 분류

시간 복잡도는 간선의 개수가 N개 일 때 O(NlogN)

 

구체적인 동작 과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬

2. 간선을 하나씩 확인하며 현재이 간선이 사이클을 발생시키는지 확인

• 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
• 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음

 

3. 모든 간선에 대해 2번 과정을 반복

 

 

 

 

크루스칼 알고리즘 구현

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
    if parent[x]!=x:
        parent[x]=find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합 합치기
def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        print[a]=b

# 노드의 개수와 간선(union 연산)의 개수 입력 받기
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(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        result+=cost

print(result)

 

# 입력 예시

7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25

 

# 출력 예시
159

 

 

관련 백준 문제 및 문제풀이