Minimal Spanning Tree

# Introduction

A spanning tree is any subgraph of a graph that is a connected tree (in other words, the tree has to include every node in the graph, though not necessarily all edges). The construction of a *minimal spanning tree* is a graph theory problem in which one tries to find a spanning tree that has minimal cost, where the cost is the sum of the weights of the edges in a tree.

# Algorithms

Prim's Algorithm - Normally $O(V^2)$, but can become $O(E\log V)$ with a binary heap.

Kruskal's Algorithm

BorÅ¯vka's Algorithm

# Example

Consider the following graph:

A minimal spanning tree of the graph is

page revision: 5, last edited: 29 Oct 2008 02:28