[C++] Kruskal MST 알고리즘(Greedy, Union & Find 활용) - 원더랜드

모든 노드를 최소비용으로 방문하는 알고리즘으로, 간선을 정렬하는 방식

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int unf[10001];

struct Edge{
    int v1;
    int v2;
    int val;
    Edge(int a, int b, int c){
        v1 = a;
        v2 = b;
        val = c;
    }
    
    bool operator<(const Edge &ref)const{ //kruskal MST는 간선을 정렬함
        return val < ref.val;
    }
};

int Find(int v){
    if(v==unf[v]) return v;
    else return unf[v] = Find(unf[v]);
}

void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    if(a!=b) unf[a] = b;
}

int main() {
    vector<Edge> Ed;
    int i,n,m,a,b,c,cnt=0,res=0;
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i++){ //각 노드들에게 집합 번호를 부여한다.
        unf[i] = i;
    }
    
    for(int i = 1; i <= m; i++){//트리구조 만들어냄, 집합 묶음
        scanf("%d %d %d",&a, &b, &c);
        Ed.push_back(Edge(a,b,c));
    }
    sort(Ed.begin(), Ed.end());
    
    for (i = 0; i < m; i++) {
        int fa = Find(Ed[i].v1);//해당 노드의 집합 번호
        int fb = Find(Ed[i].v2);
        if(fa != fb){ // 같지 않으면 Cycle이 돌지 않으므로
            res += Ed[i].val; // 최소비용에 누적
            Union(Ed[i].v1,Ed[i].v2); //집합 연결시켜주기
        }
    }
    printf("%d",res);
    return 0;
}

• Kruskal MST는 모든 노드를 최소비용으로 방문하는 알고리즘이다.
• 특징이라면 간선을 비용에 따라 정렬한다는 것이다.
• 그리고 Cycle을 없애기 위해 Union&Find를 활용한다.

 

1. 각 노드에 집합 번호를 부여한다.

   for(int i = 1; i <= n; i++){ //각 노드들에게 집합 번호를 부여한다.
       unf[i] = i;
   }​

    
2.  Vector를 이용해 각 노드의 연결 정보를 저장한다(트리를 만든다.)

   for(int i = 1; i <= m; i++){//트리구조 만들어냄, 집합 묶음
       scanf("%d %d %d",&a, &b, &c);
       Ed.push_back(Edge(a,b,c));
   }​

3. Edge 구조체에는 Operator가 정의되어 있어 Sort함수로 벡터를 저렬하면 간선에 대한 오름차순으로 정렬된다.

   struct Edge{
       int v1;
       int v2;
       int val;
       Edge(int a, int b, int c){
           v1 = a;
           v2 = b;
           val = c;
       }
       
       bool operator<(const Edge &ref)const{ //kruskal MST는 간선을 정렬함
           return val < ref.val;
       }
   };
   
   Sort(Ed.begin(), Ed.end());​

4. 그럼 벡터에는 간선의 비용이 가장 작은 노드와 노드간의 연결 정보가 오름차순으로 담겨있을 것이다.

   

5.  벡터에 담긴 순서대로 모든 도시를 연결(Union)해보면 어떻게 될까? Ed[4]에서 Cycle이 발생한다.

   

6. 따라서 Union & Find를 이용해서 각 노드가 같은 집합에 포함된다면 연결(Union)하지 않도록 한다.
   • 이렇게되면 결국 ED[4]에서 fa가 3 fb가 3으로 나와서 연결되지 않는다.

for (i = 0; i < m; i++) { //벡터 순서대로 연결할건데
     int fa = Find(Ed[i].v1);//v1의 집합 번호와
     int fb = Find(Ed[i].v2);//v2의 집합 번호가
     if(fa != fb){ // 같지 않으면 Cycle이 돌지 않으므로
        res += Ed[i].val; // 최소비용에 누적
        Union(Ed[i].v1,Ed[i].v2); //연결할 것이다
  	}
}

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard