1. 크루스칼 알고리즘

• 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘
• 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘
• 여러개 도시가 있을 때 각 도시를 도로로 연결하기 위한 최소비용을 구할 수 있음

2. 용어 정리

• 노드 = 정점 = 도시: 그래프에서 동그라미에 해당하는 부분
• 간선 = 거리 = 비용: 그래프에서 선에 해당하는 부분

3. 알고리즘

• 간선을 거리가 짧은 순서대로 그래프에 포함
  • 모든 노드를 최소 비용으로 연결 시키면 됨
  • 모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 그래프에 포함
• 사이클이 발생하지 않도록 그래프를 구성
  • Union-Find 사용

4. 자료구조

• 노드 연결 정보와 간선 비용을 하나로 묶음

struct NodeConnect
{
	int sNode;
    int eNode;
    int distance;
}

5. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//부모 노드를 가져옴
int getParent(int set[], int x)
{
	if(set[x] == x) return x;
    return set[x] = getParent(set, set[x])
}

//부모 노드를 병합
void unionParent(int set[], int a, int b)
{
	a = getParent(set, a);
    b = getParent(set, b);
    
    //숫자가 작은 부모로 병합
    if(a<b) set[b] = a;
    else set[a] = b;
}


//같은 부모를 가지는지 확인
int find(int set[], int a, int b)
{
	a = getParent(set, a);
    b = getParnet(set, b);
    if(a == b) return 1;
    return 0;
}

//간선 클래스 선언
class Edge
{
public:
	int node[2];
    int distance;
    Edge(int a, int b, int distance)
    {
    	this->node[0] = a;
        this->node[1] = b;
        this->distance = distance;
    }
    bool operator < (Edge &edge)
    {
    	return this->distance < edge.distance;
    }
}
int main(void)
{
	int n = 7;
    int m = 11;
    vector<Edge> v;
    v.push_back(Edge(1, 7, 12));
    v.push_back(Edge(1, 4, 28));
    v.push_back(Edge(1, 2, 67));
    v.push_back(Edge(1, 5, 17));
    v.push_back(Edge(2, 4, 24));
    v.push_back(Edge(2, 5, 62));
    v.push_back(Edge(3, 5, 20));
    v.push_back(Edge(3, 6, 37));
    v.push_back(Edge(4, 7, 13));
    v.push_back(Edge(5, 6, 45));
    v.push_back(Edge(5, 7, 73));
    
    sort(v.begin(), v.end());
    
    int set[n];
    for(int i=0; i<n; i++)
    	set[i] = i;
    //거리의 합을 0으로 초기화
    int sum = 0;
    for(int i=0; i<v.size(); i++)
    {
    	if(!find(set, v[i].node[0]-1,v[i].node[1]-1))
        {
        	sum += v[i].distance;
            unionParent(set, v[i].node[0]-1, v[i].node[1]-1);
        }
    }
    cout << sum;
}

6. 시간 복잡도

정렬 알고리즘과 동일