Standard disclaimer: use the algorithms from class, such as…
Standard disclaimer: use the algorithms from class, such as DFS, Explore, BFS, Dijkstra’s (using min-heaps), SCC, Kruskal’s, Prim’s etc., as a blackbox subroutine for your algorithm. Make sure to explain your algorithm in words (no pseudocode!), explain the correctness of your design, and state and analyze its running time. Faster – and correct – solutions worth more credit. Design an algorithm to solve the following problem:Input: a connected, undirected, weighted graph G = (V,E), and a subset U of the vertices .Output: A spanning tree of G of minimal weight with the property that all the vertices in U are leaves. Note that there may be other leaves in the optimal tree and it isn’t necessarily a MST of G.