Algorithm(Kruskal)

rxjw95·2020년 4월 29일
0

알고리즘

목록 보기
3/10

Kruskal 알고리즘이란?

탐욕적인 방법(greedy)을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 신장 트리를 구하는 것

신장 트리 : 모든 정점들만을 사이클이 없이 간선으로 연결한 그래프
최소 신장 트리 : 모든 정점들을 사이클이 없는 최소 비용의 간선으로 연결한 그래프

특징은?

크루스칼 알고리즘은 모든 간선 정보를 사전에 파악 후 가장 적은 비용의 간선부터 연결합니다.
그리고 사이클이 발생하는 것을 방지하기 위해 union-find 방식을 추가적으로 사용 합니다.
탐색 비용이 크다는 단점이 있습니다.

신장트리를 만들게 되면 정점의 수 -1 = 간선의 수

시간복잡도는?

가장 적은 비용의 간선으로 정렬하기 위한 정렬 시간 - E*log(E)

Flow

그래프의 간선들을 가중치의 오름차순으로 정렬한다.
정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
즉, 가장 낮은 가중치를 먼저 선택한다.
사이클을 형성하는 간선을 제외한다.
해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.

Pratice code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;
int parent[1001]; //각 정점의 부모를 저장한다.
vector<pair<int, pair<int, int>>> adj; //연결 정보

//부모를 찾는  함수
int Find_Parent(int v) {
    if (parent[v] == v) return v;
    else return Find_Parent(parent[v]); //노드 v의 부모 노드의 부모를 계속 찾아나간다.
}

//같은 부모를 갖는지 판단해주는 함수
bool SameParent(int v1, int v2){    

    v1 = Find_Parent(v1);        // 노드 v1의 부모 찾기    
    v2 = Find_Parent(v2);        // 노드 v2의 부모 찾기

    if (v1 == v2) return true; 
    else return false;         
}



//3. 서로 다른 부모일 경우, 두 개의 노드를 연결해주는 union 함수
void Union(int v1, int v2) {     // 노드 x와 y를 합쳐주는 함수
    v1 = Find_Parent(v1);    // 먼저 x의 부모를 찾고
    v2 = Find_Parent(v2);    // y의 부모를 찾아준다.

    // 만약 두 노드의 부모가 서로 다르다면
    // 한쪽 노드의 부모를 다른 한쪽 노드로 설정
    if (v1 != v2)    parent[v2] = v1;
}


int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int sv, ev, w;  cin >> sv >> ev >> w;
        adj.push_back(make_pair(w, make_pair(sv, ev)));
    }

    int ans = 0;

    sort(adj.begin(), adj.end());  //가중치 기준으로 오름차순 정렬

    for (int i = 1; i <= N; i++) parent[i] = i; //초기의 각 정점의 부모 노드는 자기 자신

    for (int i = 0; i < adj.size(); i++) { //작은 가중치들부터 연결을 시작
        if (SameParent(adj[i].second.first, adj[i].second.second) == false) {
            Union(adj[i].second.first, adj[i].second.second);
            ans += adj[i].first;
        }
    }

    //최소 비용 출력
    cout << ans << endl;

    return 0;
}
profile
겉만 핥는 호구🤗

0개의 댓글