MST - Prim 알고리즘

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

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

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

 

typedef pair<int, int> pii;

bool visit[10001] = { false };
vector<pii> adj[10001];
int v, e;

struct cmp {
    bool operator()(pii a, pii b) {
        return a.second > b.second;
    }
};

int prim(int start) {
    priority_queue<pii, vector<pii>, cmp> pq;
    int ret = 0;
    int joined = 0;
    pii cur, connect;
    pq.push({ start, 0 });

    while (joined < v) {
        cur = pq.top();
        pq.pop();
        if (visit[cur.first]) continue;
        visit[cur.first] = true;
        joined++;
        ret += cur.second;
        for (int i = 0; i < adj[cur.first].size(); i++) {
            connect = adj[cur.first][i];
            if (!visit[connect.first]) pq.push(connect);
        }
    }
    return ret;
}