크루스칼,프림 알고리즘 C++ 코드

1. 크루스칼(Kruskal) 

• 그래프 표현: 보통 간선 리스트 형태로 가지고 있습니다.
• 핵심:
  1. 모든 간선을 비용 기준으로 오름차순 정렬
  2. 유니온 파인드(Union-Find)로 사이클 확인
  3. 비용이 작은 간선부터 차례대로 MST에 추가

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;        // 간선을 잇는 두 정점
    long long cost;  // 간선의 가중치
};

// 전역 혹은 클래스 내 Union-Find
static const int MAXN = 100000; // 정점 최대 개수 예시 (원하는 만큼)
int parentSet[MAXN];
int rankSet[MAXN];

// Union-Find find 함수(경로 압축)
int Find(int x) {
    if (parentSet[x] == x) return x;
    return parentSet[x] = Find(parentSet[x]);
}

// Union-Find union 함수(Union by rank)
void Union(int a, int b) {
    int rootA = Find(a);
    int rootB = Find(b);
    if (rootA == rootB) return; // 이미 같은 집합이면 종료

    if (rankSet[rootA] < rankSet[rootB]) {
        parentSet[rootA] = rootB;
    } else if (rankSet[rootA] > rankSet[rootB]) {
        parentSet[rootB] = rootA;
    } else {
        parentSet[rootB] = rootA;
        rankSet[rootA]++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 예시: 정점 개수 N, 간선 개수 E
    int N, E;
    cin >> N >> E;

    // Union-Find 초기화
    for (int i = 0; i < N; i++) {
        parentSet[i] = i;
        rankSet[i] = 0;
    }

    vector<Edge> edges;
    edges.reserve(E);

    // 간선 입력
    for (int i = 0; i < E; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;  // 예: 0-based 또는 1-based 확인 필요
        // 만약 1-based라면 u--, v-- 처리
        edges.push_back({u, v, w});
    }

    // 1) 비용 기준으로 오름차순 정렬
    sort(edges.begin(), edges.end(), [](auto &a, auto &b){
        return a.cost < b.cost;
    });

    long long mstCost = 0;
    int usedEdges = 0; // MST에 사용된 간선 수

    // 2) 크루스칼
    for (auto &edge : edges) {
        // Find로 확인
        if (Find(edge.u) != Find(edge.v)) {
            Union(edge.u, edge.v);
            mstCost += edge.cost;
            usedEdges++;
            if (usedEdges == N - 1) break; // MST 완성
        }
    }

    // MST 비용 출력 (예시)
    cout << mstCost << "\n";

    return 0;
}

 

2. 프림(Prim) 알고리즘 베이스 코드

• 그래프 표현: 일반적으로 인접 리스트를 사용합니다.
• 핵심:
  1. 임의의 시작 정점을 MST에 포함
  2. 현재 MST와 연결 가능한 모든 간선을 우선순위 큐(최소 힙)에 넣고,
  3. 비용이 가장 낮은 간선부터 확장 (새로운 정점이 MST에 들어올 때, 그 정점과 연결된 간선들도 큐에 추가)

#include <bits/stdc++.h>
using namespace std;

// 인접 리스트에서 (연결 정점, 가중치) 형태로 저장
static const int MAXN = 100000;
vector<pair<int, long long>> adj[MAXN]; // adj[u] = {{v1, w1}, {v2, w2}, ...}

// 방문 배열
bool visited[MAXN];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, E; // 정점수 N, 간선수 E
    cin >> N >> E;

    for (int i = 0; i < E; i++){
        int u, v;
        long long w;
        cin >> u >> v >> w; 
        // 0-based라 가정
        // 양방향이라면 아래 두 줄
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // 프림 알고리즘
    // 1) 임의 정점(예: 0번)을 시작으로
    //    (만약 그래프가 완전히 연결되어 있지 않다면, 
    //     모든 정점을 순회하기 위해 추가 작업 필요)
    long long mstCost = 0;
    int usedVertices = 0;

    // 우선순위 큐: (간선 가중치, 현재 정점, 연결된 상대 정점)
    priority_queue< tuple<long long,int,int>,
                    vector< tuple<long long,int,int> >,
                    greater< tuple<long long,int,int> > > pq;

    // 0번 정점을 MST에 추가한다고 가정
    visited[0] = true;
    usedVertices++;
    // 0번 정점에 연결된 모든 간선을 pq에 삽입
    for (auto &nx : adj[0]) {
        int nxt = nx.first;
        long long cost = nx.second;
        pq.push({cost, 0, nxt});
    }

    // 2) 우선순위 큐에서 최소 비용 간선부터 뽑아서 MST 확장
    while (!pq.empty() && usedVertices < N) {
        auto [cost, u, v] = pq.top();
        pq.pop();

        // v가 이미 MST에 포함되어 있다면 skip
        if (visited[v]) continue;

        // v를 MST에 편입
        visited[v] = true;
        mstCost += cost;
        usedVertices++;

        // v와 연결된 간선들 중 MST 밖 정점들만 pq에 추가
        for (auto &nx : adj[v]) {
            int nxt = nx.first;
            long long nxtCost = nx.second;
            if (!visited[nxt]) {
                pq.push({nxtCost, v, nxt});
            }
        }
    }

    // MST 총 비용 출력
    cout << mstCost << "\n";

    return 0;
}