Algorithmes de recherche en largeur (BFS)

8.1 Principes de fonctionnement de l'algorithme BFS

Recherche en largeur (Breadth-First Search, BFS) — c'est un algorithme de parcours ou de recherche dans un graphe, qui commence par le sommet initial et explore tous ses sommets voisins au niveau actuel avant de passer aux sommets du niveau suivant.

Étapes de l'algorithme :

1. On commence par le sommet initial choisi et on le place dans la file d'attente.
2. Tant que la file d'attente n'est pas vide, on fait ce qui suit :
   • On retire un sommet de la tête de la file et on le marque comme visité.
   • Pour chaque sommet voisin non visité, on l'ajoute dans la file d'attente.
3. On répète l'étape 2 jusqu'à ce que tous les sommets atteignables depuis le sommet initial soient visités.

Visualisation :

Complexité temporelle :

O(V + E), où V est le nombre de sommets, 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 file d'attente est utilisée pour stocker les sommets ainsi que des tableaux pour stocker l'état (sommets visités).

8.2 Implémentation de BFS avec une file d'attente

La recherche en largeur est bien mise en œuvre à l'aide d'une structure de données comme une file d'attente.

Implémentation de BFS avec une file d'attente :

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Traitement du nœud
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# Exemple d'utilisation :
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 Recherche bidirectionnelle en largeur

BFS est souvent utilisé dans les jeux lorsqu'il s'agit de trouver le chemin le plus court entre deux points dans un paysage complexe. Ce type de problème se transforme facilement en un problème de recherche de chemin dans un graphe entre deux sommets. Les arêtes d'un tel graphe sont tous les chemins praticables sur la carte.

Mais pour trouver le chemin plus rapidement, il est généralement recherché à partir des deux extrémités. Pour cela, on utilise BFS bidirectionnel.

Principe de fonctionnement

La recherche bidirectionnelle en largeur (Bidirectional BFS) est une version optimisée de l'algorithme BFS, qui effectue deux parcours parallèles du graphe : un à partir du sommet initial et un autre à partir du sommet cible. Les parcours continuent jusqu'à ce que les deux parcours se croisent, ce qui réduit considérablement le nombre de sommets et d'arêtes vérifiés par rapport au BFS classique.

Étapes de l'algorithme :

• Initialisation de deux files d'attente : une pour le parcours à partir du sommet initial, l'autre à partir du sommet cible.
• Initialisation de deux ensembles de sommets visités pour suivre les sommets visités dans les deux directions.
• Exécuter le parcours alterné du graphe à partir des deux files d'attente.
• À chaque étape, on vérifie si les ensembles de sommets visités se croisent. Si une intersection est trouvée, le chemin existe.
• Le processus continue jusqu'à ce qu'un nœud d'intersection soit trouvé ou que les files d'attente soient vides.

Complexité temporelle

Dans le meilleur des cas : O(2 * (V + E)) = O(V + E), où V est le nombre de sommets, E est le nombre d'arêtes.

BFS bidirectionnel effectue généralement le parcours d'un plus petit nombre de sommets par rapport au BFS unidirectionnel, en particulier dans les grands graphes.

Complexité spatiale :

O(V) pour stocker deux files d'attente et deux ensembles de sommets visités.

Exemple d'implémentation de BFS bidirectionnel

L'exemple est très long — l'algorithme est environ trois fois plus long que la recherche unidirectionnelle — donc je ne vais pas le donner ici. Quand vous en aurez vraiment besoin, vous serez en mesure de l'écrire vous-même.

8.4 Exemples de problèmes résolus à l'aide de BFS

Exemples classiques de problèmes résolus à l'aide de BFS :

1. Recherche du chemin le plus court dans un graphe non orienté :

BFS est utilisé pour trouver le chemin le plus court (nombre minimal d'arêtes) du sommet initial au sommet cible dans un graphe non orienté.

Applications :

• Dans les systèmes de navigation pour trouver le chemin le plus court entre des points.
• Dans l'analyse des réseaux pour trouver le chemin le plus court de transmission de données.

2. Vérification de la connectivité du graphe :

Vérifier si le graphe est connexe, c'est-à-dire s'il existe un chemin entre n'importe quels deux sommets.

Applications :

• Dans l'analyse des réseaux pour vérifier la connectivité du réseau.
• Dans l'analyse des réseaux sociaux pour vérifier la connectivité d'un groupe d'utilisateurs.

3. Génération de labyrinthes :

Utilisation de BFS pour générer des labyrinthes aléatoires avec des propriétés données.

Applications :

• Dans les applications de jeux pour créer des labyrinthes.
• En robotique pour tester des algorithmes de navigation.

4. Recherche en largeur dans les arbres :

BFS est utilisé pour parcourir des arbres afin d'effectuer des actions sur chaque niveau de l'arbre (par exemple, imprimer tous les nœuds à chaque niveau).

Applications :

• Dans les problèmes de visualisation des données, où il est nécessaire d'afficher les données par niveaux.
• Dans les problèmes de planification, où il est nécessaire d'effectuer des actions à chaque niveau de hiérarchie.

5. Vérification de la bipartition d'un graphe :

Vérifier si un graphe est biparti, c'est-à-dire si ses sommets peuvent être divisés en deux ensembles de telle sorte que les arêtes n'existent qu'entre les sommets de différents ensembles.

Applications :

• En théorie des graphes pour vérifier la bipartition d'un graphe.
• Dans les problèmes de coloration de graphes, où il est nécessaire de vérifier si un graphe peut être coloré avec deux couleurs.