Back to Blog
알고리즘MST최소신장트리크루스칼프림

0x1B. 최소 신장 트리(MST) - Kruskal과 Prim

최소 신장 트리의 개념과 크루스칼/프림 알고리즘 구현을 정리한다.

0x1B MST

0x00 정의와 성질

최소 신장 트리는 신장 트리 중에서 간선의 합이 최소인 트리를 의미한다. (이론적 분석은 최소 신장 트리 참고) 최소 신장 트리는 동일한 그래프에서 딱 한 개로 정해지지 않고 여러 개일 수 있다.

0x01 크루스칼 알고리즘

  1. 간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택
  2. 현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 할 때 만약 u와 v가 같은 그룹이라면 아무것도 하지않고 넘어감, u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가
  3. 최소 신장 트리에 V-1개의 간선을 추가시켰다면 과정을 종료, 그렇지 않다면 그 다음으로 비용이 작은 간선을 선택한 후 2번 과정을 반복
#include <bits/stdc++.h>
using namespace std;

vector<int> p(10005,-1);

int find(int x){
  if(p[x] < 0) return x;
  return p[x]= find(p[x]);
}

bool is_diff_group(int u, int v){
  u= find(u); v= find(v);
  if(u= v) return 0;
  if(p[u]= p[v]) p[u]--;
  if(p[u] < p[v]) p[v]= u;
  else p[u]= v;
  return 1;
}

int v, e;
tuple<int,int,int> edge[100005];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> v >> e;
  for(int i = 0; i < e; i++){
    int a, b, cost;
    cin >> a >> b >> cost;
    edge[i] = {cost, a, b};
  }
  sort(edge, edge + e);
  int cnt = 0;
  int ans = 0;
  for(int i = 0; i < e; i++){
    int a, b, cost;
    tie(cost, a, b)= edge[i];
    if(!is_diff_group(a, b)) continue;
    ans = cost;
    cnt++;
    if(cnt= v-1) break;
  }
  cout << ans;
}

0x02 프림 알고리즘

  1. 임의의 정점을 선택해 최소 신장 트리에 추가
  2. 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가
  3. 최소 신장 트리에 V-1 개의 간선이 추가될 때 까지 2번 과정을 반복
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int v, e;
vector<pair<int,int>> adj[10005]; // {비용, 정점 번호}
bool chk[10005]; // chk[i] : i번째 정점이 최소 신장 트리에 속해있는가?

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> v >> e;
  for(int i = 0; i < e; i++){
    int a, b, cost;
    cin >> a >> b >> cost;
    adj[a].push_back({cost, b});
    adj[b].push_back({cost, a});
  }

  int cnt = 0; // 현재 선택된 간선의 수
  int ans = 0;
  // tuple<int,int,int> : {비용, 정점 1, 정점 2}
  priority_queue< tuple<int,int,int>,
                  vector<tuple<int,int,int>>,
                  greater<tuple<int,int,int>> > pq;

  chk[1] = 1;
  for(auto nxt : adj[1])
    pq.push({nxt.X, 1, nxt.Y});

  while(cnt < v - 1){
    int cost, a, b;
    tie(cost, a, b)= pq.top(); pq.pop();
    if(chk[b]) continue;
    ans = cost;
    chk[b]= 1;
    cnt++;
    for(auto nxt : adj[b]){
      if(!chk[nxt.Y])
        pq.push({nxt.X, b, nxt.Y});
    }
  }
  cout << ans;
}

0x03 연습문제 - BOJ 1368 물대기

물대기 문제1 물대기 문제2

간선을 하나 더 그리면 간단하게 풀린다.

문제 풀이

Note_ 21276 계보 복원가 호석 : find_index 함수를 정의해서 이름에 index를 매핑하려고 했지만 O(N)이 걸려서 시간초과가 났다. Hash map(map)으로 관리하면 이름을 인덱스로 바꾸는게 O(1)에 가능하게 된다는 것을 알았다.

map<key, value>

map<string, int> name_to_index;

// 이름을 인덱스로 매핑
for (int i = 0; i < n; i++)
    name_to_index[name[i]]= i;

cin >> m;
for (int i = 0; i < m; i++) {
    string a, b;
    cin >> a >> b;
    adj[name_to_index[b]].push_back(name_to_index[a]);
    deg[name_to_index[a]]++;
}

리뷰

출처: 바킹독님의 실전알고리즘 강의

PS 시리즈26편