GATE Overflow | Algorithms | Test 1 | Question: 30

Question

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)$

• A. i - b, ii - c, iii - a, iv - d
• B. i - c, ii - b, iii - d, iv - a
• C. i - b, ii - c, iii - d, iv - a
• D. i - c, ii - d, iii - a, iv - b

Answer 1

c is correct answer

Answer 2

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)

Comments

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.