next up previous contents index
suivant: Exercices monter: Graphe Eulérien précédent: Cas centré-sommets   Table des matières   Index

Cas centré-arêtes

Pour le cas centré-arêtes la même fonction peut être utilisée à condition de remplacer l'appel à l'opération NB_EDGES(NODE(G, i)) qui n'est pas disponible dans le type centré-arêtes l'appel nb_edges(NODE(G, i), G) que nous avons écrite plus haut pour le cas centré-arêtes.

Dans le cas centré-arêtes, la complexité de la fonction connected(G) est $O(\vert V(G)\vert * \vert E(G)\vert)$ et celle de la boucle for est aussi $O(\vert V(G)\vert * \vert E(G)\vert)$ à cause de l'appel à nb_edges qui est $O(\vert E(G)\vert)$ ce qui donne une complexité $O(\vert V(G)\vert * \vert E(G)\vert)$ pour la fonction eulerian.