크루스칼 알고리즘(Kruskal Algorithm)

Gyuhan Park·2022년 2월 6일
1

알고리즘 뿌시기

목록 보기
4/9

크루스칼 알고리즘이란?

: 최소 신장 트리(Minimum Spanning Tree)를 구하는 대표적인 알고리즘

신장 트리가 뭐야?

하나의 그래프 내에 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

그럼 최소 신장 트리는?

신장트리는 한 그래프 내에서 여러개가 존재하는데 신장트리 중에서 최소한의 비용으로 만들 수 있는 트리를 최소 신장 트리(Minimum Spanning Tree)라고 한다.

이 MST를 구하는 대표적인 알고리즘이 크루스칼 알고리즘이다.

알고리즘 실행 과정

  1. 주어진 간선들을 가중치를 기준으로 오름차순으로 정렬한다.
  2. 최소 비용 간선부터 뽑는데 사이클이 발생하는지 체크해야 한다.(union-find)
    => 사이클이 발생할 경우 최소 신장 트리에 포함시키지 않는다.
  3. 2를 모든 간선에 대해 반복한다.

사이클이 발생하는 지 체크할 때 union-find 알고리즘을 사용한다. find 함수를 통해 부모노드를 각각 찾고 부모노드가 다른 경우 서로 다른 집합, 즉 이어져있지 않기 때문에 사이클을 발생하지 않는다. 사이클이 발생하지 않았다면 union 함수를 이용해 노드를 이어준다.

이걸 어디에 쓸까?

  • 모든 지점을 연결하는 네트워크의 최소비용을 구하라.
  • 모든 도시를 연결하는 도로의 길이 합이 최소가 되도록 구하라.

크루스칼 알고리즘 소스코드

###### union-find ######

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

###### 크루스칼 알고리즘 ######

v, e = map(int, input().split())
parent = [i for i in range(v+1)]
edges= []
result = 0

# 1. 모든 간선 정보 저장
for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

# 2. 가중치를 기준으로 오름차순 정렬
edges.sort()

for edge in edges:
    cost, a, b = edge
    # 3. 부모 노드가 같으면 cycle 발생
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        result += cost

print(result)
profile
단단한 프론트엔드 개발자가 되고 싶은

0개의 댓글