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)을 제공하고, 실제 문제 해결의 출발점으로 자주 사용된다.