최소 신장 트리

최소 신장 트리란 그래프에서 모든 노드를 연결할 때

사용된 에지들의 가중치의 합을 "최소"로 하는 트리.

 

특징

1. 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 

사이클을 포함하지 않는다.

2. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 

항상 N - 1개다.

 

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화

에지 리스트는 노드 변수 2개와 가중치 변수로 구성

사이클 처리를 위한 유니온 파인드 배열

배열의 인덱스를 해당 자리의 값으로 초기화

 

2. 그래프 데이터를 가중치 기준으로 정렬

에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬

 

에지 리스트의 객체를 구조체로 표현하면

operator() 함수를 이용해 정렬을 수행 가능

 

3. 가중치가 낮은 에지부터 연결 시도

바로 연결하는 것이 아닌 에지를 연결 했을 때 그래프에

사이클이 형성 되는지 find 연산을 이용해 확인하고

사이클이 형성 되지 않을 때만 union 연산을 이용해 두 노드를 연결

 

4. 과정 3 반복

연결한 에지의 개수가 N - 1이 될 때까지 과정 3을 반복

 

5. 총 에지 비용 출력

에지의 개수가 N - 1이 되면 알고리즘 종료

완성된 최소 신장 트리의 총 에지 비용 출력

 

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

1197번: 최소 스패닝 트리

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
vector<int> parent;
 
int find(int a)
{
    if (a == parent[a])
        return a;
    else
        return parent[a] = find(parent[a]);
}
 
void munion(int a, int b)
{
    a = find(a);
    b = find(b);
 
    if (a != b)
    {
        parent[b] = a;
    }
}
 
 
// 에지 정보 구조체 생성
// 가중치 값 기준 오름차순 정렬
typedef struct edge {
    int s, e, v;
    bool operator > (const edge& tmp) const {
        return v > tmp.v;
    }
} edge;
 
int main()
{
    int n, m;
    cin >> n >> m;
    priority_queue<edge, vector<edge>, greater<edge>> pq;
    parent.resize(n + 1);
 
    for (int i = 0; i <= n; i++)
        parent[i] = i;
 
    for (int i = 0; i < m; i++)
    {
        int s, e, v;
        cin >> s >> e >> v;
        pq.push(edge{ s,e,v });
    }
 
    int used = 0;
    int ans = 0;
 
    while (used < n - 1)
    {
        edge now = pq.top();
        pq.pop();
 
        // 같은 부모가 아니라면 (사이클 형성 x)
        if (find(now.s) != find(now.e))
        {
            munion(now.s, now.e);
            ans = ans + now.v;
            used++;
        }
    }
    
    cout << ans << '\n';
 
    return 0;
}