Colin's Blog
[c++] 최소 스패닝 트리 알고리즘

최소 스패닝 트리는 주어진 그래프에서 모든 노드를 연결하면서 가장 작은 가중치 합을 갖는 트리를 찾는 알고리즘입니다. 대표적인 알고리즘으로는 Kruskal과 Prim이 있습니다.

Kruskal 알고리즘

Kruskal 알고리즘은 간선을 기준으로 동작하는 그리디 알고리즘입니다.

  1. 모든 간선을 가중치를 기준으로 오름차순으로 정렬합니다.
  2. 가장 작은 가중치를 가진 간선부터 검사하면서 사이클을 형성하지 않는 경우에만 그래프에 추가합니다.
  3. 모든 간선에 대해 위 과정을 반복합니다.

예시 코드:

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

struct Edge {
    int from, to, weight;
};

bool compareEdges(const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight;
}

int findParent(std::vector<int>& parent, int node) {
    if (parent[node] == node)
        return node;
    return parent[node] = findParent(parent, parent[node]);
}

void kruskalMST(std::vector<Edge>& edges, int numNodes) {
    std::sort(edges.begin(), edges.end(), compareEdges);
    std::vector<int> parent(numNodes);
    for (int i = 0; i < numNodes; ++i)
        parent[i] = i;
    
    int mstWeight = 0;
    for (const Edge& edge : edges) {
        int parent1 = findParent(parent, edge.from);
        int parent2 = findParent(parent, edge.to);
        if (parent1 != parent2) {
            std::cout << "Edge " << edge.from << " - " << edge.to << " added to MST" << std::endl;
            mstWeight += edge.weight;
            parent[parent1] = parent2;
        }
    }
    std::cout << "Minimum Spanning Tree Weight: " << mstWeight << std::endl;
}

int main() {
    std::vector<Edge> edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};
    kruskalMST(edges, 4);
    return 0;
}

Prim 알고리즘

Prim 알고리즘은 특정 노드를 기준으로 동작하는 그리디 알고리즘입니다.

  1. 임의의 시작 노드를 선택하고, 해당 노드에서부터 출발하는 간선 중에 가장 작은 가중치 간선을 선택하여 트리에 추가합니다.
  2. 트리에 추가된 노드들과 연결된 간선 중에 가장 작은 가중치를 갖는 간선을 찾아 트리에 추가합니다.
  3. 모든 노드가 트리에 포함될 때까지 위 과정을 반복합니다.

예시 코드:

#include <iostream>
#include <vector>
#include <limits>

std::vector<std::pair<int, int>> primMST(const std::vector<std::vector<std::pair<int, int>>>& graph, int numNodes) {
    std::vector<bool> visited(numNodes, false);
    std::vector<int> minWeight(numNodes, std::numeric_limits<int>::max());
    std::vector<int> parent(numNodes, -1);
    std::vector<std::pair<int, int>> mst;

    minWeight[0] = 0;
    for (int i = 0; i < numNodes; ++i) {
        int minNode = -1;
        for (int j = 0; j < numNodes; ++j) {
            if (!visited[j] && (minNode == -1 || minWeight[j] < minWeight[minNode])) {
                minNode = j;
            }
        }
        visited[minNode] = true;
        if (parent[minNode] != -1) {
            mst.push_back({parent[minNode], minNode});
        }
        for (const auto& edge : graph[minNode]) {
            int to = edge.first;
            int weight = edge.second;
            if (!visited[to] && weight < minWeight[to]) {
                parent[to] = minNode;
                minWeight[to] = weight;
            }
        }
    }
    return mst;
}

int main() {
    // 그래프의 인접 리스트 표현
    std::vector<std::vector<std::pair<int, int>>> graph = {{{1, 10}, {2, 6}, {3, 5}},
                                                          {{0, 10}, {3, 15}},
                                                          {{0, 6}, {3, 4}},
                                                          {{0, 5}, {1, 15}, {2, 4}}};
    std::vector<std::pair<int, int>> mst = primMST(graph, 4);
    for (const auto& edge : mst) {
        std::cout << "Edge " << edge.first << " - " << edge.second << " added to MST" << std::endl;
    }
    return 0;
}

최소 스패닝 트리 알고리즘은 네트워크 디자인, 도로 건설, 회로 박스 연결 등 다양한 분야에 응용됩니다.

참고 문헌

© 2018 Colin. All rights reserved.