1
$\begingroup$

I have this version of Prim's algorithm

Prim$(G=(V,E),s\in V,w)\\ 1.\ d(s)\leftarrow 0;\forall u \neq s:d(u)\leftarrow \infty\quad \color{red}{O(|V|)}\\ 2.\ \forall u \in V:p(u)\leftarrow \text{null}\quad \color{red}{O(|V|)}\\ 3.\ s\leftarrow \emptyset,T\leftarrow \emptyset\quad \color{red}{O(1)}\\ 4.\ Q \leftarrow \text{Makeheap}(V)\quad \color{red}{O(|V|)}\\ 5.\ \text{while}\ Q\neq \emptyset\\ 6.\qquad u\leftarrow Q.\text{ExtractMin()}\quad \color{red}{O(\log(|V|))}\\ 7.\qquad S\leftarrow S\cup\{u\},\ T\leftarrow T\cup\{(u,p(u))\}\quad \color{red}{O(1)}\\ 8.\qquad \text{for each}\ (u,z)\in E,z\in Q\\ 9.\qquad\qquad \text{if}\ d(z)>w(u,z)\ \text{then}\\ 10.\qquad\qquad\qquad Q.\text{Remove}(z);Q.\text{Insert}(z,w(u,z))\quad \color{red}{O(\log(|V|))}\\ 11.\qquad\qquad\qquad d(z)\leftarrow w(u,z),\ p(z)\leftarrow \quad \color{red}{O(1)}\\ 12.\ \text{return }T$

Total time: $O(|E|\log(|V|))$


Given a weighted, connected, simple undirected graph $G$ with weights of only $1$ and $2$ on each edge, why in this case the running time of the algorithm is $O(|E|+|V|\log(|V|))$?

I really not understand why the running time is not the same in this case, any help?

$\endgroup$
1
$\begingroup$

The running time depends on how you implement the queue data structure.

Hint: Can you think of any way to implement the queue data structures, so that ExtractMin, Remove, and Insert operations are much faster, if you're given the knowledge that every edge has weight either 1 or 2?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.