Parcours de Graphes

Parcours de Graphes : DFS et BFS

Introduction

Le parcours de graphes est une technique fondamentale en informatique qui permet de visiter les sommets et les arêtes d'un graphe de manière systématique. Deux des algorithmes de parcours les plus couramment utilisés sont le parcours en profondeur (DFS - Depth-First Search) et le parcours en largeur (BFS - Breadth-First Search).

Parcours en Profondeur (DFS)

Le parcours en profondeur explore autant que possible chaque branche avant de revenir en arrière. Il utilise une pile (stack) pour garder la trace des sommets à visiter.

Exemple de Vulgarisation

Histoire : Imagine que tu es un explorateur dans un labyrinthe. Tu veux explorer chaque chemin aussi loin que possible avant de revenir sur tes pas pour essayer un autre chemin.

Implémentation en JavaScript

Version Récursive

// Fonction de parcours en profondeur (DFS) récursive
function dfsRecursive(graph, start, visited = new Set()) {
    // Marquer le sommet de départ comme visité
    visited.add(start);
    console.log(start);

    // Parcourir les voisins du sommet de départ
    for (let neighbor of graph[start]) {
        // Si le voisin n'a pas été visité, appel récursif sur ce voisin
        if (!visited.has(neighbor)) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
}

// Exemple d'utilisation
const graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1, 5],
    5: [2, 4]
};

dfsRecursive(graph, 0);
// Output attendu : 0 1 3 4 5 2

Version Iterative

// Fonction de parcours en profondeur (DFS) itérative
function dfsIterative(graph, start) {
    // Utilisation d'une pile pour gérer les sommets à visiter
    const stack = [start];
    const visited = new Set();

    // Tant que la pile n'est pas vide
    while (stack.length > 0) {
        // Prendre le sommet du haut de la pile
        const vertex = stack.pop();

        // Si le sommet n'a pas été visité
        if (!visited.has(vertex)) {
            // Marquer le sommet comme visité et l'afficher
            visited.add(vertex);
            console.log(vertex);

            // Ajouter tous les voisins du sommet à la pile
            for (let neighbor of graph[vertex]) {
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

// Exemple d'utilisation
dfsIterative(graph, 0);
// Output attendu : 0 2 5 4 1 3

Explication du Code

1. Marquage des Sommets : Les sommets visités sont marqués pour éviter les cycles et les répétitions.
2. Parcours des Voisins : Les voisins non visités de chaque sommet sont ajoutés à la pile ou visités récursivement.
3. Affichage : Chaque sommet visité est affiché dans l'ordre de visite.

Parcours en Largeur (BFS)

Le parcours en largeur explore tous les voisins d'un sommet avant de passer aux sommets de niveau suivant. Il utilise une file d'attente (queue) pour garder la trace des sommets à visiter.

Exemple de Vulgarisation

Histoire : Imagine que tu es un pompier qui cherche une personne dans un immeuble. Tu veux vérifier chaque étage complètement avant de passer à l'étage suivant.

Implémentation en JavaScript

// Fonction de parcours en largeur (BFS)
function bfs(graph, start) {
    // Utilisation d'une file pour gérer les sommets à visiter
    const queue = [start];
    const visited = new Set();

    // Marquer le sommet de départ comme visité
    visited.add(start);

    // Tant que la file n'est pas vide
    while (queue.length > 0) {
        // Prendre le sommet du début de la file
        const vertex = queue.shift();
        console.log(vertex);

        // Parcourir les voisins du sommet
        for (let neighbor of graph[vertex]) {
            // Si le voisin n'a pas été visité
            if (!visited.has(neighbor)) {
                // Marquer le voisin comme visité et l'ajouter à la file
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

// Exemple d'utilisation
bfs(graph, 0);
// Output attendu : 0 1 2 3 4 5

Explication du Code

1. Marquage des Sommets : Les sommets visités sont marqués pour éviter les cycles et les répétitions.
2. Parcours des Voisins : Les voisins non visités de chaque sommet sont ajoutés à la file d'attente.
3. Affichage : Chaque sommet visité est affiché dans l'ordre de visite.

Comparaison entre DFS et BFS

Complexité Temporelle et Spatiale

• DFS :

  • Complexité Temporelle : O(V + E), où V est le nombre de sommets et E le nombre d'arêtes.
  • Complexité Spatiale : O(V) pour la version récursive en raison de la pile d'appel, O(V) pour la version itérative.

• BFS :

  • Complexité Temporelle : O(V + E), où V est le nombre de sommets et E le nombre d'arêtes.
  • Complexité Spatiale : O(V) en raison de la file d'attente.

Applications

• DFS :

  • Détection de cycles dans un graphe.
  • Algorithmes de backtracking (p. ex., résolution de puzzles, génération de labyrinthes).
  • Algorithmes de connectivité (composantes connexes).

• BFS :

  • Calcul des plus courts chemins dans un graphe non pondéré.
  • Algorithmes de diffusion (p. ex., recherche de la portée dans les réseaux sociaux).
  • Algorithmes de niveaux (p. ex., vérification de la bipartité d'un graphe).

Conclusion

Les parcours en profondeur (DFS) et en largeur (BFS) sont des techniques fondamentales pour explorer les graphes. Ils offrent des moyens systématiques pour visiter tous les sommets et arêtes d'un graphe, chacun ayant ses propres avantages et applications en fonction des besoins spécifiques de la tâche à accomplir. En comprenant et en maîtrisant ces algorithmes, les développeurs peuvent résoudre une vaste gamme de problèmes dans les domaines de l'informatique, des réseaux, et au-delà.