Copyright | Copyright (C) 2021 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P84.

# Documentation

minimumSpanningTree :: G -> Map Edge Int -> G Source #

Write a function which constructs the minimum spanning tree of a given weighted graph. While the weight of an edge could be encoded in the graph represention itself, here we will specify the weight of each edge in a separate map.

### Examples

`>>>`

`let t = minimumSpanningTree graph83 weights84`

`>>>`

33`Set.foldr (\e w -> w + weights84 ! e) 0 $ edges t`

### Hint

The minimum spanning tree of a graph can be constructed using Prim's algorithm or Kruskal's algorithm.