크루스칼 알고리즘

출처: www.youtube.com/watch?v=aOhhNFTIeFI&t=1307s

---

<신장 트리>

- 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 의미

    : 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건 == 트리의 조건

 

- 모든 노드가 연결되어 있지만 일부 간선을 사용하지 않아도 괜찮다

 

<최소 신장 트리>

- 최소한의 비용으로 구성되는 신장 트리

    ex) N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우

    : 두 도시 A, B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로 설치

---

<크루스칼 알고리즘>

- 대표적인 최소 신장 트리 알고리즘

- 그리디 알고리즘으로 분류

[동작 과정]

1. 간선 데이터를 비용에 따라 오름차순으로 정렬

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

    1) 사이클 발생 x : 최소 신장트리에 포함 O (union함수)

    2) 사이클 발생 o : 최소 신장트리 포함 x

3. 모든 간선에 대해 2번의 과정 반복

def find_parent(parent, x): #특정 원소가 속한 집합 찾기
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
    
def union_parent(parent, a, b): #두 원소가 속한 집합 찾기
    a = find_parent(a)
    b = find_parent(b)
    if a< b:
        parent[b] = a
    else:
        parent[a] = b
        
 v, e = map(int, input().split())
 parent = [0] * (v+1)
 
 edges = []
 result  = 0
 
 for i in range ( 1, v+1):
     parent[i] = i
     
 for _ in range(e):
     a, b, cost = map(int, input().split())
     edges.append((cost, a, b)) #비용순 정렬을 위해 첫 번째 원소를 비용으로 설정

edges.sort()

for edge in edges: #간선을 하나씩 확인
    cost , a, b = edge
    
    if find_parent(parent, a) != find_parent(parent, b): #사이클이 발생하지 않는 경우에만 집합 포함
        union_parent(parent, a, b)
        result+=cost
        
print(result) #간선 비용의 합

int v, e;
vector<pair<int, pair<int, int>> edges;
int result = 0;

int findParent(int x){
    if(x == parent[x]) return x;
    return parent[x] = findParent(parent[x]);
}

void unionParent(int a, int b){
    a = findParent(a);
    b = findParent(b);
    if (a<b) parent[b] = a;
    else parent[a] = b;
}
int main(){
    for(int i=1 ;i <=v; i++)
        parent[i] = i;
    for(int i=0; i < e; i++){
        int a, b, cost;
        cin >> a>> b>> cost;
        edges.push_back({cost, {a, b}});
    }
    
    sort(edges.begin(), edges.end());
    
    for(int i=0; i < edges.size(); i++){
        int cost = edges[i].first;
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        
        if(findParent(a) != findParnet(b)){ //사이클 발생 x경우만
            unionParent(a, b);
            result += cost;
        }
    }
    cout << result;
}
        
    

[성능 분석]

- 간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가짐

- 가장 많은 시간을 요구하는 곳 => 간선의 정렬을 수행하는 부분

    :표준 라이브러리를 이용해 E개의 데이터를 정렬하기 위한 시간 복잡도는 O(ElogE)