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