Algorithme de Prim sur le graphique avec des poids de seulement 1 $ et 2 $ $ sur chaque bord

Question

J'ai cette version de Algorithme de Prim

Prim $ (g = (v, e), s in v, w) 1. d (s) Leftarrow 0; forall u neq s: d (u) Leftarrow infty quad couleur {red} {o (| v |)} 2. forall u in v: p (u) Leftarrow text {null} quad couleur {red} {o (| v |)} 3. S Leftarrow videset, t Leftarrow videset quad couleur {red} {o (1)} 4. q gauche } {O (| v |)} 5. text {while} q neq videset 6. qquad u Leftarrow q. text {extractmin ()} quad couleur {red} ! quad couleur {red} {o (1)} 8. qquad tex } d (z)> w (u, z) text {alors} 10. qquad qquad qquad q. text {disposi w (u, z)) quad couleur {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 $

Temps total: $ o (| e | log (| v |)) $

---

Étant donné un graphique pondéré, connecté et non dirigé $ g $ avec des poids de seulement 1 $ et un $ $ sur chaque bord, pourquoi dans ce cas, l'heure d'exécution de l'algorithme est $ o (| e | + | v | log (| V |)) $?

Je ne comprends vraiment pas pourquoi le temps d'exécution n'est pas le même dans ce cas, une aide?