Par contre la fonction mark_from(s) du type centré-sommets ne peut pas être utilisée pour le type centré-arêtes puisque elle utilise l'opération NB_EDGES(s) qui est spécifique au type centré-sommets.
Malheureusement,
dans le type centré-arêtes, une opération équivalente à mark_from(s)
ne peut pas être réalisée aussi facilement qu'avec le type centré-sommets
car on n'a pas accès facilement aux arêtes issues d'un sommet.
Cet accès ne peut se faire qu'en parcourant pour chaque sommet l'ensemble
de ses arêtes. La complexité obtenue sera
au lieu de
dans le cas centré-sommets.
Pour pouvoir parcourir l'ensemble des arêtes du graphe il faut passer le graphe en paramètre en plus du sommet. Ce qui donnera la fonction suivante :
def mark_from (s, G): if NODE_MARKED(s): return MARK_NODE(s) for i in range(NB_EDGES(G)): e = EDGE(G, i) if EDGE_END(e, 0) == s: mark_from(EDGE_END(e, 1), G) if EDGE_END(e, 1) == s: mark_from(EDGE_END(e, 0), G)
La fonction connexité s'écrira alors de manière similaire au cas
centré-sommets mais aura une complexité
.
def connected (G): unmark_all(G) mark_from(NODE(G, 0), G) return all_nodes_marked(G):