Minimum Spanning Tree (MST) - Kruskal

크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기

모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다.

 

• 유니온 파인드(Union-Find)에 대한 이해 8할
• Edge 구조체 설계 2할?

---

find_topnode() 를 통해서 현재 정점(Vertax)의 최상단 노드(부모노드) 를 알 수 있다.

Node[Vertax]의 값이 음수이면 Vertax가 부모노드임을 의미한다

 

is_cycle()을 통해서 a와 b 정점이 서로 같은 노드인지 확인한다(find_topnode() 사용)

 

Union_node()를 통해서 a 와 b정점을 하나로 병합한다

a, b정점의 부모 노드가 가지는 값은 항상 음수이다.

값이 더 작을수록 더 많은 자식노드를 가지고 있는 것이므로 값이 작은쪽에 다른 노드의 값(음수)을 더해주고

반대편에는 값이 작은 노드의 정점번호를 넣어줘서 둘을 이어준다

글 진짜 못적네

 

Union Find Basic Code C++

 

// ------------------------------------------------------------------
//      최소 스패닝 트리
//      pseudo code
//      아래 사이트의 구현방식을 따름
//      https://www.cs.usfca.edu/~galles/visualization/Kruskal.html
//
//      2021/05/09
// ------------------------------------------------------------------
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
struct Line{
    int st;
    int ed;
    long long value;
};
 
int V, E;
long long result = 0;
int Node[10001];
vector<Line> Edge;
 
bool compare(Line &a, Line &b){
    return a.value < b.value;
}
 
int find_topnode(int a){
    if(Node[a] < 0) return a;
    return find_topnode(Node[a]);
}
 
bool is_cycle(int a, int b){
    a = find_topnode(a);
    b = find_topnode(b);
    if(a == b) return true;
    else return false;
}
 
void Union_node(int a, int b){
    a = find_topnode(a);
    b = find_topnode(b);
    if(Node[a] > Node[b]){
        Node[b] += Node[a];
        Node[a] = b;
    }
    else{
        Node[a] += Node[b];
        Node[b] = a;
    }
}
 
void solve(){
    int va, vb, cnt = 0;
    for(int i = 0; i < Edge.size(); i++){
        if(cnt == V-1) break;
        va = Edge[i].st;
        vb = Edge[i].ed;
        if(!is_cycle(va, vb)){
            Union_node(va, vb);
            result += Edge[i].value;
            cnt++;
        }
    }
    cout << result;
}
 
void init(){
    // test 1
    // 7 12
    // 1 2 3
    // 1 3 2
    // 3 2 1
    // 2 5 2
    // 3 4 4
    // 7 3 6
    // 5 1 5
    // 1 6 2
    // 6 4 1
    // 6 5 3
    // 4 5 3
    // 6 7 4
    // ans = 12
    
    int a, b, c;
    cin >> V >> E;
    for(int i = 0; i < E; i++){
        cin >> a >> b >> c;
        Edge.push_back({a, b, c});
    }
    sort(Edge.begin(), Edge.end(), compare);
    memset(Node, -1, sizeof(Node));
}
 
int main(){
    init();
    solve();
    
    return 0;
}

Kruskal MST Visualzation

위 사이트에서 그래프를 여러번 돌려보며 구현했다