최소 스패닝 트리(MST)를 구하는 알고리즘인 프림 알고리즘(Prim Algorithm)

프림 알고리즘은 최소 스패닝 트리를 구하는 데 사용되는 그리디 알고리즘이다. MST는 그래프의 모든 정점을 포함하면서, 모든 정점을 연결하는 간선의 가중치 합이 최소인 트리중 하나이다 프림 알고리즘은 임의의 시작 정점에서 출발하여, 각 단계마다 이미 선택된 정점과 연결된 간선 중 가장 작은 가중치를 가진 간선을 선택하여 트리에 추가하는 방식으로 동작한다

프림 알고리즘의 동작 과정

1. 임의의 시작 정점을 선택하고, 해당 정점을 MST에 포함
2. MST에 포함된 정점과 연결된 간선 중에서 가장 작은 가중치를 가진 간선을 선택 이 간선의 반대쪽 정점은 아직 MST에 포함되지 않은 정점
3. 선택된 간선과 해당 정점을 MST에 추가하고, 해당 정점을 MST에 포함
4. 모든 정점이 MST에 포함될 때까지 위 과정을 반복

프림 알고리즘 구현

#include <iostream>
#include <vector>
#include <queue>

// 그래프의 정점과 간선을 나타내는 구조체
struct Edge {
    int dest;     // 간선의 도착 정점
    int weight;   // 간선의 가중치
};

// 프림 알고리즘 함수
void primAlgorithm(const std::vector<std::vector<Edge>>& graph, int start) {
    int numVertices = graph.size();
    std::vector<bool> visited(numVertices, false);  // 방문 여부를 저장하는 배열
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;  // 우선순위 큐를 사용하여 최소 가중치 간선 선택
    
    // 시작 정점을 방문하고, 해당 정점과 연결된 간선을 우선순위 큐에 추가
    visited[start] = true;
    for (const Edge& edge : graph[start]) {
        pq.push(edge);
    }
    
    while (!pq.empty()) {
        Edge currentEdge = pq.top();
        pq.pop();
        int currentVertex = currentEdge.dest;
        
        // 이미 방문한 정점인 경우,패스
        if (visited[currentVertex]) {
            continue;
        }
        
        // 현재 간선을 MST에 추가
        std::cout << "Edge: " << start << " - " << currentVertex << ", Weight: " << currentEdge.weight << std::endl;
        visited[currentVertex] = true;
        
        // 현재 정점과 연결된 간선을 우선순위 큐에 추가
        for (const Edge& edge : graph[currentVertex]) {
            pq.push(edge);
        }
    }
}

int main() {
    // 그래프의 인접 리스트 표현
    std::vector<std::vector<Edge>> graph = {
        {{1, 2}, {2, 3}},               // 정점 0에 연결된 간선: (0, 1, 2), (0, 2, 3)
        {{0, 2}, {2, 4}, {3, 1}},       // 정점 1에 연결된 간선: (1, 0, 2), (1, 2, 4), (1, 3, 1)
        {{0, 3}, {1, 4}, {3, 2}},       // 정점 2에 연결된 간선: (2, 0, 3), (2, 1, 4), (2, 3, 2)
        {{1, 1}, {2, 2}}                // 정점 3에 연결된 간선: (3, 1, 1), (3, 2, 2)
    };
    
    int startVertex = 0;  // 시작 정점
    
    std::cout << "Minimum Spanning Tree:" << std::endl;
    primAlgorithm(graph, startVertex);