최소 비용 신장트리

📌최소 비용 신장트리

💡최소 비용 신장트리

1. 정의
   • 가중치가 부여된 무방향 그래프에서 신장 트리의 비용
     가중치 : 두 vertex 사이의 거리 혹은 연결하는 비용
     = 신장트리를 구성하는 에지들의 비용의 합
   • 최소 비용 신장트리 : 가장 비용이 적은 신장 트리

2. 응용 분야
   • 도로 건설 : 도시를 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
     ex) 통신, 배관

3. 최소 비용 신장트리 알고리즘
   • 최소 비용 신장트리 알고리즘
     1) 그래프 내에 존재하는 Edge들만 사용한다.
     2) 정점의 개수가 n일 때, n - 1개의 Edge들만 사용한다.
     3) 사이클을 형성하는 edge는 사용불가하다.
   • 최소 비용 신장트리를 구하기 위한 알고리즘들
     1) 크루스칼
     2) 프림
     3) 솔린

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

• E log E 의 시간 복잡도를 가진다.
  Heap 을 이용하여 구현하는 것이 필요하다.

1. 알고리즘의 개요
   • Edge들을 비용의 오름차순으로 정렬한다.
   • 가장 비용이 적은 Edge부터 하나씩 선택한다.
   • 선택된 Edge는 기존에 선택된 Edge들과 사이클을 형성하지 않을 경우에만 신장트리 T에 포함된다.
   • 그래프 G가 연결되어 있으며, N(> 0)개의 정점이 존재하는 경우, 정확히 N-1개의 Edge가 선택된다.

💡프림 알고리즘(Prim Algorithm)

• 이미 선택된 것에서 나머지로 가는 것만 체크한다.
  Prim 알고리즘에서는 사이클 검사가 따로 필요하지 않는다.

1. 알고리즘의 개요
   • 하나의 정점만 갖는 트리 T에서 시작한다.
   • T에 포함된 정점과 포함되지 않는 정점을 연결하는 Edge들 중에서 비용이 최소인 Edge를 T에 추가한다.
   • 추가된 Edge의 vertex를 T에 포함한다.
     O(n * n)

희소 그래프 = 크루스칼 = 정점이 몇 개 없다면 사용
완전 그래프 = 프림 = 정점이 많다면 사용

💡솔린(Sollin) 알고리즘

1. 알고리즘의 개요
   • 단계별로 T에 포함시킬 여러 Edge들을 동시에 선택한다.
   • 각 단계에서 선택된 엣지들은 그래프의 "신장 숲(Spanning Forest)" 구성
   • 초기에는 Edge가 없으므로, forest에 정점 수만큼의 트리가 존재한다.
   • 각 단계에서 forest에 있는 각 트리에 대해 하나의 에지를 선택한다.
     선택 기준 = 최소비용
   • 두 개의 트리에서 동일한 edge를 선택할 수 있으므로, 중복된 Edge를 제거하는 절차가 필요하다.
   • 하나의 트리만 남거나 혹은 추가할 Edge가 없을 경우 종료한다.