August 26, 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 P83does the trick. The data of the example graph to the right can be found below.
Graph:
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)))
> 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