Minimal Spanning Tree


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.


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


Consider the following graph:

A minimal spanning tree of the graph is

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License