Category:Minimal Spanning Tree

Introduction

The red colored edges are the minimal spanning tree of this graph.

Input

• A undirected connected graph [math]\displaystyle{ G=(V,E) }[/math]
• A weight [math]\displaystyle{ w(u,v) }[/math] for each edge [math]\displaystyle{ (u,v) \in E }[/math]

Output

A acylic subset [math]\displaystyle{ T \subseteq E }[/math] in which [math]\displaystyle{ w(T) = \sum_{(u,v) \in T} w(u,v) }[/math] is minimal.

Generic algorihm

Generic-MST(G, w)
1 A ← ∅
2 while A is not a spanning tree
3     do determine a edge (u,v)
4              A ← A ∪ {(u,v)}
5 return A

Known algorithms

• Kruskal
• Prim