Aller au contenu principal

Parcours de graphes

#Parcours de graphes : BFS et DFS

Les algorithmes de parcours de graphes sont fondamentaux en informatique. Ils permettent d'explorer systématiquement tous les nœuds d'un graphe, ce qui est essentiel pour de nombreuses applications comme la recherche de chemins, la détection de cycles, la topologie, etc.

#Parcours en largeur (BFS - Breadth-First Search)

Le parcours en largeur explore d'abord tous les nœuds à une distance donnée du nœud de départ, puis passe aux nœuds à la distance suivante. Il utilise une file (queue) pour gérer l'ordre de visite.

#Principe

  1. Mettre le nœud de départ dans une file
  2. Tant que la file n'est pas vide :
    • Retirer un nœud de la file
    • Si ce nœud n'a pas encore été visité :
      • Le marquer comme visité
      • Ajouter tous ses voisins non visités à la file

#Animation interactive

Voici une animation qui illustre le fonctionnement des algorithmes BFS et DFS :

Chargement...

#Implémentation en Python

pythonpython
1from collections import deque2 3def bfs(graphe, depart):4    """5    Parcours en largeur d'un graphe6    """7    visite = set()8    file = deque([depart])9    resultat = []10    11    while file:12        noeud = file.popleft()13        if noeud not in visite:14            visite.add(noeud)

#Parcours en profondeur (DFS - Depth-First Search)

Le parcours en profondeur explore aussi loin que possible le long de chaque branche avant de revenir en arrière. Il utilise une pile (stack) pour gérer l'ordre de visite.

#Principe

  1. Mettre le nœud de départ dans une pile
  2. Tant que la pile n'est pas vide :
    • Retirer un nœud de la pile
    • Si ce nœud n'a pas encore été visité :
      • Le marquer comme visité
      • Ajouter tous ses voisins non visités à la pile

#Implémentation en Python

pythonpython
1def dfs_iteratif(graphe, depart):2    """3    Parcours en profondeur d'un graphe (version itérative)4    """5    visite = set()6    pile = [depart]7    resultat = []8    9    while pile:10        noeud = pile.pop()11        if noeud not in visite:12            visite.add(noeud)13            resultat.append(noeud)14

#Comparaison BFS vs DFS

| Caractéristique | BFS | DFS | |----------------|-----|-----| | Structure de données | File (FIFO) | Pile (LIFO) | | Ordre d'exploration | Largeur d'abord | Profondeur d'abord | | Mémoire | Plus de mémoire (file peut grossir) | Moins de mémoire (pile généralement plus petite) | | Trouver le chemin le plus court | Oui (dans graphe non pondéré) | Non | | Applications | Trouver le chemin le plus court, niveaux | Topologie, détection de cycles, arbres de parcours |

#Applications

#BFS

  1. Trouver le chemin le plus court dans un graphe non pondéré
  2. Niveaux d'un arbre - explorer niveau par niveau
  3. Propagation - comme dans les réseaux sociaux
  4. Puzzles - trouver la solution minimale

#DFS

  1. Topologie - ordonner les nœuds selon les dépendances
  2. Détection de cycles dans un graphe
  3. Arbres de parcours - créer une structure arborescente
  4. Labyrinthes - trouver une sortie

#Exercice : Détection de cycles dans un graphe

Implémentez une fonction qui utilise DFS pour détecter si un graphe contient un cycle.

#Instructions

  1. Utilisez DFS avec un tableau de statuts pour chaque nœud
  2. Trois statuts : non visité (0), en cours de visite (1), visité (2)
  3. Si vous tombez sur un nœud en cours de visite, il y a un cycle

#Exemple de code

pythonpython
1def detecter_cycle(graphe):2    """3    Détecter un cycle dans un graphe dirigé4    """5    # 0: non visité, 1: en cours, 2: visité6    statut = {noeud: 0 for noeud in graphe}7    8    def dfs(noeud):9        # Marquer comme en cours de visite10        statut[noeud] = 111        12        # Visiter les voisins13        for voisin in graphe.get(noeud, []):14            if statut[voisin] == 1:  # Cycle détecté

#Complexité

| Algorithme | Complexité temporelle | Complexité spatiale | |------------|----------------------|---------------------| | BFS | O(V + E) | O(V) | | DFS | O(V + E) | O(V) |

Où V est le nombre de nœuds (vertices) et E est le nombre d'arêtes (edges).

Les algorithmes de parcours de graphes sont essentiels pour de nombreuses applications en informatique, des moteurs de recherche aux réseaux de neurones en passant par les compilateurs.