[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리

문제 정의

• 모든 노드가 연결되어 있는 상태를 만들기 위해 최소한으로 필요한 비용을 구하는 문제

문제 접근

• Kruscal
  • 가장 작은 간선 순으로 추가하는 방식
  • 기존에 추가된 노드를 추가하면 안되니까, 기존에 이미 추가되었던 간선이라면 추가하지 않음
  • 기존에 추가된 간선인지 확인하는 방법은 Union-Find로 결정
    • Union Find
      • 두개의 노드가 같은 그룹에 있는지 확인하는 방법
      • 모든 노드의 부모를 찾는 배열을 설정 후 모두 -1로 초기화 시킨다음
      • 간선을 추가할때마다 두 노드를 비교한 후, 부모가 같지 않으면 두 노드중 하나를 부모로 결정
      • 위 과정을 반복
  • 총 추가한 노드의 개수가 N개가 되면 종료

• Prim

  • 현재 추가된 노드를 기준으로, 주변에 있는 간선 중 작은 간선부터 추가하는 방식
  • 처음에 한점을 잡고 인접한 간선을 모두 우선순위 큐에 추가
  • 우선순위 큐에서 하나씩 꺼냄
  • 꺼낸 후 이미 선택되었던 노드인지 확인
  • 선택되었던 노드아니라면, 노드의 주변에 있는 간선을 우선순위 큐에 추가
  • 총 추가한 노드의 개수가 N개가 되면 종료

시간복잡도

• Kruscal
  • 모든 간선 정렬 : ElgE
  • V개의 노드 : V
  • E개의 간선 : E
  • 총 시간복잡도 : O(ElgE + V + E) = O(ElgE)
• Prim
  • 모든 간선 우선순위 큐에 삽입 및 자동 정렬 : ElgE
  • V개의 노드 : V
  • E개의 간선 : E
  • 총 시간복잡도 : O(ElgE + V + E) = O(ElgE)

대표예제 : 백준 1197 최소 스패닝 트리

• Kruscal

  #include <iostream>
  #include <tuple>
  #include <algorithm>
   
  using namespace std;
  typedef tuple<int, int, int> ti3;
   
  int p[10010];
  ti3 edge[100010];
   
  int find(int v) {
      if(p[v] < 0) return v;
      return p[v] = find(p[v]);
  }
   
  // union find
  bool is_diff_group(int v1, int v2) {
      // 각 부모노드를 찾음
      v1 = find(v1); v2 = find(v2);
      
      // 부모가 같은 노드라면 종료
      if(v1==v2) return 0;
      
      if(p[v1] == p[v2]) p[v1]--;
      if(p[v1] < p[v2]) p[v2] =v1;
      else p[v1] = v2;
      return 1;
      
      
  }
   
  int main() {
      ios::sync_with_stdio(0);
      cin.tie(0);
      
      int V,E; cin >> V >> E;
      fill(p, p+10010, -1);
      
      // E개의 간선 추가
      for(int i=0; i<E; i++) {
          int a,b,c; cin >> a >> b >> c;
          edge[i] = {c,a,b};
      }
      sort(edge, edge+E);
      
      int cnt=1;
      int ans=0;
      for(int i=0; i<E; i++) {
          int a,b,c; tie(c,a,b) = edge[i];
          
          // 둘이 같은 그룹이라면 건너뜀
          if(!is_diff_group(a,b)) continue;
          
          // 다른그룹이라면
          cnt++;
          ans+=c;
          
          // 모든 노드 추가되면 종료
          if(cnt == V) break;
          
      }
      
      cout << ans << '\n';
      
      
      
      return 0;
  }
   

• Prim

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<pair<int, int>> adj[10010];
bool chk[10010];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E; cin >> V >> E;
    
    fill(chk, chk+10010, false);
    
    for(int i=0; i<E; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
        adj[b].push_back(make_pair(c,a));
    }
    
    // 한 간선에 대해서 인접한 간선 모두 추가
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(auto x : adj[1]) {
        pq.push(x);
    }
    chk[1] = 1;
    
    int cnt=1;
    int ans=0;
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        if(chk[ei] == true) continue;
        chk[ei] = true;
        cnt++;
        ans += ec;
        
        // 모든 노드 추가되면 종료
        if(cnt== V) break;
        
        // 인접한 간선 추가
        for(auto nq : adj[ei]) {
            int nc = nq.first;
            int ni = nq.second;
            if(chk[ni] == true)continue;
            pq.push(nq);
        }
        
    }
    
    cout << ans << '\n';
    
    return 0;
}