자료구조 - 최소비용 알고리즘

[최소비용 알고리즘 : Minimum Cost Algorithm)]

 

• 목표: 주어진 그래프에서 모든 정점을 연결하는데 필요한 최소 비용을 구하는 것입니다. 이는 주로 네트워크 설계, 도로망 구축, 전력 공급망 등에서 활용됩니다.
• 대표적인 예시: 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) 등이 있습니다.
• 특징: 그래프에서 간선의 가중치를 고려하여 최소 비용으로 모든 정점을 연결하는 트리를 생성합니다.

 

 

 

 

 

[신장 트리(spanning tree)]

신장 트리란 그래프 내의 모든 정점을 포함하는 트리입니다.

신장 트리는 모든 정점들이 연결되어 있어야하고 사이클을 포함해서는 안됩니다.

 

신장 트리는 네트워크 구축에 많이 사용됩니다.

네트워크는 각 링크마다 구축하는 비용이 다르고 최소의 비용을 소비하는 네트워크 망을 구축해야 합니다.

이러한 경우 최소 비용 신장 트리가 사용됩니다.

 

 

 

[최소 비용 신장 트리(MST : minimun spanning tree)]

 

MST의 특징

1. 연결성: 그래프의 모든 정점이 연결되어야 합니다.
2. 비순환성: 트리의 구조이므로 사이클이 존재하지 않아야 합니다.
3. 가장 적은 비용: 간선의 가중치의 합이 최소가 되어야 합니다.

 

 

최소비용 신장트리를 찾는 방법

 

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

크루스칼 알고리즘은 그래프에서 최소비용 신장트리를 찾는 알고리즘 중 하나입니다.

간선을 가중치의 오름차순으로 정렬한 후, 가장 작은 가중치의 간선부터 선택하면서 사이클이 생성되지 않도록 트리를 확장해 나가는 방식으로 동작합니다.

 

 

알고리즘 과정

1. 간선을 가중치의 오름차순으로 정렬한다.
2. 가장 작은 가중치의 간선부터 선택한다.
3. 선택한 간선이 사이클을 생성하지 않는 경우에만 트리에 추가한다.
4. 모든 정점이 연결될 때까지 2~3번 과정을 반복한다.

 

 

코드

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

// 간선을 나타내는 구조체
struct Edge 
{
    int src, dest, weight;
};

class KruskalMST 
{
    public:
        KruskalMST(const std::vector<Edge>& edges, int V) : V(V) 
        {
            // 그래프의 간선을 가중치의 오름차순으로 정렬
            this->edges = edges;
            std::sort(this->edges.begin(), this->edges.end(), [](const Edge& a, const Edge& b) 
            {
                return a.weight < b.weight;
            });
        }

        // 최소 비용 신장 트리를 생성하고 출력
        void findMST() 
        {
            // 부모 노드를 저장하는 배열 (Union-Find 연산을 위한 배열)
            std::vector<int> parent(V, -1);        

            int edgeCount = 0; // 선택한 간선의 수
            int index = 0; // 정렬된 간선 배열의 인덱스

            std::cout << "Minimum Spanning Tree edges using Kruskal's algorithm:\n";
            while (edgeCount < V - 1 && index < edges.size()) 
            {
                const Edge& edge = edges[index++];

                // 사이클이 생성되지 않는 경우에만 간선을 선택
                int x = find(parent, edge.src);
                int y = find(parent, edge.dest);

                if (x != y)
                {
                    std::cout << "(" << edge.src << " - " << edge.dest << ") ";
                    unionSet(parent, x, y);
                    ++edgeCount;
                }
            }
        }

    private:
        std::vector<Edge> edges; // 간선들
        int V; // 정점의 수

        // 부모 노드 찾기 (경로 압축 기법 사용)
        int find(std::vector<int>& parent, int i) 
        {
            if (parent[i] == -1)
                return i;
            return find(parent, parent[i]);
        }

        // 두 집합을 합치기
        void unionSet(std::vector<int>& parent, int x, int y)
        {
            int xroot = find(parent, x);
            int yroot = find(parent, y);
            parent[xroot] = yroot;
        }
};

int main()
{
    std::vector<Edge> edges = 
    {
        {0, 1, 10}, {0, 2, 6}, {0, 3, 5},
        {1, 3, 15}, {2, 3, 4}
    };
    int V = 4; // 정점의 수

    KruskalMST MST(edges, V);
    MST.findMST();

    return 0;
}

 

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

프림 알고리즘은 하나의 정점에서 시작하여 해당 정점과 연결된 간선 중 최소 가중치의 간선을 선택하면서 트리를 확장해 나가는 방식으로 동작합니다.

 

알고리즘 과정

1. 임의의 정점을 선택하여 시작한다.
2. 선택된 정점과 인접한 간선 중 가장 작은 가중치를 가진 간선을 선택한다.
3. 새로운 정점과 연결된 가장 작은 가중치의 간선을 선택하여 트리에 추가한다.
4. 모든 정점이 연결될 때까지 2~3번 과정을 반복한다.

 

 

 

코드

#include <iostream>
#include <vector>
#include <climits>

class PrimMST 
{
    public:
        PrimMST(int V) : V(V) {}

        // 최소 비용 신장 트리를 생성하고 출력
        void findMST(const std::vector<std::vector<int>>& graph) 
        {
            std::vector<int> parent(V, -1); // 부모 노드를 저장하는 배열
            std::vector<int> key(V, INT_MAX); // 최소 가중치를 저장하는 배열
            std::vector<bool> mstSet(V, false); // 최소 비용 신장 트리에 포함된 정점인지를 나타내는 배열

            key[0] = 0; // 임의의 시작 정점을 선택

            // 모든 정점을 순회하면서 MST를 구축
            for (int count = 0; count < V - 1; ++count) 
            {
                // 최소 가중치를 가진 정점을 찾음
                int u = minKey(key, mstSet);

                // 최소 가중치의 정점을 MST에 추가
                mstSet[u] = true;

                // u와 연결된 정점들에 대해 key 값을 업데이트
                for (int v = 0; v < V; ++v) 
                {
                    if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) 
                    {
                        parent[v] = u;
                        key[v] = graph[u][v];
                    }
                }
            }

            // MST 출력
            std::cout << "Minimum Spanning Tree edges using Prim's algorithm:\n";
            printMST(parent, graph);
        }

    private:
        int V; // 정점의 수

        // key 배열에서 최소값을 가진 정점을 찾는 함수
        int minKey(const std::vector<int>& key, const std::vector<bool>& mstSet)
        {
            int min = INT_MAX, minIndex = -1;    

            for (int v = 0; v < V; ++v)
            {
                if (!mstSet[v] && key[v] < min) 
                {
                    min = key[v];
                    minIndex = v;
                }
            }
            return minIndex;
        }

        // MST를 출력하는 함수
        void printMST(const std::vector<int>& parent, const std::vector<std::vector<int>>& graph)
        {
            for (int i = 1; i < V; ++i)
            {
                std::cout << "(" << parent[i] << " - " << i << ") ";
            }
            std::cout << std::endl;
        }
};

int main() 
{
    int V = 5; // 정점의 수
    std::vector<std::vector<int>> graph = 
    {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };

    PrimMST MST(V);
    MST.findMST(graph);

    return 0;
}

 

 

 

 

 

[Union-Find(합집합-찾기)]

여러 개의 서로소 집합들을 관리하며, 각 집합의 대표 원소를 찾거나 두 집합을 합치는 연산을 수행하는 알고리즘입니다.

주로 Kruskal 알고리즘에서 사이클을 검출하는 데 사용됩니다.

 

Union-Find 연산

MakeSet(x): 새로운 원소 x에 대해 단순히 자기 자신을 단일 집합으로 생성합니다.
Find(x): 원소 x가 속한 집합의 대표 원소를 찾습니다. 이때 대표 원소는 해당 집합의 루트 노드입니다.
Union(x, y): 두 집합을 합칩니다. 두 원소 x와 y가 속한 집합의 대표 원소를 찾아, 한 집합의 대표 원소의 부모를 다른 집합의 대표 원소로 설정합니다.

 

Union-Find 코드

#include <iostream>
#include <vector>

class UnionFind 
{
    public:
        UnionFind(int n) : parent(n), rank(n, 0) 
        {
            // 초기에는 모든 원소가 자신을 부모로 가리킴
            for (int i = 0; i < n; ++i)
                parent[i] = i;
        }

        // x가 속한 집합의 대표 원소를 찾는 연산
        int find(int x) 
        {
            if (parent[x] != x)
                parent[x] = find(parent[x]); // 경로 압축
            return parent[x];
        }

        // 두 집합을 합치는 연산
        void unionSets(int x, int y) 
        {
            int rootX = find(x);
            int rootY = find(y);

            // 두 집합의 대표 원소가 같으면 이미 같은 집합에 속해있음
            if (rootX == rootY)
                return;

            // rank를 기준으로 집합을 합침
            if (rank[rootX] < rank[rootY])
                parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY])
                parent[rootY] = rootX;
            else 
            {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }

    private:
        std::vector<int> parent; // 부모를 저장하는 배열
        std::vector<int> rank; // 각 집합의 높이를 저장하는 배열
};

int main() 
{
    UnionFind uf(5); // 원소가 5개인 집합 생성

    // 집합을 합치는 연산 예시
    uf.unionSets(0, 1);
    uf.unionSets(1, 2);
    uf.unionSets(3, 4);

    // 각 원소가 속한 집합의 대표 원소 출력
    for (int i = 0; i < 5; ++i)
        std::cout << "Parent of " << i << ": " << uf.find(i) << std::endl;

    return 0;
}

 

parent는 각 원소의 부모를 저장하는 배열이고, rank는 각 집합의 높이(또는 깊이)를 저장하는 배열입니다. 경로 압축(Path Compression)은 find 연산을 수행할 때, 재귀적으로 부모를 찾아가는 동안 해당 노드의 부모를 바로 루트로 설정하여 경로를 최적화하는 기법입니다.