3 10 Marks Graphs The Non Circular Edge Problem The Input Is A Directed Graph G V E Containing M E Edges An 1 (22.76 KiB) Viewed 32 times
3. [10 marks] Graphs. The non-circular edge problem. The input is a directed graph G = (V, E) containing m= |E| edges and n = |V] nodes. Give an O(n + m) time algorithm to output all edges that are not part of a cycle. As usual, give pseudocode¹, a correctness argument, and analyze the runtime of your algo- rithm (i.e., explain why it has the desired complexity).
4. [10 marks] Graphs. The almost-unweighted graph problem. The input is an undirected weighted graph G = (V, E) and a source node s. The edge weights in this graph are restricted: Every edge has weight 1 or 3. Let n = |V), m= |E|, and V = (v₁, 02,..., Un). The desired output is an array d[1..n], where d contains the length of the shortest path from s to v. (In other words, we want to solve the single-source shortest-path problem.) Provide an O(n + m) algorithm (including pseudocode¹) to solve this problem. As usual, justify correctness and analyze the runtime of your algorithm (i.e., explain why it has the desired complexity).
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!