크루스칼_Kruskal

크루스칼(Kruskal)

• 탐욕적인 방법(greedy method)을 이용하여 네트워크(가중치 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
  • 탐욕적인 방법
    • 결정을 할 때마다 그 순간 가장 좋다고 생각 되는것을 선택함으로서 최종적인 해답에 도달하는 것
    • 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야한다.
    • Kruscal 알고리즘은 최적의 해답을 주는 것으로 증명되었다.

동작

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

특징

• 간선선택을 기반으로 하는 알고리즘
• 다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는지 체크
  • 새로운 간선이 이미 다른 경로에 의해 연결되어있는 정점들을 연결할 때 사이클이 형성된다.
  • 즉, 추가 할 새로운 간선의 양 끝 정점이 같은 집합에 속해 있으면 사이클이 형성된다.
• 사이클 생성 여부를 확인하는 법
  • union-find 알고리즘 이용
• 시간복잡도
  • 간선 e개를 퀵정렬과 같은 효율적인 알고리즘으로 정렬한다면 O(eloge)
  • prim 의 알고리즘 시간복잡도는 O(n²)
    • 그래프 내 적은 숫자의 간선만을 가지는 ‘희소 그래프(Spares Graph)는 Kruskal
    • 그래프 내 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 는 prim