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