[C++로 배우는 알고리즘과 자료구조 심화] Day 8: 최소 신장 트리 (Minimum Spanning Tree) 심화

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

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

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

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

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

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

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

프림 알고리즘은 임의의 시작 정점에서 출발하여, 가장 적은 가중치를 가지는 간선을 선택하여 MST를 구성하는 알고리즘입니다.

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

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

크루스칼 알고리즘 구현

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

#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;
    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++;
        }
    }

    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;
}

 

프림 알고리즘 구현

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

#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);
    std::vector<bool> inMST(vertices, false);

    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;

            if (!inMST[v] && key[v] > weight) {
                key[v] = weight;
                pq.push(std::make_pair(key[v], v));
                parent[v] = u;
            }
        }
    }

    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. 크루스칼 알고리즘:
   • find: 유니온-파인드 구조체에서 특정 원소의 루트를 찾습니다.
   • unionSubsets: 두 집합을 합칩니다.
   • kruskalMST: 간선을 가중치 순으로 정렬하고, 사이클을 형성하지 않는 간선을 선택하여 MST를 구성합니다.
2. 프림 알고리즘:
   • addEdge: 간선을 추가합니다.
   • primMST: 우선순위 큐를 사용하여 각 정점의 최단 경로를 추적합니다. 시작 정점을 0으로 설정하고, 모든 정점의
   키 값을 무한대로 초기화합니다. 인접 정점을 탐색하여 더 짧은 경로를 발견하면 키 값을 업데이트하고, 우선순위 큐에 삽입합니다. MST에 포함된 간선을 추적하여 최종 MST를 출력합니다.

크루스칼 알고리즘과 프림 알고리즘의 심화 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 9: 최단 경로 알고리즘 심화 (벨만-포드, 존슨 알고리즘)"에 대해 학습하겠습니다.