Match List I with List II

List I	List II
(A) Topological sort of DAG	(I) O(V + E)
(B) Kruskal's MST algorithm	(II) O(VE)
(C) Bellman-Ford's single-source shortest path algorithm	(III) θ (V + E)
(D) Floyd-Warshall's all-pair   shortest path algorithm	(IV) θ(V3)

 

Choose the correct answer from the options given below: 

The correct answer is option 4.

Key Points

Topological sort of DAG= O(V + E)

Bellman-Ford's single-source shortest path algorithm=O(VE)

Floyd-Warshall's all-pairs shortest path algorithm= θ(V3)

Kruskal's MST algorithm= θ (V + E)

Due to sorting the edges, the dominant term in Kruskal's time complexity is O(ElogE). However, if we can conduct sorting in linear time or if the edges are already sorted, the problem can be solved by detecting whether there is a cycle in the graph or not. Since the edges have already been sorted, add each edge to MST one by one.

It is now possible to determine whether or not an undirected graph has a cycle:

1)   select one among DFT or BFT:- O(V+E)

2)   Using Union-Find:- O(ElogV)

 ∴ Kruskal’s MST algorithm :-  θ(V+E)

∴ Hence the correct answer is A - I, B - III, C - II, D - IV.