크루스칼 알고리즘

크루스칼 알고리즘에 대해 공부해보겠습니다.
크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다.
즉 MST를 만들기 위한 대표적인 알고리즘 입니다.

언택트 시대를 맞아 저희 집의 MST를 구해보겠습니다.

위 그래프를 보면 노드의 갯수는 5개 이고, 간선의 갯수는 6개 입니다.

크루스칼 알고리즘의 핵심 개념은 간선의 거리가 짧은 순서대로 그래프에 포함 시키는 것 입니다.

• Greedy한 방법을 이용, 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하기

MST (최소 비용 신장 트리)

• 최소 비용 간선으로 구성
• 사이클을 포함하지 않음

Kruskal 알고리즘의 동작

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다
   • 즉, 가장 낮은 가중치를 먼저 선택한다
   • 사이클을 형성하는 간선을 제외한다.
3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.

Kruskal 알고리즘을 이용하여 MST를 만드는 구체적인 과정은 아래와 같다

• 간선 선택 기반 알고리즘
• 이전 단계에서 만들어진 신장 트리와 상관 없이 무조건 최소 간선만 선택

• 밥먹거나 소파에 있다가 책상으로 오기전에 침대를 거치는 것이 효율적이군요

주의 해야할 점

다음 간선을 이미 선택딘 간선들의 집합에 추가할 때 사이클을 생성하는지 체크

사이클 생성 여부를 확인하는 방법

• 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사.
• ‘union-find 알고리즘’이용

Kruskal 알고리즘의 시간 복잡도

• union-find 알고리즘을 이용하면 Kruskal 알고리즘의 시간 복잡도는 간선을 정렬하는 시간에 좌우 됨.
• 즉, 간선 e개를 퀵 정렬과 같은 효율적인 알고리즘으로 정렬
• 시간 복잡도는 O(elog2e)

Prim 알고리즘의 시간 복잡도는 O(n^2)

• 그래프 내에 적은 숫자의 간선만을 가지는 Sparse Graph의 경우 kruskal이 적합하고
• 간선이 많이 존재하는 Dense Graph의 경우 Prim 알고리즘이 적합

연관 개념

• 최소 신장 트리 (MST)
• Prim 알고리즘
• 그래프 (Graph)
• 트리 (Tree)