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

Language | Haskell2010 |

- 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)$

mstEdges :: Ord e => PlanarGraph s w v e f -> [Dart s] Source

Computes the set of edges in the Minimum spanning tree

running time: $O(n log n)$