Minimal Spanning Tree

Posted in Data structure by

The algorithm from Kruskal enables to extract the minimal spanning tree out of a Graph. Useful to save edges.

The algorithm sorts all edges depending on their costs. Starting with the lowest. A new graph without edges is created. Now take the edge with the lowest cost, add it to the graph if it doesn't create a cycle afterwards take the next edge and continue...

The runtime is O(e log e).

Published at , Updated at 2011-10-25

next: Plane Sweep Algorithm prev: All Pairs shortest Path