신장트리, 크루스칼 알고리즘

신장트리는 그래프에서 자주보이는 유형이다.

 

신장트리란, 하나의 그래프가있을때 모든 노드를 포함하면서 사이클을 발생 시키지 않는 부분그래프를 뜻한다.

 

그래프에서 사이클이 발생하지 않는 부분그래프 (빨간선)

 

이처럼 신장트리에서 최소 비용으로 만들어진 신장트리를 '최소비용 신장트리' 리고하는데

 

이 신장트리를 구하는 대표적인 방법은 크루스칼 알고리즘이 있다.

 

크루스칼 알고리즘의 동작순서는 다음과 같다.

 

1. 간선데이터의 비용을 크기에 따라 오름 차순 정렬한다.

2. 간선을 하나씩확인하며 사이클을 발생 시키는지 확인한다.

      1. 사이클이 발생하지 않는다면 최소비용 신장트리에 포함시킨다.

      2. 사이클이 발생하는 경우 포함하지 않는다.

3. 모든 간선에 대하여 2 번의 과정을 반복한다.

 

다음은 크루스칼 알고리즘의 코드이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int V ,E ; // 노드의 갯수 , 간선의 갯수 
int parent[100001]; // 사이클 검사를 위한 부모노드 
int ans=0;
vector < pair < int , pair <int ,int>> > edge;

void init(){
    for(int i = 1 ;i <= V ;i++){ // 모든 노드들의 부모를 자기 자신으로 설정한다.
        parent[i] = i;
    }
    sort(edge.begin() ,edge.end()); // 간선들의 비용을 오름차순 정렬한다.
}
int findParent(int v){ // 재귀를 통하여 부모 탐색
    if(v == parent[v]) return v;
    return  parent[v] = findParent(parent[v]);

}
void unionParent(int v1 , int v2){
    int v1_p = findParent(v1);
    int v2_p = findParent(v2);

    if(v1_p < v2_p){
        parent[v2_p] = v1_p;
    }
    else{
        parent[v1_p] = v2_p;
    }
}
int main(){
    cin >> V >> E; // 노드의 
    for(int i =0 ; i < E ; i++){
        int v1, v2, cost;
        cin >> v1 >> v2 >> cost;
        edge.push_back({cost,{v1 ,v2} });  
    }
    init();

    for(int i = 0 ; i < edge.size() ; i++){
        int v1, v2, cost;
        cost = edge[i].first;
        v1 = edge[i].second.first;
        v2 = edge[i].second.second;

        if (findParent(v1) != findParent(v2)) {
            unionParent(v1, v2);
            ans += cost;
        }
    }
    cout << ans ; // 최소비용 출력
    return 0;
}

 

크루스칼 알고리즘은 간선의 개수가 E 개 일 때, O (ElogE)의 시간 복잡도를 가진다.