Copyright	Copyright (C) 2021 Yoo Chung
License	GPL-3.0-or-later
Maintainer	dev@chungyc.org
Safe Haskell	Safe-Inferred
Language	GHC2021

Problems.P84

Description

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

Synopsis

minimumSpanningTree :: G -> Map Edge Int -> G
weights84 :: Map Edge Int

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
>>> Set.foldr (\e w -> w + weights84 ! e) 0 $ edges t
33

Hint

Expand

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

weights84 :: Map Edge Int Source #

Edge to weight map for use with graph83 as an example for minimumSpanningTree.