Fiche de révision sur les algorithmes de parcours en largeur d'abord (BFS) et de parcours en profondeur d'abord (DFS) en utilisant Python.

Parcours en largeur (BFS)

L'algorithme de parcours en largeur d'abord (BFS) explore les nœuds d'un graphe ou d'un arbre de manière itérative, en visitant d'abord tous les nœuds du niveau courant, avant de passer aux nœuds du niveau suivant.
Voici comment implémenter le BFS récursif en Python :

def bfs_recursif(graphe, file=None, visite=None):
    if file is None and visite is None:
        file = ['A']  # Initialiser la file avec le nœud de départ
        visite = set(file)  # Ajouter le nœud de départ à l'ensemble des nœuds visités

    if not file:
        return

    sommet = file.pop(0)
    print(sommet)

    for voisin in graphe[sommet]:
        if voisin not in visite:
            file.append(voisin)
            visite.add(voisin)

    bfs_recursif(graphe, file, visite)

Exemple d'utilisation :

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("Parcours en largeur d'abord (BFS) récursif :")
bfs_recursive(graph, 'A')
# Résultat : A B C D E F

Version itérative en Python :

def bfs_iterative(graph, start):
    visited = set()
    queue = [start]
    visited.add(start)

    while queue:
        node = queue.pop(0)
        print(node)

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

    return visited

Exemple d'utilisation :

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("Parcours en largeur d'abord (BFS) itératif :")
bfs_iterative(graph, 'A')
# Résultat : A B C D E F

Dans les deux versions, nous utilisons une liste (queue) pour stocker les nœuds à visiter. La version récursive utilise un paramètre visited pour garder trace des nœuds déjà visités, tandis que la version itérative utilise un ensemble (visited) pour le même objectif.

Parcours en profondeur (DFS)

L'algorithme de parcours en profondeur d'abord (DFS) explore les nœuds d'un graphe ou d'un arbre de manière récursive ou itérative, en descendant d'abord aussi loin que possible dans une branche avant de revenir en arrière. Voici comment implémenter le DFS récursif en Python :

def dfs_recursif(graphe, depart, visite=set()):
    visite.add(depart)
    print(depart)

    for voisin in graphe[depart]:
        if voisin not in visite:
            dfs_recursif(graphe, voisin, visite)

Exemple d'utilisation :

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

print("Parcours en profondeur d'abord (DFS) récursif:")
dfs_recursif(graphe, 'A')
# Résultat : A B D E F C

Et voici comment implémenter le DFS itératif en utilisant une pile :

def dfs_iteratif(graphe, depart):
    visite = set()
    pile = [depart]

    while pile:
        sommet = pile.pop()
        if sommet not in visite:
            visite.add(sommet)
            print(sommet)

            for voisin in graphe[sommet]:
                if voisin not in visite:
                    pile.append(voisin)

Exemple d'utilisation :

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

print("Parcours en profondeur d'abord (DFS) itératif:")
dfs_iteratif(graphe, 'A')
# Résultat : A C F B E D

Conclusion

Les arbres binaires sont une structure de données importante en informatique, et il est essentiel de comprendre les algorithmes fondamentaux associés à leur manipulation.

Exercices - corrigés: parcours BFS (parcours en largeur) et DFS (parcours en profondeur)

Exercice 1:

Créez une classe Node pour représenter un nœud dans un arbre binaire de recherche. Chaque nœud doit avoir une valeur et des références vers ses nœuds enfants gauche et droit.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Exercice 2:

Implémentez une fonction insert qui prend en paramètre un nœud root et une valeur, et insère cette valeur dans l'arbre binaire de recherche correspondant. Assurez-vous que les valeurs plus petites sont insérées à gauche et les valeurs plus grandes à droite.

def insert(root, value):
    if root is None:
        return Node(value)
    
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    
    return root

Exercice 3:

Implémentez une fonction récursive inorder_traversal qui prend en paramètre un nœud root et effectue un parcours en ordre (infixe) de l'arbre en imprimant les valeurs des nœuds.

def inorder_traversal(root):
    if root is not None:
        inorder_traversal(root.left)
        print(root.value, end=" ")
        inorder_traversal(root.right)

Exercice 4:

Implémentez une fonction récursive preorder_traversal qui prend en paramètre un nœud root et effectue un parcours préfixe (préordre) de l'arbre en imprimant les valeurs des nœuds.

def preorder_traversal(root):
    if root is not None:
        print(root.value, end=" ")
        preorder_traversal(root.left)
        preorder_traversal(root.right)

Exercice 5:

Implémentez une fonction récursive postorder_traversal qui prend en paramètre un nœud root et effectue un parcours postfixe (postordre) de l'arbre en imprimant les valeurs des nœuds.

def postorder_traversal(root):
    if root is not None:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.value, end=" ")

Exercice 6:

Implémentez une fonction bfs_traversal qui prend en paramètre un nœud root et effectue un parcours en largeur (BFS) de l'arbre en imprimant les valeurs des nœuds.

from collections import deque

def bfs_traversal(root):
    if root is None:
        return
    
    queue = deque()
    queue.append(root)
    
    while queue:
        node = queue.popleft()
        print(node.value, end=" ")
        
        if node.left is not None:
            queue.append(node.left)
        
        if node.right is not None:
            queue.append(node.right)

Exercice 7:

Créez un arbre binaire de recherche avec les valeurs suivantes : 8, 3, 10, 1, 6, 14, 4, 7, 13. Utilisez les fonctions de parcours BFS et DFS pour imprimer les valeurs des nœuds.

root = None
values = [8, 3, 10, 1, 6, 14, 4, 7, 13]

for value in values:
    root = insert(root, value)

print("BFS traversal:")
bfs_traversal(root)
print()

print("Inorder traversal:")
inorder_traversal(root)
print()

print("Preorder traversal:")
preorder_traversal(root)
print()

print("Postorder traversal:")
postorder_traversal(root)
print()