[알고리즘] 최소 신장 트리(Minimum Spanning Tree)

 

 

반응형

 

최소 신장 트리(Minimum Spanning Tree)

신장 트리(Spanning Tree)란 그래프의 모든 정점을 포함하는 트리를 말한다. n개의 정점이 있다면 n-1개의 간선이 존재해야 한다. 이는 트리의 일종이기에 모든 정점들은 최소 하나의 간선에는 연결되어 있어야 하고, 사이클이 없어야 하기 때문이다. DFS와 BFS를 통해 얻어낸 트리도 신장 트리의 한 예가 된다.

 

연결 그래프 G

연결 그래프 G에 대한 BFS에서의 트리(좌)와 DFS에서의 트리(우)

최소 신장 트리(Minimum Spanning Tree)는 가중치 그래프에서 가중치의 합이 가장 작은 트리를 뜻한다. 이러한 최소 신장 트리를 찾는 알고리즘의 종류에는 프림 알고리즘(Prim Algorithm), 크루스칼 알고리즘(Kruskal Algorithm)이 있다.

---

프림 알고리즘(Prim Algorithm)

프림 알고리즘은 다음과 같은 과정으로 수행된다.

G = (V, E) 그래프에서
1. 시작 정점을 선택해 초기 트리를 만든다.
2. 현재 트리의 정점들과 인접한 정점들 중 간선의 가중치가 가장 작은 정점 v를 선택한다.
3. v와 해당 간선을 트리에 추가한다.
4. 간선의 수가 v-1이 될 때까지(또는 모든 정점이 추가될 때까지) 2~3을 반복한다.

 

프림 알고리즘(Prim Algorithm)의 수행 과정

 

그림에서와 같이 처음에는 시작 정점을 제외한 나머지 정점들은 값이 무한대가 된다. 이후, 트리에 추가된 정점의 인접 정점들의 값만 가중치로 갱신되고, 그 중 가장 작은 가중치를 가진 정점을 트리에 추가시켜나간다. (d)와 (g)의 경우처럼 가중치가 더 낮아진다면 더 낮은 쪽으로 갱신해준다.

int get_min_vertex() {
    int mindist = INF; // INF = 9999999
    int minv = 0;
    for (int v = 0; v < vtxsize; v++) {
        if (selectvtx[v] != false && dist[v] < mindist) {
            mindist = dist[v];
            minv = v;
        }
    }
    return minv;
}

void prim() {

    // 시작 정점을 제외하고 나머지는 무한대로 초기화
    for (int i = 0; i < vtxsize; i++) {
        dist[i] = INF; // dist는 정점들 간의 가장 가까운 거리를 저장하는 배열
        selectvtx[i] = false;
    }
    dist[0] = 0;
    
    for (int i = 0; i < vtxsize; i++) {
        int u = get_min_vertex();

        if (dist[u] == INF) { // u가 최소 신장 트리에 연결되어 있지 않은 경우 예외 처리
            return;
        }

        selectvtx[u] = true;
        cout << vtx[u] << " ";

        for (int v = 0; v < vtxsize; v++) { // 인접 정점들을 찾아 dist값 갱신
            if (grp[u][v] != INF) {
                if (selectvtx[v] != false && grp[u][v] < dist[v]) {
                    dist[v] = grp[u][v];
                }
            }
        }
    }
}

프림 알고리즘의 시간 복잡도를 분석해보자. Prim 함수의 첫번째 루프(초기화)에서 정점의 수만큼 반복된다. 아래의 두번째 루프에서도 마찬가지로 정점의 수 만큼 반복된다. 내부 for문도 정점의 수 만큼 반복된다는 것을 알 수 있다. 즉, \(O(n^2)\)이 된다.

 

인접 행렬이 아닌 인접 리스트로 그래프를 만들고 가중치가 최소인 정점을 찾는 방법을 힙으로 구현한다면, \(O(nlogn)\)이 된다. 아래는 그 예시이다.

vector<pair<int, int>> grp[MAX_VERTEX_SIZE];
bool selectvtx[MAX_VERTEX_SIZE];

// 최소 힙을 만들기 위해
struct compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.first > b.first;
    }
};

void prim() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
    pq.push({ 0, 0 }); // 시작 정점은 가중치가 0이다.

    while (!pq.empty()) {
        int weight = pq.top().first;
        int vertex = pq.top().second;
        pq.pop();

        if (visited[vertex])
            continue;

        visited[vertex] = true;
        cout << vertex << " ";

        for (int i = 0; i < grp[planet].size(); i++) {
            int next_cost = grp[planet][i].first;
            int next_vertex = grp[planet][i].second;
            if (!visited[next_vertex]) {
                pq.push({ next_weight, next_vertex });
            }
        }
    }
}

 

---

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

크루스칼 알고리즘은 다음과 같은 과정으로 수행된다.

G = (V, E) 그래프에서
1. 그래프의 모든 간선을 가중치의 크기 순으로 정렬해 배열에 저장한다.
2. 가중치가 가장 작은 간선 e를 하나 선택한다.
3. e를 넣어 만든 신장트리에 사이클이 생기면 다시 2번부터 시작한다.
4. 그렇지 않으면 신장 트리에 삽힙한다.
5. 삽입된 간선의 수가 n-1개가 될 때 까지 2번부터 반복한다.

크루스칼 알고리즘(Kruskal Algorithm)의 수행 과정

 

프림 알고리즘과는 달리 간선이 선택된다. 가중치가 가장 작은 간선부터 차례차례 선택되어 간다. (g)의 경우에서처럼, 사이클이 발생하면 삽입하지 않고 다음 순서로 넘어간다.

 

사이클이 생겼는지를 판별하는 법을 알아야한다. 사이클은 간선의 양끝 정점이 같은 집합에 속해 있으면 사이클이 형성된다. 이를 검사할 수 있게 도와주는 알고리즘이 Union-Find 알고리즘이다. 합집합을 만드는 알고리즘인데, 예를 들어 정점 A, B, C가 있다고 하자. 이들은 {A}, {B}, {C}라는 다른 집합에 들어있다(1). 이 상태는 서로 연결되어있지 않다는 의미이다. 이 셋을 합하면 {A, B, C}가 된다. 이는 A, B, C가 사이클 없이 연결된 상태를 의미한다(2). 만약 여기서 간선 (C, B)를 추가한다면 사이클이 생기게 될 것이다(3).

즉, 두 정점이 같은 집합에 있지 않으면 사이클이 형성되지 않게 된다는 의미이다.

// union-find 부분
int parent[MAX_VTX];
int set_size;
set<char> check_set;

bool find_set(int v1, int v2) {
    if (check_set.count(v1) == 1 && check_set.count(v2) == 1) {
        return true;
    }
    return false;
}

void union_set(int s1, int s2) {
    check_set.insert(s1);
    check_set.insert(s2);
}

struct Edge {
    int weight;
    int v1;
    int v2;
};

bool cmp(Edge a, Edge b) { return a.weight < a.weight; }

// Kruskal 알고리즘
void kruskal() {
    int edgecount = 0;
    int setv1, setv2;
    vector<Edge> weight;
    Edge e;

    // 가중치 저장
    for (int i = 0; i < vtxsize - 1; i++) {
        for (int j = i + 1; j < vtxsize; j++) {
            if (grp[i][j] != INF) {
                e.weight = grp[i][j];
                e.v1 = i;
                e.v2 = j;

                weight.push_back(e);
            }
        }
    }

    // 가중치 정렬
    sort(weight.begin(), weight.end(), cmp);

    // 간선 추가
    int idx = 0;
    while (edgecount < vtxsize - 1 || idx < weight.size()) {
        e = weight[idx];

        // 둘 다 집합에 없을 경우에만
        if (!find_set(e.v1, e.v2)) {
            cout << vtx[e.v1] << " " << vtx[e.v2] << " 가중치 : " << e.weight << endl;
            union_set(vtx[e.v1], vtx[e.v2]);
            edgecount++;
        }
        idx++;
    }
}

크루스칼 알고리즘의 수행 시간은 정렬 알고리즘에 큰 영향을 받는다. 첫번째 for문이 2중 루프라 \(O(n^2)\)일 것 같지만 실제로는 \(O(n)\)이다. 아래의 while문도 \(O(n)\)임을 알 수 있다. 그러니 정렬 알고리즘이 더 큰 값을 가지게 돼, 정렬 알고리즘에 따라 수행 시간이 결정된다. 위에서는 퀵정렬을 사용했으므로, 위 코드의 시간 복잡도는 \(O(nlogn)\)이다.

 

 

[Reference]

문병로, 「쉽게 배우는 알고리즘」 (한빛 아카데미, 2018)

 

 

728x90