Algorithmes de parcours d'un graphe

Parcours de graphes

Du parcours d'arbres au parcours de graphes

Un arbre, étant un graphe connexe et acyclique, impose une structure stricte avec trois propriétés fondamentales :

• Chemin unique entre la racine et tout nœud.
• Aucun cycle : on ne peut revenir au point de départ sans faire demi-tour.
• Exploration linéaire : les parcours progressent toujours vers de nouveaux nœuds.

Conséquence

Cette structure rend inutile la mémorisation ou le marquage des nœuds visités, car aucun nœud ne peut être rencontré deux fois par des chemins différents.

Dans un graphe général (par opposition à un arbre), la structure n'impose plus de contraintes strictes, ce qui entraîne deux défis majeurs :

• Les cycles : Il est possible de partir d'un sommet A, d'en visiter d'autres, et de revenir à A sans emprunter le même chemin à l'envers. Un algorithme simple peut ainsi tourner en boucle infinie.
• Convergence des chemins : Plusieurs chemins distincts peuvent mener au même sommet. Sans contrôle, le même nœud peut être traité plusieurs fois, provoquant de la redondance, des inefficacités, ou des résultats incorrects.

Pour explorer un graphe, il est essentiel de mémoriser les nœuds déjà visités.

Parcours en largeur (BFS)

Le BFS explore un graphe par niveaux successifs, du plus proche au plus éloigné.

Mécanisme de base

Il utilise une file (FIFO) pour traiter les nœuds dans l'ordre de leur découverte. Un tableau de marquage est indispensable pour ne pas revisiter un nœud et éviter les boucles infinies.

Avant d'enfiler un voisin dans la file, on vérifie s'il est déjà marqué. S'il l'est, on l'ignore. C'est ce simple test qui transforme un algorithme potentiellement infini en un algorithme robuste.

Atout principal

Dans un graphe non pondéré, le BFS garantit de trouver le chemin le plus court (en nombre d'arêtes) entre la source et tout autre sommet. Le "niveau" de découverte correspond exactement à cette distance minimale.

Structure produite

Le parcours génère un arbre BFS, une arborescence qui retrace pour chaque sommet le chemin le plus court depuis la racine. Les arêtes du graphe original qui ne font pas partie de cet arbre sont ignorées, car elles correspondent à des chemins plus longs ou forment des cycles.

  Exemple

On considère le graphe suivant et on effectue un parcours en largeur à partir du sommet A.
Les voisins sont traités par ordre alphabétique.

graphe = {
    "A": ["B", "C", "D"],
    "B": ["A", "E"],
    "C": ["A", "D", "F"],
    "D": ["A", "C", "E", "F", "G"],
    "E": ["B", "D", "G"],
    "F": ["C", "D", "G"],
    "G": ["D", "E", "F"],
}

Initialisation du BFS

Avant toute exploration :

• Le sommet de départ est A
• A est immédiatement marqué visité
• La file contient uniquement A

Visites = \(\{A\}\), File = \([A]\)

Étape 1 — Traitement du sommet A

• Sommet défilé : \(A\)
• Voisins de \(A\) : \(B, C, D\)
• Tous sont non visités → on les marque et on les enfile

Visites = \(\{A,B,C,D\}\) File = \([B, C, D]\)

Étape 2 — Traitement du sommet B

• Sommet défilé : \(B\)
• Voisins de \(B\) : \(A, E\)
• \(A\) est déjà visité
• \(E\) est découvert et ajouté à la file

Visites = \(\{A,B,C,D,E\}\) File = \([C, D, E]\)

Étape 3 — Traitement du sommet C

• Sommet défilé : \(C\)
• Voisins de \(C\) : \(A, D, F\)
• \(A\) et \(D\) sont déjà visités
• \(F\) est découvert et ajouté à la file

Visites = \(\{A,B,C,D,E,F\}\) File = \([D, E, F]\)

Étape 4 — Traitement du sommet D

• Sommet défilé : \(D\)
• Voisins de \(D\) : \(A, C, E, F, G\)
• Tous sont visités sauf \(G\)
• \(G\) est découvert et ajouté à la file

Visites = \(\{A,B,C,D,E,F,G\}\) File = \([E, F, G]\)

Étape 5 — Traitement du sommet E

• Sommet défilé : \(E\)
• Tous ses voisins sont déjà visités

Visites = \(\{A,B,C,D,E,F,G\}\) File = \([F, G]\)

Étape 6 — Traitement du sommet F

• Sommet défilé : \(F\)
• Tous ses voisins sont déjà visités

Visites = \(\{A,B,C,D,E,F,G\}\) File = \([G]\)

Étape 7 — Traitement du sommet G

• Sommet défilé : \(G\)
• Tous ses voisins sont déjà visités
• La file devient vide → fin du parcours

Visites = \(\{A,B,C,D,E,F,G\}\) File = \([]\)

Ordre de visite

\(A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow F \rightarrow G\)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SOMMETS 100

// Structure pour la file d'attente
typedef struct {
    int elements[MAX_SOMMETS];
    int debut;
    int fin;
} File;

void initFile(File* f) {
    f->debut = 0;
    f->fin = 0;
}

void enfiler(File* f, int val) {
    f->elements[f->fin++] = val;
}

int defiler(File* f) {
    return f->elements[f->debut++];
}

bool fileVide(File* f) {
    return f->debut == f->fin;
}

// Structure pour le graphe (liste d'adjacence)
typedef struct Noeud {
    int sommet;
    struct Noeud* suivant;
} Noeud;

typedef struct {
    Noeud* tete;
} ListeAdj;

typedef struct {
    int n; // nombre de sommets
    ListeAdj* listes;
} Graphe;

// Créer un graphe avec n sommets
Graphe* creerGraphe(int n) {
    Graphe* graphe = (Graphe*)malloc(sizeof(Graphe));
    graphe->n = n;
    graphe->listes = (ListeAdj*)malloc(n * sizeof(ListeAdj));
    for (int i = 0; i < n; i++) {
        graphe->listes[i].tete = NULL;
    }
    return graphe;
}

// Ajouter une arête non orientée
void ajouterArete(Graphe* graphe, int u, int v) {
    Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
    nouveau->sommet = v;
    nouveau->suivant = graphe->listes[u].tete;
    graphe->listes[u].tete = nouveau;
    
    // Pour graphe non orienté, ajouter aussi l'arête inverse
    nouveau = (Noeud*)malloc(sizeof(Noeud));
    nouveau->sommet = u;
    nouveau->suivant = graphe->listes[v].tete;
    graphe->listes[v].tete = nouveau;
}

// BFS
void bfs(Graphe* graphe, int source) {
    bool visites[MAX_SOMMETS] = {false};
    File file;
    initFile(&file);
    
    visites[source] = true;
    enfiler(&file, source);
    
    printf("Ordre BFS : ");
    
    while (!fileVide(&file)) {
        int u = defiler(&file);
        printf("%d ", u);
        
        Noeud* voisin = graphe->listes[u].tete;
        while (voisin != NULL) {
            int v = voisin->sommet;
            if (!visites[v]) {
                visites[v] = true;
                enfiler(&file, v);
            }
            voisin = voisin->suivant;
        }
    }
    printf("\n");
}

int main() {
    // Création du graphe de l'exemple
    // A=0, B=1, C=2, D=3, E=4, F=5, G=6
    Graphe* graphe = creerGraphe(7);
    
    ajouterArete(graphe, 0, 1); // A-B
    ajouterArete(graphe, 0, 2); // A-C
    ajouterArete(graphe, 0, 3); // A-D
    ajouterArete(graphe, 1, 4); // B-E
    ajouterArete(graphe, 2, 3); // C-D
    ajouterArete(graphe, 2, 5); // C-F
    ajouterArete(graphe, 3, 5); // D-F
    ajouterArete(graphe, 3, 4); // D-E
    ajouterArete(graphe, 3, 6); // D-G
    ajouterArete(graphe, 4, 6); // E-G
    ajouterArete(graphe, 5, 6); // F-G
    
    bfs(graphe, 0);
    
    return 0;
}

def parcours_largeur(graphe, source):
    # Initialise la file (FIFO) et le suivi des sommets visités
    file = [source]            
    visites = [source]         
    ordre = [source]

    # Tant qu'il reste des sommets à explorer
    while file:
        u = file.pop(0)        # Récupère le premier sommet de la file

        # Explore chaque voisin non encore visité
        for v in graphe[u]:
            if v not in visites:
                visites.append(v)
                ordre.append(v)
                file.append(v) # Ajoute à la file pour exploration future

    return ordre

graphe = {
    "A": ["B", "C", "D"],
    "B": ["A", "E"],
    "C": ["A", "D", "F"],
    "D": ["A", "C", "E", "F", "G"],
    "E": ["B", "D", "G"],
    "F": ["C", "D", "G"],
    "G": ["D", "E", "F"],
}

ordre = parcours_largeur(graphe, "A")
print(ordre)

['A', 'B', 'C', 'D', 'E', 'F', 'G']

Parcours en profondeur (DFS)

Le DFS explore un graphe en s'enfonçant le plus loin possible le long d'un chemin avant de revenir en arrière (backtracking).
Contrairement au BFS qui progresse par niveaux, le DFS privilégie l'exploration complète d'une branche avant d'envisager les autres.

Mécanisme de base

Le DFS repose soit sur la récursion, soit sur une pile explicite (LIFO) pour mémoriser les sommets en attente d'exploration.

Atout principal

Le DFS permet d'analyser finement la structure interne du graphe. Il est particulièrement adapté à la détection de propriétés globales telles que :

• l'existence de cycles,
• la connexité,
• la bipartition,
• la structure hiérarchique induite par le graphe.

Contrairement au BFS, le DFS ne garantit pas la découverte d'un plus court chemin, mais il offre une exploration plus profonde et plus structurante.

  Exemple

On considère le même graphe. Dans toute la suite, l'ordre des voisins est celui donné par la liste d'adjacence. Le DFS est réalisé ici sous sa forme récursive, ce qui revient conceptuellement à utiliser une pile (LIFO).

Initialisation du DFS

Avant toute exploration :

• Le sommet de départ est \(A\)
• \(A\) est immédiatement marqué visité
• La pile d'appels contient implicitement \(A\)

Visites = \(\{A\}\), Pile (appels récursifs) = \([A]\)

Étape 1 — Traitement du sommet A

• Sommet courant : \(A\)
• Voisins de \(A\) : \(B, C, D\)
• Le premier voisin non visité est \(B\)

On marque \(B\) et on descend récursivement.

Visites = \(\{A, B\}\), Pile = \([A, B]\)

Étape 2 — Traitement du sommet B

• Sommet courant : \(B\)
• Voisins de \(B\) : \(A, E\)
• \(A\) est déjà visité
• \(E\) est non visité

On marque \(E\) et on continue l'exploration en profondeur.

Visites = \(\{A, B, E\}\), Pile = \([A, B, E]\)

Étape 3 — Traitement du sommet E

• Sommet courant : \(E\)
• Voisins de \(E\) : \(B, D, G\)
• \(B\) est déjà visité
• \(D\) est non visité

On marque \(D\) et on descend encore.

Visites = \(\{A, B, E, D\}\), Pile = \([A, B, E, D]\)

Étape 4 — Traitement du sommet D

• Sommet courant : \(D\)
• Voisins de \(D\) : \(A, C, E, F, G\)
• \(A\) et \(E\) sont déjà visités
• \(C\) est non visité

On marque \(C\) et on poursuit.

Visites = \(\{A, B, E, D, C\}\), Pile = \([A, B, E, D, C]\)

Étape 5 — Traitement du sommet C

• Sommet courant : \(C\)
• Voisins de \(C\) : \(A, D, F\)
• \(A\) et \(D\) sont déjà visités
• \(F\) est non visité

On marque \(F\) et on poursuit.

Visites = \(\{A, B, E, D, C, F\}\), Pile = \([A, B, E, D, C, F]\)

Étape 6 — Traitement du sommet F

• Sommet courant : \(F\)
• Voisins de \(F\) : \(C, D, G\)
• \(C\) et \(D\) sont déjà visités
• \(G\) est non visité

On marque \(G\) et on poursuit.

Visites = \(\{A, B, E, D, C, F, G\}\), Pile = \([A, B, E, D, C, F, G]\)

Étape 7 — Traitement du sommet G

• Sommet courant : \(G\)
• Voisins de \(G\) : \(D, E, F\)
• Tous sont déjà visités

Aucun nouvel appel récursif possible → retour en arrière (dépilement).

Ordre possible de visite

\(A \rightarrow B \rightarrow E \rightarrow D \rightarrow C \rightarrow F \rightarrow G\)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SOMMETS 100

// Structure pour le graphe (liste d'adjacence)
typedef struct Noeud {
    int sommet;
    struct Noeud* suivant;
} Noeud;

typedef struct {
    Noeud* tete;
} ListeAdj;

typedef struct {
    int n; // nombre de sommets
    ListeAdj* listes;
} Graphe;

Graphe* creerGraphe(int n) {
    Graphe* graphe = (Graphe*)malloc(sizeof(Graphe));
    graphe->n = n;
    graphe->listes = (ListeAdj*)malloc(n * sizeof(ListeAdj));
    for (int i = 0; i < n; i++) {
        graphe->listes[i].tete = NULL;
    }
    return graphe;
}

void ajouterArete(Graphe* graphe, int u, int v) {
    Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
    nouveau->sommet = v;
    nouveau->suivant = graphe->listes[u].tete;
    graphe->listes[u].tete = nouveau;
    
    nouveau = (Noeud*)malloc(sizeof(Noeud));
    nouveau->sommet = u;
    nouveau->suivant = graphe->listes[v].tete;
    graphe->listes[v].tete = nouveau;
}

// Fonction récursive pour DFS
void dfsRecursif(Graphe* graphe, int sommet, bool visites[]) {
    visites[sommet] = true;
    printf("%d ", sommet);
    
    Noeud* voisin = graphe->listes[sommet].tete;
    while (voisin != NULL) {
        int v = voisin->sommet;
        if (!visites[v]) {
            dfsRecursif(graphe, v, visites);
        }
        voisin = voisin->suivant;
    }
}

void dfs(Graphe* graphe, int source) {
    bool visites[MAX_SOMMETS] = {false};
    printf("Ordre DFS : ");
    dfsRecursif(graphe, source, visites);
    printf("\n");
}

int main() {
    Graphe* graphe = creerGraphe(7); // A=0, B=1, C=2, D=3, E=4, F=5, G=6
    
    ajouterArete(graphe, 0, 1); // A-B
    ajouterArete(graphe, 0, 2); // A-C
    ajouterArete(graphe, 0, 3); // A-D
    ajouterArete(graphe, 1, 4); // B-E
    ajouterArete(graphe, 2, 3); // C-D
    ajouterArete(graphe, 2, 5); // C-F
    ajouterArete(graphe, 3, 5); // D-F
    ajouterArete(graphe, 3, 4); // D-E
    ajouterArete(graphe, 3, 6); // D-G
    ajouterArete(graphe, 4, 6); // E-G
    ajouterArete(graphe, 5, 6); // F-G
    
    dfs(graphe, 0);
    
    return 0;
}

def parcours_profondeur(graphe, sommet, visites):
    # Ajouter le sommet actuel à la liste des nœuds visités
    visites.append(sommet)
    
    # Affichage du sommet pour suivre l'ordre de passage
    print(sommet, end=" ")

    # Parcourir tous les sommets adjacents (voisins) du sommet actuel
    for voisin in graphe[sommet]:
        # Si le voisin n'a pas encore été visité, on explore sa branche
        if voisin not in visites:
            # Appel récursif : on plonge plus profondément dans le graphe
            parcours_profondeur(graphe, voisin, visites)

graphe = {
    "A": ["B", "C", "D"],
    "B": ["A", "E"],
    "C": ["A", "D", "F"],
    "D": ["A", "C", "E", "F", "G"],
    "E": ["B", "D", "G"],
    "F": ["C", "D", "G"],
    "G": ["D", "E", "F"],
}

print("Ordre DFS : ", end="")
parcours_profondeur(graphe, "A", [])

Ordre DFS : A B E D C F G

Comparaison BFS vs DFS