MST - Kruskal 알고리즘

Kruskal 알고리즘의 시간복잡도 = O(E logE)

Prim 알고리즘의 시간복잡도 = O(E logV)

즉, 간선이 많다면 Prim을, 그렇지 않다면 Kruskal을 쓰는 것이 효율적이다.

 

//유니온-파인드가 구현된 상태여야 함.

'알고리즘 공부/Disjoint-set(유니온-파인드)' 카테고리의 글 목록

 

typedef struct _elem {
    int a, b, w;
} elem;

struct cmp {
    bool operator()(elem a, elem b) {
        return a.w > b.w;
    }
};

 

priority_queue<elem, vector<elem>, cmp> pq;
int v, e;
int parent[10001];
int depth[10001];

 

int kruskal() {
    int ret = 0;
    int joined = 0;
    elem cur;
    while (joined < v - 1) {
        cur = pq.top();
        pq.pop();
        if (findSet(cur.a) == findSet(cur.b)) continue;
        else {
            unionSet(cur.a, cur.b);
            joined++;
            ret += cur.w;
        }
    }
    return ret;
}

 

int main {

    ...

    for (int i = 1; i <= v; i++) {
        depth[i] = 1;
        parent[i] = i;

    }
    for (int i = 0; i < e; i++) {
        cin >> a >> b >> c;
        pq.push(elem{ a, b, c });
    }

    ...

}