August 26, 2024
P83 - Construct all spanning trees.
Write a methodspanningTreesto construct all spanning trees of a given graph. With this method, find out how many spanning trees there are for the graph depicted to the right. The data of this example graph can be found below. When you have a correct solution for thespanningTrees method, use it to define two other useful methods:isTreeandisConnected. Both are five-minute tasks!
Graph:
Graph.term(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'),
List(('a', 'b'), ('a', 'd'), ('b', 'c'), ('b', 'e'),
('c', 'e'), ('d', 'e'), ('d', 'f'), ('d', 'g'),
('e', 'h'), ('f', 'g'), ('g', 'h')))
> Graph.fromString("[a-b, b-c, a-c]").spanningTrees
res0: List[Graph[String,Unit]] = List([a-b, b-c], [a-c, b-c], [a-b, a-c])
Be first to comment