Minimum Spanning Tree
IT 위키
Minimum Spanning Tree (MST) is a subset of edges in a weighted, connected, and undirected graph that connects all the vertices with the minimum possible total edge weight, without forming any cycles.
1 Definition[편집 | 원본 편집]
Given an undirected graph G = (V, E), where:
- V is the set of vertices.
- E is the set of edges with weights.
A minimum spanning tree satisfies:
- It includes all vertices from V.
- It forms a tree (i.e., a connected acyclic subgraph).
- The sum of edge weights is minimized.
2 Properties[편집 | 원본 편집]
- A graph with N vertices has exactly N-1 edges in its MST.
- A connected graph may have multiple MSTs if different edge sets have the same total weight.
- Removing any edge from an MST disconnects the graph.
- Adding an edge to an MST creates a cycle.
3 Example[편집 | 원본 편집]
Consider the following weighted graph:
| Vertex Pair | Edge Weight |
|---|---|
| A - B | 4 |
| A - C | 3 |
| B - C | 1 |
| B - D | 2 |
| C - D | 5 |
One possible MST for this graph consists of the edges:
- B - C (1)
- B - D (2)
- A - C (3)
Total MST weight: 1 + 2 + 3 = 6
4 Algorithms[편집 | 원본 편집]
Several algorithms exist to find the minimum spanning tree efficiently:
- Kruskal's Algorithm
- Sorts all edges by weight and adds them one by one, ensuring no cycles are formed.
- Prim's Algorithm
- Grows the MST from an arbitrary starting vertex by adding the smallest edge connecting it to a new vertex.
- Borůvka's Algorithm
- Adds the smallest edge from each component to another component until a single tree remains.
5 Implementation[편집 | 원본 편집]
A simple implementation of Kruskal's algorithm in Python:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
self.parent[root_u] = root_v
def kruskal_mst(edges, n):
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
mst = []
for u, v, weight in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append((u, v, weight))
return mst
edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 5)]
mst = kruskal_mst(edges, 4)
print("Minimum Spanning Tree:", mst)
6 Applications[편집 | 원본 편집]
- Network Design
- Used in designing efficient communication, power, and transportation networks.
- Approximation Algorithms
- Forms the basis for solving hard problems like the Traveling Salesman Problem (TSP).
- Cluster Analysis
- Used in hierarchical clustering techniques.
