192 views

Match the following:

 i. BFS a. $O(\mid E \mid + \mid V \mid \log \mid V \mid)$ ii. DFS b. $O(E)$ iii. Kruskal's algorithm c. Stack iv. Dijikstra's Algorithm d. $O(E \log V)$
1. i - b, ii - c, iii - a, iv - d
2. i - c, ii - b, iii - d, iv - a
3. i - b, ii - c, iii - d, iv - a
4. i - c, ii - d, iii - a, iv - b

When use fibanocci heap dijkstra take O(E+VlogV). Kruskal always takes O(ElogE+VlogV) ..  Ei s O(V^2) so T=O(2ElogV+VlogV) or

O( ElogV)(assuming graph is not a sparse graph)

DFS is implemented using  stack

BFS O(E+V) =O(E) (again assuming graph is a dense graph)

Kruskal's and Dijikstra have same TC. if you can implement Dijikstr'as algo with FIbnocci heap then kruskal's can also be done.
this paper is really strange!!
Kruskal can take O(∣E∣+∣V∣log∣V∣) , if sorting of edges is done in preprocessing step.

And Dijkstra can take O(ElogV) , by min heap.

so A) is also possible.
Kruskal can be done in O(∣E∣+∣V∣log∣V∣) , edges are sorted in pre processing step.

Dijkstra can be implemented in O(ElogV) by min heap .

So A) is also possible.