L'algoritmo di Prim sul grafico con pesi di soli $ 1 $ e $ 2 $ su ogni bordo

Question

Ho questa versione di L'algoritmo di Prim

Prim $ (g = (v, e), s in v, w) 1. d (s) leftarrow 0; forall u neq s: d (u) leftarrow infty quad color {rosso} {o (| v |)} 2. forall u in v: p (u) leftarrow text {null} quad color {rosso} {o (| v |)} 3. s leftarrow vuoto, t leftarrow vuoto Quad Color {Red} {o (1)} 4. q Leftarrow text {makeHeHap} (v) Quad Color {Red } {O (| v |)} 5. text {while} q neq vuoto 6. qquad u leftarrow q. text {extractmin ()} quad color {rosso {rosso {O ( log (| v |))} 7. qquad s leftarrow s coppa {u }, t leftarrow t coppa {(u, p (u)) } Quad color {rosso} {o (1)} 8. qquad text {per ciascuno} (u, z) in e, z in q 9. qquad qquad text {if } d (z)> w (u, z) text {quindi} 10. qquad qquad qquad q. text {remove} (z); q. text {insert} (z, w (u, z)) quad color {rosso} {o ( log (| v |))} 11. qquad qquad qquad d (z) leftarrow w (u, z), p (z) leftarrow quad color {rosso} {o (1)} 12. text {return} t $

Tempo totale: $ o (| e | log (| v |)) $

---

Dato un grafico ponderato, connesso, semplice non indiretto $ g $ con pesi di soli $ 1 $ e $ 2 $ su ogni bordo, perché in questo caso il tempo di esecuzione dell'algoritmo è $ o (| e |+| v | log (| V |)) $?

Non capisco davvero perché il tempo di esecuzione non è lo stesso in questo caso, qualche aiuto?