[C++] MST 구현

자세한 이론은 이전 글 참고!

https://qqs-diary.tistory.com/106

MST (Minimum Spanning Tree)

 

이론 정리글에서 사용했던 그래프를 이용해서 코드로 구현해보자.

이 그래프를 MST로 만들면 

총 가중치는 1+2+3+3+3+4+5 = 21이 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#define SZ 8
using namespace std;

int getparent(int cycle[], int x)
{//cycledetection 배열에서 부모가 누군지 가져옴
    if(cycle[x]==x) return x;
    return cycle[x] = getparent(cycle,cycle[x]);
}

void unionparent(int cycle[],int a, int b)
{//연결되었다는 의미로 부모를 같게 해준다.
    a=getparent(cycle,a);
    b=getparent(cycle,b);
    //숫자가 앞서는 부모를 기준으로 연결
    if(a<b) cycle[b]=a;
    else cycle[a]=b;
}

int find(int cycle[], int a, int b)
{//부모가 같은지 확인
    a=getparent(cycle, a);
    b=getparent(cycle, b);
    if(a==b) return 1;
    else return 0;
}

class Edge
{
public:
    int vertex[2];
    int weight;
    Edge(int a, int b, int weight)
    {
        this->vertex[0]=a;
        this->vertex[1]=b;
        this->weight=weight;
    }
    bool operator <(Edge &edge)
    {
        return this->weight < edge.weight;
    }
};

int main()
{
    vector<Edge> v;
    v.push_back(Edge(1,2,8));
    v.push_back(Edge(1,6,10));
    v.push_back(Edge(1,8,5));
    v.push_back(Edge(2,6,4));
    v.push_back(Edge(2,3,4));
    v.push_back(Edge(2,8,4));
    v.push_back(Edge(2,5,4));
    v.push_back(Edge(3,6,3));
    v.push_back(Edge(3,4,3));
    v.push_back(Edge(4,5,1));
    v.push_back(Edge(4,6,6));
    v.push_back(Edge(4,7,2));
    v.push_back(Edge(5,7,3));
    v.push_back(Edge(7,8,3));

    sort(v.begin(),v.end());

    int cycledetection[SZ];
    for(int i=0; i<SZ; i++) cycledetection[i]=i;

    int sum=0;//최종 가중치 저장
    for(int i=0; i<v.size(); i++)
    {
        if(!find(cycledetection,v[i].vertex[0]-1,v[i].vertex[1]-1))
        {
            sum+=v[i].weight;
            unionparent(cycledetection,v[i].vertex[0]-1,v[i].vertex[1]-1);
        }
    }

    cout<<"weight is : "<<sum;
}

결과

코드 구현 결과도 21이 나옴을 알 수 있다.