[C++로 배우는 알고리즘과 자료구조] Day 27: 최소 신장 트리 (크루스칼, 프림 알고리즘)

최소 신장 트리 (MST, Minimum Spanning Tree)

최소 신장 트리(MST)는 가중치가 있는 연결된 그래프에서 모든 정점을 포함하며, 간선의 가중치 합이 최소가 되는 트리입니다. MST를 찾는 대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있습니다.

크루스칼 알고리즘 (Kruskal's Algorithm)

크루스칼 알고리즘은 간선을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 MST를 구성하는 알고리즘입니다.

크루스칼 알고리즘의 시간 복잡도:

• (O(E \log E + E \log V)), 여기서 (E)는 간선의 수, (V)는 정점의 수입니다.

크루스칼 알고리즘 구현

그래프 구현 (간선 리스트 사용)

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

// 간선 구조체 정의
struct Edge {
    int src, dest, weight;
};

// 그래프 클래스 정의
class Graph {
public:
    Graph(int vertices);
    void addEdge(int src, int dest, int weight); // 간선 추가
    void kruskalMST(); // 크루스칼 알고리즘 호출

private:
    int vertices; // 정점의 수
    std::vector<Edge> edges; // 간선 리스트

    // 유니온-파인드 구조체 정의
    struct Subset {
        int parent;
        int rank;
    };

    int find(std::vector<Subset>& subsets, int i);
    void unionSubsets(std::vector<Subset>& subsets, int x, int y);
};

// 그래프 생성자 정의
Graph::Graph(int vertices) {
    this->vertices = vertices;
}

// 간선 추가 함수 정의
void Graph::addEdge(int src, int dest, int weight) {
    edges.push_back({src, dest, weight});
}

// 유니온-파인드에서 찾기 함수 정의
int Graph::find(std::vector<Subset>& subsets, int i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}

// 유니온-파인드에서 합치기 함수 정의
void Graph::unionSubsets(std::vector<Subset>& subsets, int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank) {
        subsets[xroot].parent = yroot;
    } else if (subsets[xroot].rank > subsets[yroot].rank) {
        subsets[yroot].parent = xroot;
    } else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

// 크루스칼 알고리즘 함수 정의
void Graph::kruskalMST() {
    std::vector<Edge> result; // 최종 MST를 저장할 벡터
    int e = 0; // 결과 간선의 수
    int i = 0; // 정렬된 간선을 순회하기 위한 변수

    // 간선을 가중치의 오름차순으로 정렬
    std::sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    // 유니온-파인드를 위한 초기화
    std::vector<Subset> subsets(vertices);
    for (int v = 0; v < vertices; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    while (e < vertices - 1 && i < edges.size()) {
        Edge nextEdge = edges[i++];

        int x = find(subsets, nextEdge.src);
        int y = find(subsets, nextEdge.dest);

        // 사이클을 형성하지 않는 경우 간선을 선택
        if (x != y) {
            result.push_back(nextEdge);
            unionSubsets(subsets, x, y);
            e++;
        }
    }

    // 최종 MST 출력
    std::cout << "최소 신장 트리의 간선:" << std::endl;
    for (auto edge : result) {
        std::cout << edge.src << " -- " << edge.dest << " == " << edge.weight << std::endl;
    }
}

// 메인 함수
int main() {
    Graph g(4);
    g.addEdge(0, 1, 10);
    g.addEdge(0, 2, 6);
    g.addEdge(0, 3, 5);
    g.addEdge(1, 3, 15);
    g.addEdge(2, 3, 4);

    g.kruskalMST();

    return 0;
}

프림 알고리즘 (Prim's Algorithm)

프림 알고리즘은 임의의 시작 정점에서 출발하여,

가장 적은 가중치를 가지는 간선을 선택하여 MST를 구성하는 알고리즘입니다. 프림 알고리즘은 주로 우선순위 큐를 사용하여 구현합니다.

프림 알고리즘의 시간 복잡도:

• 우선순위 큐를 사용한 구현: (O((V + E) \log V)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.

프림 알고리즘 구현

그래프 구현 (인접 리스트 사용)

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <utility>

// 그래프 클래스 정의
class Graph {
public:
    Graph(int vertices);
    void addEdge(int u, int v, int weight); // 간선 추가
    void primMST(); // 프림 알고리즘 호출

private:
    int vertices; // 정점의 수
    std::vector<std::list<std::pair<int, int>>> adjList; // 인접 리스트
};

// 그래프 생성자 정의
Graph::Graph(int vertices) {
    this->vertices = vertices;
    adjList.resize(vertices);
}

// 간선 추가 함수 정의
void Graph::addEdge(int u, int v, int weight) {
    adjList[u].push_back(std::make_pair(v, weight));
    adjList[v].push_back(std::make_pair(u, weight)); // 무방향 그래프
}

// 프림 알고리즘 함수 정의
void Graph::primMST() {
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    int src = 0; // 시작 정점

    std::vector<int> key(vertices, INT_MAX); // 모든 정점의 키 값을 무한대로 초기화
    std::vector<int> parent(vertices, -1); // MST를 구성하는 간선을 저장
    std::vector<bool> inMST(vertices, false); // MST에 포함된 정점을 추적

    pq.push(std::make_pair(0, src));
    key[src] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        inMST[u] = true;

        // 현재 정점과 인접한 모든 정점을 탐색
        for (auto i = adjList[u].begin(); i != adjList[u].end(); ++i) {
            int v = (*i).first;
            int weight = (*i).second;

            // 현재 정점 u를 통해 더 짧은 경로를 발견한 경우
            if (!inMST[v] && key[v] > weight) {
                key[v] = weight;
                pq.push(std::make_pair(key[v], v));
                parent[v] = u;
            }
        }
    }

    // 최종 MST 출력
    std::cout << "최소 신장 트리의 간선:" << std::endl;
    for (int i = 1; i < vertices; ++i) {
        std::cout << parent[i] << " -- " << i << " == " << key[i] << std::endl;
    }
}

// 메인 함수
int main() {
    Graph g(9);
    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);

    g.primMST();

    return 0;
}

 

설명

1. 그래프 클래스:
   • vertices: 그래프의 정점 수.
   • adjList: 각 정점의 인접 리스트를 저장하는 벡터.
2. addEdge 함수:
   • 정점 u에서 정점 v로의 간선과 가중치를 그래프에 추가합니다. 무방향 그래프이므로 반대 방향의 간선도 추가합니다.
3. primMST 함수:
   • 프림 알고리즘을 사용하여 MST를 구성합니다.
   • 우선순위 큐를 사용하여 각 정점의 최단 경로를 추적합니다.
   • 시작 정점을 0으로 설정하고, 모든 정점의 키 값을 무한대로 초기화합니다.
   • 인접 정점을 탐색하여 더 짧은 경로를 발견하면 키 값을 업데이트하고, 우선순위 큐에 삽입합니다.
   • MST에 포함된 간선을 추적하여 최종 MST를 출력합니다.

크루스칼 알고리즘과 프림 알고리즘의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 알고리즘과 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨주세요. 내일은 "Day 28: 동적 계획법 (DP) 기초"에 대해 학습하겠습니다.