August 28, 2024
P84 - Construct the minimal spanning tree.
Write a method minimalSpanningTree to construct the minimal spanning tree of a given labeled graph.
Hint: Use Prim’s Algorithm. A small modification of the solution of P83 does the trick. The data of the example graph to the right can be found below.
Graph:
scala
Graph.termLabel(
List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'),
List(('a', 'b', 5), ('a', 'd', 3), ('b', 'c', 2), ('b', 'e', 4),
('c', 'e', 6), ('d', 'e', 7), ('d', 'f', 4), ('d', 'g', 3),
('e', 'h', 5), ('f', 'g', 4), ('g', 'h', 1)))
scala> Graph.fromStringLabel("[a-b/1, b-c/2, a-c/3]").minimalSpanningTree
res0: Graph[String,Int] = [a-b/1, b-c/2]
Be first to comment