Cas centré-sommets

Nous allons nous baser sur l'algorithme 9.8 de la section 9.2. Cet algorithme utilise la fonction mark_from(s) décrite par l'algorithme 9.9. Il est indispensable d'implémenter mark_from pour pouvoir ensuite implémenter l'algorithme permettant de tester la connexité. Une traduction quasi-directe de l'algorithme 9.9 nous donne la fonction Python suivante :

def mark_from(s):
    if NODE_MARKED(s):
        return
    MARK_NODE(s)
    for i in range(NB_EDGES(s)):
        mark_from(FOLLOW_EDGE(s, EDGE(s, i)))

Les points $3$ et $4$ de l'algorithme 9.8 permettent de vérifier si tous les sommets du graphe ont été marqués. Cette opération pouvant être utile pour d'autres algorithme nous créons une fonction all_nodes_marked(G) qui retourne 1 (vrai) si tous les sommets sont marqués, 0 (faux) sinon.

def all_nodes_marked (G):
    for i in range(NB_NODES(G)):
        if not NODE_MARKED(NODE(G, i)):
            return 0
    return 1

Il est maintenant aisé de traduire l'algorithme 9.8 en une fonction
connected(G)
qui retourne 1 (vrai) si le graphe G est connexe, 0 (faux) sinon.

def connected (G):
    unmark_all(G)
    mark_from(NODE(G, 0))
    return all_nodes_marked(G):

La fonction unmark_all(G) sert à démarquer tous les sommets du graphe. Sa complexité est $O(\vert V(G\vert)$. Elle s'écrit très simplement :

def unmark_all (G):
    for i in range(NB_NODES(G)):
        UNMARK_NODE(NODE(G, i))