이호진
크루스칼 알고리즘 - 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를 비교한다.
'주요 알고리즘' 카테고리의 다른 글
최단 경로 알고리즘 - 다익스트라 - 2021/04/02 (0) | 2021.04.02 |
---|---|
다익스트라 알고리즘 - 2021/03/22 (0) | 2021.03.22 |
음료수 얼려먹기 - DFS (2021/02/22) (0) | 2021.02.22 |
탐색 알고리즘 BFS (2021/02/21) (0) | 2021.02.21 |
탐색 알고리즘 DFS (2021/02/21) (0) | 2021.02.21 |