본문 바로가기
PS/Algorithm

[알고리즘 개념정리] 11. 분리집합/최소 신장 트리

by 이지이즤 2022. 2. 17.

**본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.**

 

 

분리 집합 (Disjoint Set)

  • 서로 겹치는 원소가 없는 집합들을 관리하는 자료구조
  • 서로소 집합, 유니온-파인드 (Union-Find)
  • 포레스트의 일종
  • Find
    - 주어진 원소가 포함된 집합의 대푯값을 구하는 연산
    - 집합마다 유일한 대푯값 존재
    - 나머지 다른 원소에서 대표로 가는 경로 존재

  • Union
    - 두 집합을 합치는 연산
    - 한 집합의 대푯값을 다른 집합의 대푯값으로 linking

 

int par[1000001], height[1000001];

int find(int num){
    if(num==par[num]) return num; //self roop만났음! 즉, 대푯값 찾았음!
    return par[num] = find(par[num]); //경로압축
}

void unite(int a, int b){
    a=find(a), b=find(b);
    if(height[a] < height[b]) swap(a,b); //높이는 항상 a>=b
    par[b]=a; // 높이 큰 a에 높이 작은 b를 합쳐 (b의 부모가 a)

    if(height[a] == height[b]) //높이가 a==b였다면 a의 높이는 1 증가
        height[a]++;
}
...
// par[i]=i (self roof) 라고 초기화 해준 후, find와 union연산을 해준다.
for(int i=0; i<=n; i++) par[i]=i;

 

  • union 연산을 할 때, 트리를 어떻게 합치는 것이 좋을까?

    (트리 a의 높이) > (트리 b의 높이) 라면, 높은 트리 a에 낮은 트리 b를 합치는 것이 좋다.
    height[a]=3, height[b]=2라고 할 때,
    par[a]=b를 하면 height[a]=4가 되지만 par[b]=a를 하면 height[a]=3으로 유지되기 때문이다.

    (트리 a의 높이) == (트리 b의 높이) 라면,
    par[a]=b를 하든, par[b]=a를 하든 height가 1 증가한다.

  • 시간 복잡도

    2^m개의 노드가 있다고 할 때, union연산을 계속해서 하나의 트리를 만들어 보자.
    높이 1인 트리 2^m개 -> 높이 2인 트리 2^(m-1)개 -> 높이 3인 트리 2^(m-2)개 -> ... -> 높이 m+1인 트리 1개
    여기서 m=log_2_n 이므로, 높은 트리에 낮은 트리를 합치는 방식으로 union했다면
    Union-Find 연산의 시간 복잡도는 O(log_2_n) 이다.

    하지만 트리 형성 시 최악의 경우인, 선형트리가 만들어졌다면 시간 복잡도는 O(n)이다.
    따라서 효율성을 위해 Find과정에서 경로 압축을 할 수 있다.

  • 경로 압축 (Path Compression)
    - Find 연산 시 대푯값을 찾는 과정에서 만나는 경로 상의 모든 원소가 대푯값을 바로 가리키게 한다.
    - 최악의 시간 복잡도 O(n)을 O(1)으로 만들어준다.
     
    int find(int num){
    if(num==par[num]) return num;
    return find(par[num]); //->경로 압축 return par[num] = find(par[num]);
}

 

 

 

 

최소 신장 트리 (Minimum Spanning Tree)

 

신장 트리 (Spanning Tree)

  • 어떤 그래프의 모든 노드와 간선 일부를 포함하며
    모든 노드 간에 경로가 존재하도록 만들어진 부분 그래프 중 트리인 것
  • 방향성 없음
  • 유일하지 않음
  • 신장트리 가중치 : 간선 가중치의 합

 

최소 신장 트리 (Minimun Spanning Tree)

  • 신장 트리 중 가중치가 가장 작은 트리
  • 유일하지 않을 수 있음

 

 

🟪MST를 구하기 위한 알고리즘 두가지!!

1. Kruskal's Algorithm (크루스칼 알고리즘)

  • 탐욕법을 기반으로 간선을  추가해 가면서 MST를 구성하는 방법
  • Tree임을 만족하면서 가중치가 작은 간선을 차례로 추가
    : 간선을 선택하게 될 경우 사이클이 생기는지 판단 후 연결!
vector<pair<int, pii>> adj;
int par[1001], ans;

int find(int num){
    if(num==par[num]) return num;
    return par[num] = find(par[num]); //경로압축
}
void unite(int cost, int a, int b){
    int pa=find(a), pb=find(b);

    if(pa==pb) return; //이미 같은 집합이면 사이클 발생하므로 간선 추가 불가능

    //다른 집합이면 간선 추가 가능
    par[pb]=pa;
    ans+=cost;
}

 

 

2. Prim's Algorithm (프림 알고리즘)

  • 정점을  추가해 가면서 MST를 구성하는 방법
  • 임의의 노드로부터 새 노드와 트리를 연결하는 노드 중 가중치가 가장 작은 간선 선택 (우선순위 큐 사용)
    Single Source Shortest Path 알고리즘 중 Dijkstra's algorithm과 유사
    : visit배열을 이용하여 사이클 체크! 한 번 방문했으면 이미 같은 집합이므로 그 간선은 패스 
int vis[10001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; //{가중치, 노드}
...
pq.push({0,1}); //일단 1번 노드 선택

while(!pq.empty()){
    while(!pq.empty() && vis[pq.top().second]) pq.pop(); //이미 방문했던 노드는 무시
    if(pq.empty()) break;

    int cur=pq.top().second;
    ans+=pq.top().first;
    vis[cur] =1;
    pq.pop();

    for(auto &u:adj[cur]){
        int next=u.first, cost=u.second;
        if(!vis[next]) pq.push({cost, next});
    }
}

 

 

 

 

관련 문제

 

'PS > Algorithm' 카테고리의 다른 글

[알고리즘 개념정리] 10. 최단경로 알고리즘  (0) 2022.02.14
[알고리즘 개념정리] 9. 트리  (0) 2022.02.09
[알고리즘 개념정리] 8. 그래프/그래프 탐색  (5) 2022.02.05
[알고리즘 개념정리] 7. 이분탐색/분할정복  (0) 2022.02.02
[알고리즘 개념정리] 6. 완전탐색/백트래킹  (0) 2022.01.29

관련글

댓글

티스토리툴바