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

The question stated that we are using the array as a queue, we cant modify it to be used as an array.

However, yes we can use this "queue" data structure to keep set of all visited vertices while all vertices are not visited.That saves us O(n) space.

But still, we need to use either Adjacency Matrix or Min-heap to find the min edge from all visited vertices.

Could you pls explain why have you chosen Adjacency matrix over min-Heap?

---

bcz we are using array as queue.

---

That's my point. That array has been used to implement a queue, Its Queue, which is available to us, how can we modify it?

---

@abhishek, why adjacency matrix? I mean the representation of graph is not mentioned in the question, they have mentioned the queue datastructure to implement Prims algo, so are you modifying the queue to adjacency matrix?

---

I think implementation of array using queue we need to adjency matrix.

---

what is meaning of array using queue? is it like each array forming a column of matrix and multiple columns are formed by multiple arrays?

why is it require, can u explain in detail?

---

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

---

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.