Parcours de graphes

Implémentations

Nous allons, tout d’abord, présenter différentes façons de représenter informatiquement un graphe. Nous les illustrerons par des exemples de graphes orientés, mais ces exemples sont tous transposables aux graphes non orientés en considérant simplement qu’une arête \(A – B\) correspond à deux arcs \(A → B\) et \(B → A\).

Matrice d’adjacence

Il s’agit d’un tableau de dimension 2 dans lequel on indique la présence ou le poids d’un arc (ou d’une arête) à l’intersection de la ligne et de la colonne dont les numéros (ou index) permettent d’identifier les deux sommets ainsi reliés.

Voici un exemple de matrice d’adjacence avec un graphe orienté pondéré.

On commence par numéroter les sommets : A:0, B:1 C:2, D:3.

On établit la matrice en passant en revue tous les arcs :

• Ainsi la présence de l’arc \(A → C\) se traduit par un 17 à l’intersection de la ligne 0 (sommet A) et de la colonne 2 (sommet C).
• Tandis que l’absence d’arc \(B → D\) fait qu’on retrouve 0 à l’intersection de la ligne 1 (sommet B) et de la colonne 3 (sommet D).

ou

$$\begin{pmatrix} 0 & 25 & 17 & 0 \\ 0 & 0 & 34 & 0 \\ 0 & 34 & 0 & 20 \\ 0 & 18 & 20 & 0 \end{pmatrix}$$

Remarques. Il faut un tableau de \(n^2\) entiers pour stocker un graphe de \(n\) sommets. Dans le cas d’un graphe non-orienté on obtient une matrice symétrique (suivant la diagonale descendante).

Liste d’adjacence

Lorsqu’il y a peu d’arcs ou d’arêtes, il devient plus intéressant de mémoriser pour chaque sommet du graphe, la liste de ses voisins (par leur numéro ou leur étiquette).

Voici un exemple de liste d’adjacence par numéro avec un graphe orienté non pondéré.

On commence par numéroter les sommets : A:0, B:1, C:2, D:3.

On établit dans l’ordre les listes des sommets liés aux sommets :

• A va vers B:1 et C:2 ce qui donne [1, 2].
• B va vers A:0 et D:3 ce qui donne [0, 3].
• C va vers A:0 ce qui donne [0].
• D va vers A:0 et C:2 ce qui donne [0, 2].

Ce graphe non pondéré est donc représenté par la liste [[1, 2], [0, 3], [0], [0, 2]].

La numérotation des sommets, à la fois arbitraire et imposée dans les représentations précédentes, peut être évitée en utilisant un dictionnaire. L’étiquette d’un sommet du graphe sert alors de clé et on lui associe la liste des étiquettes des sommets voisins.

Voici un exemple de liste d’adjacence par dictionnaire.

Les clés sont "A", "B", "C", "D" et "E". Pour chaque clé on établit la liste des clés voisines :

• "A" avec la liste "B", "C", "D".
• "B" avec la liste "C", "D".
• "C" avec la liste "B", "D", "E".
• "D" avec la liste "B".
• "E" avec la liste vide.

Ce qui donne le dictionnaire :

{
    "A": ["B", "C", "D"],
    "B": ["C", "D"],
    "C": ["B", "D", "E"],
    "D": ["B"],
    "E": []
}

Remarques. Il n’y a pas d’ordre prédéfini dans l’écriture d’une liste de voisins. Ces représentations peuvent être adaptées aux graphes pondérés en mémorisant des listes de couples (sommet voisin, poids).

Par la suite nous allons nous restreindre aux graphes non orientés connexes , pour lesquels il existe toujours un chemin reliant deux sommets quelconques ; contrairement aux autres graphes dont le parcours nécessite d’être repris à partir d’un sommet non encore parcouru.

Parcours

Tout comme pour les arbres, il existe plusieurs façons de parcourir les sommets en suivant les arêtes d’un graphe. On peut choisir d’avancer en passant en revue les voisins directs dans un premier temps, puis les voisins des voisins dans un second temps, et ainsi de suite. Ou au contraire, choisir d’avancer en passant par le premier sommet voisin disponible. Dans tous les cas il faut veiller à ne pas repasser par des sommets déjà parcourus. Aussi, il est nécessaire de marquer les sommets rencontrés au cours de l’exploration du graphe.

Nous allons illustrer ces différents parcours en prenant comme exemple le graphe ci-dessous.

Et nous utiliserons sa représentation sous forme de liste d’adjacence au moyen du dictionnaire suivant :

G = {
    "A": ["C", "I"],
    "C": ["A", "E"],
    "I": ["A", "R", "S"],
    "R": ["I"],
    "E": ["C", "S"],
    "S": ["E", "I"]
}

Nous utiliserons aussi une liste afin de marquer les sommets en les plaçant tout simplement dedans.

Parcours en profondeur (Depth-First Search - DFS)

Une fois établi le sommet de départ, le parcours en profondeur consiste à avancer tant que cela reste possible, ainsi à chaque étape on passe par le premier (ou dernier) voisin qui se présente et qui n’a pas encore été parcouru (marqué). Le parcours en profondeur utilise une pile pour stocker les sommets à parcourir : soit explicitement dans l’algorithme itératif, soit au travers de la pile d’appel dans l’algorithme récursif.

Parcours en profondeur récursif

# G : le graphe
# S : le sommet de départ
# deja_vus : la liste des sommets déjà visités qui est vide au départ et vaut donc []

def parcourir_profondeur_recursif(G, S, deja_vus):
    deja_vus.append(S)                  # marquer S
    print(S, end=" ")                   # traiter S
    for voisin in G[S]:
        if voisin not in deja_vus:
            parcourir_profondeur_recursif(G, voisin, deja_vus)

parcourir_profondeur_recursif(G, "A", [])

A C E S I R

Le parcours en profondeur récursif passe à chaque fois par le premier voisin non encore marqué : \(A\rightarrow C\) (premier voisin de A) \(\rightarrow E \rightarrow S \rightarrow I \rightarrow R\).

Parcours en profondeur itératif

def parcourir_profondeur_iteratif(G, S, deja_vus):
    pile_a_traiter = [S]                # pile initialisée avec S
    while pile_a_traiter != []:
        S = pile_a_traiter.pop()        # dépiler le sommet
        if S not in deja_vus:
            deja_vus.append(S)          # marquer S
            print(S, end=" ")           # traiter S
            for voisin in G[S]:
                if voisin not in deja_vus:
                    pile_a_traiter.append(voisin)

parcourir_profondeur_iteratif(G, "A", [])

A I S E C R

Le parcours en profondeur itératif passe par le dernier voisin non marqué (car c’est celui qui se retrouve au sommet de la pile) : \(A\rightarrow I\) (dernier voisin empilé de A) \(\rightarrow S \rightarrow E \rightarrow C \rightarrow R\).

Parcours en largeur (Breadth-First Search - BFS)

Le parcours en largeur consiste à examiner les sommets voisins puis les voisins des voisins et ainsi de suite… Il procède ainsi par éloignement progressif depuis le sommet de départ, c’est pourquoi il emploie une file dans l’algorithme itératif présenté ici.

def parcourir_largeur(G, S, deja_vus):
    file_a_traiter = [S]            # file initialisée avec S
    deja_vus.append(S)              # marquer S immédiatement
    while file_a_traiter != []:
        S = file_a_traiter.pop(0)   # défiler le sommet
        print(S, end=" ")           # traiter le sommet
        for voisin in G[S]:
            if voisin not in deja_vus:
                deja_vus.append(voisin)          # marquer le voisin
                file_a_traiter.append(voisin)    # enfiler le voisin

parcourir_largeur(G, "A", [])

A C I E R S

Le parcours en largeur itératif examine à chaque fois tous les voisins directs, non encore marqués, avant de passer aux voisins plus éloignés : A puis C et I (à une arête de A), puis E, R et S (à deux arêtes de A). Un sommet marqué est un sommet qui va être parcouru lors du défilement de la file ou qui a déjà été parcouru auparavant.

Comparaison des deux parcours

Les deux parcours itératifs ont une structure quasi identique. Deux points les distinguent :

Pourquoi marquer au dépilement en DFS ? Un même sommet peut être empilé plusieurs fois par des voisins différents. On ne sait pas encore par quelle arête le parcours y arrivera. Par exemple, "C" est empilé dès le départ (voisin de "A"), mais le parcours visite d’abord \(I \to S \to E\) avant de dépiler "C".

Pourquoi marquer à l’enfilement en BFS ? Le BFS explore les sommets par distance croissante. Quand on enfile un voisin, on sait que c’est par l’arête la plus courte en nombre d’arêtes. Marquer à l’enfilement évite d’enfiler un sommet en double.

Ordre DFS récursif vs itératif. En récursif, les voisins sont traités dans l’ordre de la liste d’adjacence. En itératif, ils sont empilés dans cet ordre puis dépilés en ordre inverse. C’est pourquoi les résultats diffèrent : A C E S I R (récursif) contre A I S E C R (itératif).

Propriété du BFS. Le parcours en largeur permet de trouver un plus court chemin en nombre d’arêtes entre deux sommets, car il explore par éloignement progressif.

Détection de cycle

Un cycle est un chemin dont le sommet d’arrivée est le sommet de départ. On identifie sa présence par le fait qu’on rencontre un sommet déjà parcouru (en s’interdisant un retour en arrière, bien évidemment).

Le graphe ci-dessous possède un cycle : G, F, I, J.

G = {
    "A": ["C"],
    "B": ["C"],
    "C": ["A", "B", "D"],
    "D": ["C", "E", "G"],
    "E": ["D"],
    "F": ["G", "I"],
    "G": ["D", "F", "H", "J"],
    "H": ["G", "K"],
    "I": ["F", "J"],
    "J": ["G", "I"],
    "K": ["H"]
}

Voici une implémentation de l’algorithme basée sur le parcours en profondeur itératif.

def possede_cycle(G, S, deja_vus):
    pile_a_traiter = [S]
    while pile_a_traiter != []:
        S = pile_a_traiter.pop()
        if S in deja_vus:           # S a-t-il été parcouru ?
            return True             # dans ce cas on a un cycle
        deja_vus.append(S)
        for voisin in G[S]:
            if voisin not in deja_vus:
                pile_a_traiter.append(voisin)
    return False


print(possede_cycle(G, "A", []))
# On supprime l'arête entre I et J dans le graphe G
G["I"].remove("J")        # J n'est plus un voisin de I
G["J"].remove("I")        # I n'est plus un voisin de J
# Il n'y a alors plus de cycle dans le graphe G
print(possede_cycle(G, "A", []))

True
False

Comme un sommet marqué est un sommet déjà parcouru, dès qu’on rencontre un sommet marqué cela signifie qu’on a réalisé un cycle.

La présence de doublons dans la pile, se traduit par la présence d’un cycle : la première occurrence va être marquée, c’est lors du dépilement de la seconde (qui aura emprunté une arête différente) qu’on constatera la présence du marquage et donc du cycle.

Recherche d’un chemin

La recherche d’un chemin, entre un sommet de départ et un sommet d’arrivée, s’effectue simplement en contrôlant à chaque étape si le sommet à traiter correspond à celui d’arrivée, tout en veillant à conserver la trace des arêtes parcourues.

def recherche_chemin(G, S, D):
    M = {}                       # les prédécesseurs
    R = []                       # le chemin inversé
    if parcourir(G, S, D, M):
        R.append(D)
        while D != S:
            D = M[D]
            R.append(D)
    R.reverse()
    return R


def parcourir(G, S, D, deja_vus):
    file_a_traiter = [S]                   # file de départ
    deja_vus[S] = None
    while file_a_traiter != []:
        S = file_a_traiter.pop(0)         # défiler
        if S == D:                         # destination ?
            return True                    # chemin trouvé
        for voisin in G[S]:
            if voisin not in deja_vus:
                deja_vus[voisin] = S       # prédécesseur
                file_a_traiter.append(voisin)
    return False                           # aucun chemin


print(recherche_chemin(G, "A", "K"))

['A', 'C', 'D', 'G', 'H', 'K']

Le parcours en largeur utilise ici un dictionnaire pour marquer les sommets parcourus et mémoriser l’origine de l’arête empruntée. Ce dictionnaire sert ensuite à reconstituer le chemin en remontant les arêtes suivies du sommet d’arrivée jusqu’au sommet de départ.