크루스칼 알고리즘 - 2021/03/16

크루스칼 알고리즘이란 신장 트리 중에서 최소비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 중 가장 대표적인 알고리즘이다.

 

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

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

2-1. 사이클을 발생시키면 최소 신장 트리에 포함하지 않는다.

2-2. 사이클을 발생시키지 않으면 최소 신장 트리에 포함한다.

3. 모든 간선에 대하여 2를 반복한다.

 

코드로 나타내면

 

#크루스칼 알고리즘
v,e = map(int,input().split())

parent=[0]*(v+1)
for i in range(v+1):
    parent[i]=i
    
def find_parent(parent,a):
    if parent[a] != a:
        parent[a]=find_parent(parent,parent[a])
    return parent[a]
    
def union(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
result=0
edge=[]
for i in range(e):
    a,b,cost=map(int,input().split())
    edge.append((cost,a,b))
    

edge.sort()
for i in edge:
    cost,a,b=i
    if find_parent(parent,a) != find_parent(parent,b):
        union(parent,a,b)
        result+=cost

 

a,b,cost로 받은 입력을 cost,a,b,순으로 저장해서 정렬을 하고 for문을 이용해 a와 b를 비교한다.