Minimum Spanning Trees

상위 문서: Graph

개요

Spanning Tree는 주어진 그래프 G의 모든 정점을 포함하면서 사이클이 없는 부분 그래프이다. 그 중에서도 MST(Minimum Spanning Tree)는 G의 모든 spanning tree 중 간선 가중치의 총합이 최소인 트리를 의미한다. 이때 동일한 가중치를 가진 간선이 여러 개 있을 경우, 서로 다른 MST들이 존재할 수 있다. 또한 이는 Greedy Algorithm으로 항상 최적의 해를 얻을 수 있는 대표적인 문제이다. 하지만, 이를 해결하기 위해서는 효율적인 자료구조(우선순위 큐, Disjoint Set Union)가 필요하다.

아래는 해당 문서에서 MST에 대한 코드를 작성할 때 주어지는 그래프를 저장하는 자료구조이다:

int y;          // 간선이 연결된 정점
int weight;     // 간선의 가중치
struct edgenode *next;  // 다음 간선을 가리키는 포인터

위는 인접 리스트(adjacency list)에서 각 간선이 가중치(weight) 정보를 가지도록 확장한 형태이다.

edgenode *edges[MAXV+1]; // 각 정점의 인접 리스트 시작점
int degree[MAXV+1];      // 각 정점의 차수 (outdegree)
int nvertices;           // 정점 개수
int nedges;              // 간선 개수
int directed;            // 방향 그래프 여부

위는 그래프 구조 전체를 정의한 코드이다.

Applications of MSTs

MST 알고리즘은 여러 도시나 서버를 가장 적은 비용으로 연결하는 네크워크 구축을 하는데 사용된다. 또한 MST를 사용하여 점들을 연결한 뒤 가중치가 큰 간선을 끊어 그룹을 형성하는데 사용되기도 한다. 그 외에도, 친구 관계 그래프에서 자연스러운 친구 집단을 찾는 것과 같은 소셜 그래프 분석에도 사용된다.

MSTs and Net Partitioning

MST 알고리즘은 그래프를 여러 작은 부분으로 분할(partition)하는데 사용되기도 한다. 이는 아래와 같은 과정을 거친다:

1. 먼저 전체 그래프에서 MST를 만든다.
   • MST는 전체 정점을 모두 연결하면서도 가장 적은 비용으로 연결된 그래프이다.
   • 이를 통해 그래프 내의 "가벼운 간선"은 유지되고, "비싼 간선"은 최소화할 수 있다.
2. MST를 만든 뒤, 그 안에서 가장 큰 가중치의 간선을 하나 혹은 여러 개 제거한다.
   • 이렇게 하면 자연스럽게 그래프가 서로 잘 연결된 여러 작은 덩어리(subgraphs)로 나뉜다.

MSTs and TSP

TSP(Traveling Salesman Problem)는 외판원 문제라고도 불리며, 모든 정점(도시)을 한 번씩 방문하고 다시 출발점으로 돌아오는 최소 비용의 경로를 찾는 문제이다. 이때 MST는 TSP의 좋은 heuristic(근사 알고리즘)을 제공한다. MST를 두 번 따라가면 모든 노드를 방문하게 되고, 그 비용은 최적 TSP 경로의 2배 이내이기 때문이다. 즉, MST는 TSP의 하한(lower bound)을 제공하고, 실제 문제 해결의 출발점으로 자주 사용된다.

Prim’s Algorithm

Prim 알고리즘은 탐욕적(Greedy) 접근법을 사용해 MST를 만드는 대표적인 방법이다. 이는 아래와 같은 방법을 따른다:

1. 시작점 하나를 정하고, 그 정점에서부터 시작해 하나씩 간선을 추가하면서 트리를 확장한다.
2. 한 정점에서 출발해 주변 정점 중에서 가장 싼 간선(cheapest edge)을 선택하고, 그 정점을 트리에 추가한다.
3. 이 과정을 반복해서 결국 모든 정점이 연결될 때까지 계속 확장한다.

이 과정은 figure 1에 잘 설명되어 있다. 왼쪽 그림은 원래 그래프 G를 의미한다. 가운데 그림은 정점 A에서 시작해서 MST를 점차 확장한 것이다. 오른쪽 그림은 MST를 형성하는 다른 알고리즘인 kruskal 알고리즘을 G에 적용한 결과이다.

Pseudocode of Prim's Algorithm

아래는 Prim 알고리즘에 대한 수도 코드이다:

Prim-MST(G)
    임의의 시작 정점 s 선택
    While (트리에 포함되지 않은 정점이 남아있는 동안)
        Pick min cost edge between tree/non-tree vertices 
        Add the selected edge and vertex to the tree Tprim.

위 수도 코드에서 각 정점 v는 다음 세 가지 중 하나의 상태에 있다:

• In tree: 이미 MST에 포함됨
• Fringe: 트리와 연결될 수 있는 후보 정점
• Unseen: 트리와 전혀 연결되어 있지 않은 정점

Time Complexity of Prim's Algorithm

Prim 알고리즘은 자료구조에 따라 속도가 달라진다. 정점의 개수가 n이고 간선의 개수가 m인 그래프 G에 대해 가장 단순하게 구현을 한다면, 각 단계마다 트리와 트리 밖 정점 간의 최소 가중치 간선을 찾으므로, 각 단계는 O(n)의 시간 복잡도가 소요된다. 따라서 해당 과정을 모든 정점에 대해서 수행하므로 총 O(n²)의 시간복잡도가 소요된다.

이보다 효율적으로 만들려면, 우선순위 큐(min-heap)을 활용하여 간선 탐색을 매번 처음부터 하지 않을 수 있다. 이 경우, 시간 복잡도는 O((n + m)log(n))이 된다.

Prim’s Implementation

아래는 C 코드로 Prim 알고리즘을 직접 구현한 예시이다:

int prim(graph *g, int start) {
    edgenode *p;           // 간선 리스트를 순회할 포인터
    bool intree[MAXV+1];   // 정점 i가 트리에 포함되었는지 여부
    int distance[MAXV+1];  // 정점 i까지 연결되는 최소 간선 가중치
    int parent[MAXV+1];    // MST에서의 부모 정점
    int v;                 // 현재 처리 중인 정점
    int w;                 // 인접 정점
    int dist;              // 트리를 확장하기 위한 간선 중 가장 저렴한 연결 비용
    int weight = 0;        // 최종 MST의 총 가중치

    /* Initialization */
    for (int i = 1; i <= g->nvertices; i++) {
        intree[i] = false;    // 모든 정점을 intree[i] = false로 설정(아직 트리에 포함되지 않음)
        distance[i] = MAXINT; // 모든 거리를 MAXINT로 설정(연결된 간선이 없음)
        parent[i] = -1;       // 부모 없음
    }
    distance[start] = 0;      // 시작 정점(start)의 거리는 0으로 설정
    v = start;                // 현재 정점 v를 시작점으로 설정

    /* Main loop */
    while (!intree[v]) {
        intree[v] = true;     // 현재 정점 v를 트리에 포함
        if (v != start) {     // 시작점이 아니라면, 
            // parent[v]와 v를 연결하는 간선을 출력하고, 그 가중치를 weight에 더함.
            printf("edge (%d,%d) in tree\n", parent[v], v); 
            weight = weight + dist; 
        }

        /* Update distances for neighbors */
        p = g->edges[v]; 
        while (p != NULL) { // 현재 정점 v의 인접 리스트(edges[v])를 탐색.
            w = p->y;
            // 만약 현재 저장된 거리보다 더 작은 간선 가중치를 발견하면
            if ((distance[w] > p->weight) && (!intree[w])) {
                // 더 싼 가격으로 w를 트리에 포함할 수 있는 경로를 업데이트
                distance[w] = p->weight;
                parent[w] = v;
            }
            p = p->next;
        }

        // 아직 트리에 포함되지 않은 모든 정점 중에서 distance[i] 값이 가장 작은 정점을 v로 선택
        dist = MAXINT;
        for (i = 1; i <= g->nvertices; i++) {
            if ((!intree[i]) && (dist > distance[i])) {
                dist = distance[i];
                v = i;
            }
        }
    }

    return(weight);
}