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