Qu'est-ce que l'algorithme de recherche en largeur?

L'algorithme de recherche en largeur (BFS - Breadth-First Search) est un algorithme de parcours ou de recherche dans un arbre ou un graphe. Il commence par le nœud racine (ou un nœud arbitraire si le graphe n'est pas un arbre) et explore tous ses voisins immédiats, puis explore les voisins de ces voisins, et ainsi de suite, niveau par niveau. BFS est implémenté en utilisant une file.

Principe de fonctionnement:

1. Mettre le nœud de départ dans la file.
2. Tant que la file n'est pas vide:
   • Extraire un nœud de la file.
   • Si le nœud est celui recherché, arrêter la recherche.
   • Sinon, mettre dans la file tous ses voisins non visités et les marquer comme visités.

Caractéristiques:

• Complétude: Garantit la trouvaille d'une solution si elle existe.
• Optimalité: Trouve le chemin le plus court dans un graphe sans poids (où les poids des arêtes sont égaux).
• Complexité en temps: Dépend de la structure du graphe, pour E arêtes et V sommets — O(V + E).
• Complexité en mémoire: O(V) dans le pire des cas, car il faut stocker les sommets visités et la file.

Applications en QA:

• Recherche du chemin le plus court entre des nœuds dans des scénarios de test.
• Exploration de tous les états accessibles du système lors des tests d'automates finis.
• Test de l'accessibilité de toutes les pages d'un site web lors du crawling.

Exemple (parcours d'arbre):

from collections import deque

# Exemple de représentation d'un arbre sous forme de dictionnaire d'adjacence
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Exemple d'appel
# bfs(graph, 'A')
# Sortie:
# A
# B
# C
# D
# E
# F