World's most popular travel blog for travel bloggers.

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

, , No Comments
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
Answered By : D.W.

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?

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback