[c++]크루스칼 알고리즘(kruskal)

#include <iostream>
#include <algorithm>
#include <vector>
//C++ STL 사용
using namespace std;
typedef pair<int, int> iPair;
 
struct DisjointSets // Disjoint Sets은 집합을 트리로 형성하여 그래프의 Cycle을 형성하는지 체크.
{
    int *parent, *rnk;
    int n;
 
    DisjointSets(int n) // 생성자
    {
        this->n = n;
        parent = new int[n + 1];
        rnk = new int[n + 1];
 
        for (int i = 0; i <= n; i++)
        {
            rnk[i] = 0;
            parent[i] = i;
        }
    }
 
    int find(int u) // 같은 부모를 가지는 지 확인하는 함수
    {
        if (u != parent[u])
            parent[u] = find(parent[u]);
        return parent[u];
    }
 
    void unionmerge(int x, int y) // 부모 노드를 병합
    {
        x = find(x), y = find(y);
 
        if (rnk[x] > rnk[y]) // 더 작은 숫자를 부모에 병합 
            parent[y] = x;
        else // If rnk[x] <= rnk[y]
            parent[x] = y;
 
        if (rnk[x] == rnk[y])
            rnk[y]++;
    }
};
 
struct Graph
{
    int V, E;
    vector< pair<int, iPair> > edges;
 
    Graph(int V, int E) // 생성자
    {
        this->V = V;
        this->E = E;
    }
    
    void addEdge(int u, int v, int w) // init_set() 과 같은 함수, 정점을 추가한다.
    {
        edges.push_back({ w,{ u, v } });
    }
 
    int kruskalMST();
};
 
int Graph::kruskalMST()
{
    int mst_wt = 0; // 초기값은 0
 
    sort(edges.begin(), edges.end()); // 오름차순 정렬
 
    DisjointSets DS(V);
 
    vector< pair<int, iPair> >::iterator it;
    for (it = edges.begin(); it != edges.end(); it++)
    {
        int u = it->second.first;
        int v = it->second.second;
 
        int set_u = DS.find(u);
        int set_v = DS.find(v);
 
        // 동일한 부모를 가르키지 않는 경우, 즉 사이클이 발생하지 않을 때만 선택.
        if (set_u != set_v)
        {
            cout << u << " - " << v << endl; // 결과 값 출력
            mst_wt += it->first;
            DS.unionmerge(set_u, set_v); //DisjointSets의 unionmerge 함수
        }
    }
    return mst_wt;
}
 
 
 
int main()
{
    int V = 9, E = 14; //정점, 간선의 수
    Graph kruskal(V, E);
 
    // edge 추가
    kruskal.addEdge(0, 1, 4);
    kruskal.addEdge(0, 7, 8);
    kruskal.addEdge(1, 2, 8);
    kruskal.addEdge(1, 7, 11);
    kruskal.addEdge(2, 3, 7);
    kruskal.addEdge(2, 5, 4);
    kruskal.addEdge(2, 8, 2);
    kruskal.addEdge(3, 4, 9);
    kruskal.addEdge(3, 5, 14);
    kruskal.addEdge(4, 5, 10);
    kruskal.addEdge(5, 6, 2);
    kruskal.addEdge(6, 7, 1);
    kruskal.addEdge(6, 8, 6);
    kruskal.addEdge(7, 8, 7);
 
    cout << "MST의 연결된 정점\n";
    int mst_wt = kruskal.kruskalMST(); //
 
    cout << "\nMST 비용은 " << mst_wt << "입니다." << endl;
 
    return 0;
}

크루스칼알고리즘.hwp

kruskal.cpp