Category:Minimal Spanning Tree

From Algowiki
Revision as of 15:47, 7 November 2014 by Flomm (talk | contribs) (Created page with "== Introduction == 400px The red colored edges are the minimal spanning tree of this graph. == Input == * A undirected connected graph <math>G=(...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Introduction

Min span tree.jpg

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 \subset 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              AA{(u,v)}
5 return A

Known algorithms

This category currently contains no pages or media.