Q5 MST Mix Up 0.3 Points For the questions below, determine whether the algorithm presented on the described graph will

[answerhappygod]

Q5 Mst Mix Up 0 3 Points For The Questions Below Determine Whether The Algorithm Presented On The Described Graph Will 1 (79.55 KiB) Viewed 78 times

Q5 MST Mix Up 0.3 Points For the questions below, determine whether the algorithm presented on the described graph will always, sometimes, or never find a valid MST. Assume that the original graph is • simple • connected • undirected • has at least one cycle • and the weights of all the edges are distinct. Assume ties are broken randomly in each algorithm presented. 1) For this part, additionally assume the original graph has at least one negative edge. Run Kruskal's as normal. Always finds a valid MST Sometimes finds a valid MST Never finds a valid MST 2) For this part, additionally assume the graph has exactly one cycle. Run DFS from a random vertex breaking ties by edge weight. Output the DFS tree. Always finds a valid SPT Sometimes finds a valid MST O Never finds a valid MST 3) Run Dijkstra's from every vertex in the graph for one step so that from each vertex we have found one edge. Add these edges to a set. Output the set. Always finds a valid MST Sometimes finds a valid MST Never finds a valid MST Save Answer