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 , but can become with a binary heap.
Kruskal's Algorithm
Borůvka's Algorithm

Example

Consider the following graph:

A minimal spanning tree of the graph is