Algorithmes de recherche en profondeur (DFS)

7.1 Principes de fonctionnement de l'algorithme DFS

Recherche en profondeur (Depth-First Search, DFS) — c'est un algorithme de parcours ou de recherche dans un graphe. Il commence par le sommet initial et va en profondeur dans le graphe jusqu'à atteindre un sommet sans voisins non visités, puis revient en arrière et continue le processus avec d'autres sommets.

Étapes de l'algorithme :

1. On commence par le sommet initial choisi et on le marque comme visité.
2. On explore le premier sommet voisin non visité.
3. On répète les étapes 1 et 2 pour ce sommet voisin.
4. Si tous les voisins du sommet actuel sont visités, on revient en arrière (backtrack) au sommet précédent et continue le processus.
5. Le processus se répète jusqu'à ce que tous les sommets atteignables du sommet initial soient visités.

Visualisation :

Complexité temporelle et spatiale de DFS :

Complexité temporelle :

O(V + E), où V est le nombre de sommets et E est le nombre d'arêtes.

Chaque nœud et chaque arête du graphe sont visités une fois.

Complexité spatiale :

O(V), car une pile d'appels ou une pile explicite est utilisée pour stocker les sommets, ainsi que des tableaux pour stocker l'état (sommets visités).

7.2 Implémentation de DFS en utilisant la récursion

Commençons par implémenter DFS en utilisant la récursion — le code sera élégant et compact.

Implémentation récursive de DFS :

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Traitement du nœud
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# Exemple d'utilisation :
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 Implémentation de DFS en utilisant une pile

Sans récursion, le code sera un peu plus long, car nous devons stocker la liste des sommets visités.

Implémentation itérative de DFS (en utilisant une pile) :

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Traitement du nœud
        
            for neighbor in reversed(graph[vertex]):  # Ordre inverse pour l'ordre de parcours correct
                if neighbor not in visited:
                    stack.append(neighbor)
        
# Exemple d'utilisation :
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 Exemples de problèmes résolus avec DFS

Exemples classiques de problèmes résolus avec DFS :

1. Recherche de chemin dans un labyrinthe :

Utilisé pour trouver un chemin dans un labyrinthe du point de départ au point d'arrivée.

Application :

Dans les jeux vidéo et la robotique pour la navigation dans les labyrinthes et les espaces complexes.

2. Vérification de la connectivité d'un graphe :

Vérifier si un graphe est connexe (s'il existe un chemin entre n'importe quelles deux sommets).

Application :

Dans l'analyse de réseau pour vérifier la connectivité d'un réseau.

3. Tri topologique :

Utilisé pour ordonner les sommets d'un graphe orienté acyclique (DAG) de telle manière que pour toute arête (u, v) le sommet u précède le sommet v.

Application :

Dans les compilateurs pour l'ordonnancement des dépendances et des tâches.

4. Détection de cycles dans un graphe :

Vérifier si un graphe contient des cycles.

Application :

Dans l'analyse des dépendances pour détecter les dépendances cycliques.

5. Génération de labyrinthes :

Utilisation de DFS pour générer des labyrinthes aléatoires.

Application :

Dans les applications de jeux et de divertissement pour créer des labyrinthes.