개념

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘으로 흔히 여러개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소로 하기 위해 실제로 적용되는 알고리즘이다.

노드 = 정점 = 도시

간선 = 거리 = 비용

일단 모든 노드를 최대한 적은 비용으로 연결 시켜야하기 때문에 간선 정보를 오름차순으로 정렬 한 후 비용이 적은 간선부터 차근차근 그래프에 포함시킨다. 단 이때 사이클을 형성하게 될 경우 간선을 포함하지 않는다.

조건

1. 간선 정보를 오름차순으로 정렬
2. 사이클이 형성되지 않게 연결

사용하기 좋은 경우

1. 모든 노드를 최소 비용으로 연결할 경우
2. 연결되어있는 그룹의 수를 구하는 경우 → 크루스칼 알고리즘으로 다 연결 한 후 최상단 부모의 개수가 그룹의 수이다.

구현 방법

1. 비용, 출발, 도착의 정보를 갖는 노드들을 비용을 기준으로 오름차순 정렬하기

typedef pair<int, int> pii;
for(int i = 0; i < m; i++) { //a: 출발지점, b: 도착지점, c: 비용
        scanf("%d%d%d", &a, &b, &c);
        v.push_back(pair<int, pii>(c, pii(a,b)));
    }
    int p = 0;
    sort(v.begin(), v.end()); //비용 기준으로 정렬