(1197) 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

단계별로 풀어보기

35단계(최소 신장 트리) 2번째

 

 

 

최소 신장 트리를 구하는 알고리즘은 크루스칼 알고리즘과 프림 알고리즘 두 가지가 가장 유명하다.

크루스칼 알고리즘은 모든 간선을 가중치를 기준으로 정렬한 뒤, 간선을 하나씩 살펴보며 간선을 잇는 두 정점이 이미 연결되지 않았다면(주로 유니온 파인드로 구현) 해당 간선으로 그래프를 잇는다. 간선을 정렬하는 과정이 가장 오래 걸리기 때문에 시간 복잡도는 일반적으로 O(E log E)이다.

프림 알고리즘은 임의의 정점을 잡고 이웃한 간선 중에서 가중치가 가장 작은 간선을 뽑아(주로 우선순위 큐로 구현) 연결한 적 없다면 연결하고, 새로 연결된 정점에 연결된 간선도 후보로 넣고 다시 탐색한다. 우선순위 큐로 구현했을 때 각 정점마다 간선을 체크하여 모든 간선을 확인하므로 O(E)가 걸리고, 우선순위 큐의 삽입과 삭제는 O(log V)가 걸리므로 일반적으로 O(E log V)가 걸린다.

 

구현 방법이나 시간 복잡도가 다르므로 문제에 따라 적절한 알고리즘을 선택하는 것이 좋다.

개인적인 경험으로 보면, 일반적으로 MST 문제의 입력은 간선이 정점에 비해 많은 밀집 그래프인 경우가 많으므로 프림 알고리즘이 대개 유리하다. 또 구현 방법을 기준으로 봐도 유니온 파인드를 쓰는 크루스칼보다 우선순위 큐를 쓰고 다익스트라와 유사한 프림 알고리즘이 편한 것 같다.

 

위쪽 코드가 크루스칼, 아래쪽 코드가 프림이다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, pair<int, int>> edge;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, e;
  
  cin >> n >> e;
  
  vector<int> uf(n+1);
  vector<edge> v(e);
  
  for(int i=0;i<e;i++)  cin >> v[i].second.first >> v[i].second.second >> v[i].first;
  
  for(int i=1;i<=n;i++)  uf[i]= i;
  
  sort(v.begin(), v.end());
  
  auto find= [&](auto self, int x) -> int {
    if(uf[x]==x)  return x;
    else  return uf[x]= self(self, uf[x]);
  };
  
  auto merge= [&](int x, int y){
    x= find(find, x);
    y= find(find, y);
    
    if(x==y)  return false;
    
    uf[y]= x;
    
    return true;
  };
  
  int cnt= 1, ans= 0;
  
  for(edge elem:v){
    if(merge(elem.second.first, elem.second.second)){
      cnt++;
      ans+= elem.first;
      
      if(cnt==n)  break;
    }
  }
  
  cout << ans;
  
  return 0;
}

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> p;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int v, e;
  
  cin >> v >> e;
  
  vector adj(v+1, vector<p> ());
  vector<bool> visited(v+1);
  priority_queue<p, vector<p>, greater<p>> pq;
  
  while(e--){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    adj[a].push_back({c,b});
    adj[b].push_back({c,a});
  }
  
  visited[1]= true;
  for(p edge:adj[1])  pq.push(edge);
  
  int cnt= 1, ans= 0;
  
  while(!pq.empty()){
    p now= pq.top();
    pq.pop();
    
    if(visited[now.second])  continue;
    
    visited[now.second]= true;
    cnt++;
    ans+= now.first;
    
    if(cnt==v)  break;
    
    for(p next:adj[now.second]){
      if(visited[next.second])  continue;
      
      pq.push({next.first, next.second});
    }
  }
  
  cout << ans;
  
  return 0;
}