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

#크루스칼

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 1001;
const int INF = 1e9;

int parent[MAX];

int Find(int a) {
    if (parent[a] == a) return a;
    return parent[a] = Find(parent[a]); // 경로 압축 기법
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) parent[b] = a; // 부모를 갱신하여 연결
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<pair<int, pair<int, int>>> edges; // {weight, {u, v}}
    for (int i = 0; i < M; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        edges.push_back({ weight, {u, v} });
    }

    // 부모 초기화
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    // 간선을 가중치 기준으로 정렬
    sort(edges.begin(), edges.end());

    int mst_weight = 0;
    vector<pair<int, int>> mst_edges;

    for (const auto& edge : edges) {
        int weight = edge.first;
        int u = edge.second.first;
        int v = edge.second.second;

        if (Find(u) != Find(v)) {
            Union(u, v);
            mst_weight += weight;
            mst_edges.push_back({ u, v });
        }
    }

    cout << "Minimum Spanning Tree Weight: " << mst_weight << "\n";
    cout << "Edges in the MST:\n";
    for (const auto& edge : mst_edges) {
        cout << edge.first << " - " << edge.second << "\n";
    }

    return 0;
}

 

 

#프림

#include <iostream>
#include <cstring> 
#include <climits>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 1001;
const int INF = 1e9;

vector<pair<int, int>> graph[MAX];
bool visited[MAX];

int prim(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int totalCost = 0;
    int connected = 0;

    pq.push({ 0,start });

    while (!pq.empty()) {
        int cost = pq.top().first;
        int current = pq.top().second;
        pq.pop();

        if (visited[current]) continue;
        visited[current] = true;
        totalCost += cost;
        connected++;

        if (connected == MAX) break;

        for (auto& edge : graph[current]) {
            int next = edge.first;
            int nextCost = edge.second;
            if (!visited[next]) pq.push({ nextCost,next });
        }
    }
    return totalCost;
}

int main() {
    
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({ b,c });
        graph[b].push_back({ a,c });
    }

    fill(visited, visited + MAX, false);
    
    cout << prim(1) << endl; 
    
    return 0;
}