Minimum Spanning Trees

A spanning tree is a set of edges that connect all nodes of a graph but does not have any superfluous edges. The problem of finding a spanning tree (usually of minimum cost) is common in communication networks where it is important that every node can communicate with all other nodes (not necessarily directly). It also occurs in distribution networks (e.g., supply houses of a block with water through a connected network of pipes, electricity networks).
logo for the category 'Kruskal's Algorithm'
Kruskal's Algorithm

Kruskal’s Algorithm computes a minimal spanning tree on an undirected graph. Furthermore, it returns a minimal spanning forest if the graph was unconnected.

logo for the category 'Prim's Algorithm'
Prim's Algorithm

Prim’s Algorithm computes a minimal spanning tree on an undirected graph.