Gradeup Test series

Question

Suppose prim’s algorithm is implemented using array as queue for a graph $G(V,E)$. Then what is the time complexity of Prim’s algorithm?

• A. $O (E \hspace{0.1cm}log\hspace{0.1cm} V)$
• B. $O (V^2 \hspace{0.1cm}log\hspace{0.1cm} V)$
• C. $O(V^2)$
• D. $O(VE)$

Answer 1

If we use min heap to implement prims algorithm time complexity is: O(E log V)

without using min heap time complexity is: O$\left ( V^{2} \right )$

so answer would be option C.O$\left ( V^{2} \right )$

Comments

what do mean it is implemented without binary heap take o(v^2).????/

---

without binary heap means we can implement prim's algorithm with arrays. where as using min heap(i.e, using extract-min,decrease-key,build-heap) we can implement it in with O(E log V) time.

---

@Shaheena can you explain the significance of using array as a queue here? I do not understand what for a queue is being used. Is it related to DFS?

Thanks in advance.

---

prims algorithm basically implemented using queue . but what is need of using array as queue?

Answer 2

• if we are implement prims using array then We use a boolean array  to represent the set of vertices included in MST. so this implementation is done by adjacency matrix and time complexity become o(v^2).

Comments

I think the question is talking about the array implementation of queue, as follows-

struct queue{

int *rear;

int *front;

int arr[];

}

What do u say?

---

ok
but if it be done with adjacency matrix
then there should be multidiamentional array

---

Exactly that was my point. We don't have matrix here(so we can't easily say its O(V²)).We have been provided with the queue as a data structure so we'll use it to implement prims.