Safe Haskell | None |
---|---|

Language | Haskell2010 |

## Synopsis

- mst :: Ord e => PlanarGraph s w v e f -> Tree (VertexId s w)
- mstEdges :: Ord e => PlanarGraph s w v e f -> [Dart s]
- makeTree :: forall s w v e f. PlanarGraph s w v e f -> [Dart s] -> Tree (VertexId s w)

# Documentation

mst :: Ord e => PlanarGraph s w v e f -> Tree (VertexId s w) Source #

Minimum spanning tree of the edges. The result is a rooted tree, in which the nodes are the vertices in the planar graph together with the edge weight of the edge to their parent. The root's weight is zero.

The algorithm used is Kruskal's.

running time: \(O(n \log n)\)