Algorithmes sur les graphes

Comme pour les arbres, il existe différentes façons de parcourir un graphe. On peut le parcourir en largeur ou en profondeur. Le parcours d'un graphe consiste à visiter tous ses nœuds.

Parcours en largeur

Nous allons utiliser des nœuds avec un attribut « visite » à « Faux » par défaut et qui sera mis à « Vrai » lorsqu'il aura été visité. Des nœuds sont dit adjacents ou voisins s'ils sont réliés par une arrête. Voici donc un algorithme du parcours en largeur :

VARIABLES
f : file
nœud : nœud de départ (origine)
x : nœud actuellement visité
y : nœud

DEBUT
nœud.visite = Vrai
f.enfile(nœud)
tant que f est non vide:
    x = f.defile()
    afficher x
    pour chaque y adjacent à x:
        si y.visite est Faux:
            y.visite = Vrai
            f.enfile(y)
FIN

1) Appliquez cet algorithme au graphe ci-dessous en partant de A. On notera sur une même ligne le nœud actuellement visité et le contenu de la file f.

2) Faire un tableau des distances entre A et les autres nœuds.

3) Qui a-t-il de remarquable entre ce tableau et le parcours en largeur ?

4) Appliquez à nouveau cet algorithme au graphe ci-dessous en prenant A comme nœud initial.

Parcours en profondeur

Voici maintenant un algorithme qui propose un parcours en profondeur :

VARIABLES
nœud : nœud de départ (origine)

DEBUT
profondeur(nœud):
    nœud.visite = True
    afficher nœud
    pour chaque y adjacent à nœud:
        si y.visite est Faux:
            profondeur(y)

FIN

5) Quelle est la particularité de ce programme par rapport au parcours en largeur ?

6) Appliquez cet algorithme au graphe ci-dessous en partant de A.

7) Appliquez à nouveau cet algorithme au graphe ci-dessous en prenant A comme nœud initial.

Chemin

Il est souvent nécessaire de trouver un chemin entre deux nœuds d'un graphe. Voici un algorithme qui permet de faire cette recherche :

VARIABLES
graphe : le graphe
start : nœud de départ (origine)
end : nœud d'arrivée
chaine : chemin initialement vide

DEBUT
trouve-chaine(graphe, start, end, chaine)
    ajouter start à chaine
    si start = end:
        retourner chaine
    pour chaque y adjacent à start:
        si y n'appartient pas à chaine:
            chemin = trouve-chaine(graphe, y, end, chaine)
            si chemin est non-vide
                retourner chemin
    retourner None
FIN

8) Appliquez rigoureusement cet algorithme au graphe ci-dessous entre A et C.

9) Appliquez à nouveau cet algorithme au graphe ci-dessous entre A et C.

Cycle

Un cycle est une suite d'arrêtes (donc une chaine) dont les deux extrémités sont identiques.

Il est parfois intéressant de savoir si un graphe contient un cycle. Par exemple un graphe qui contient un cycle ne peut pas être un arbre.

Voici donc un algorithme qui permet de détecter s'il y a au moins un cycle dans un graphe :

VARIABLES
graphe : le graphe
d : le nœud de départ
p : pile

DEBUT
trouve-cycle(graphe, d)
    p.empile(s)
    tant que p n'est pas vide:
        x = p.depile()
        pour chaque y adjacent à x:
            si y.visite est Faux:
                p.empile(y)
        si x.visite est Vrai:
            retourner Vrai
        sinon:
            x.visite = Vrai
    retourner Faux
FIN

10) Appliquez cet algorithme au graphe en haut de page en prenant A comme nœud initial.

11) Appliquez à nouveau cet algorithme au graphe ci-dessous en prenant A comme nœud initial.