World's most popular travel blog for travel bloggers.

# Prim's algorithm on graph with weights of only $1$ and $2$ on each edge

, ,
Problem Detail:

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?

###### Asked By : Error 404

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?