Standard disclaimer: your solution should use the algorithms…
Standard disclaimer: your solution should use the algorithms from class (DFS, BFS, Dijkstra’s, Topological Sort, Bellman-Ford, Floyd-Warshall, SCC, Kruskal’s, Prim’s, Ford-Fulkerson, Edmonds-Karp, and 2-SAT) as a black box subroutine for your algorithm. If you attempt to modify one of these algorithms you will not receive full credit, even if it is correct. 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 are worth more credit. You are given a connected, undirected, weighted graph G=(V,E) with distinct edge weights w(e), and a Minimum Spanning Tree T of G. An edge e’ that is in T is deleted from G, creating a new graph G’=(V,E’). This is, G’ has the same set of vertices and exactly one less edge. Design an algorithm to produce an MST of G’. Your algorithm must return False if G’ has no MST.
Read Details