Minimum Spanning Tree 편집하기

'''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.
==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.
==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.
==Example==
Consider the following weighted graph:
{| class="wikitable"
!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'''
==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.
==Implementation==
A simple implementation of Kruskal's algorithm in Python:<syntaxhighlight lang="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)
</syntaxhighlight>
==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.
==See Also==
*[[Graph Theory]]
*[[Shortest Path Problem]]
*[[Kruskal’s Algorithm]]
*[[Prim’s Algorithm]]
*[[Borůvka’s Algorithm]]
[[Category:Algorithm]]
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*