Graphes : Structures et algorithmes de parcours

Définitions clés

Un graphe est une structure composée de sommets (ou nœuds) et d’arêtes (ou arcs) reliant ces sommets. On distingue deux types principaux :

• Graphe non orienté : les arêtes n’ont pas de direction (ex : réseau social).
• Graphe orienté : les arcs ont une direction (ex : réseau routier à sens unique).

Un graphe peut être représenté par :

• Matrice d’adjacence : tableau 2D où mat[i][j] = 1 si une arête existe entre i et j.
• Liste d’adjacence : liste où chaque sommet pointe vers ses voisins (plus efficace pour les graphes peu denses).

Parcours de graphes

Deux algorithmes fondamentaux permettent de parcourir un graphe :

1. Parcours en largeur (BFS) :

   • Utilise une file (FIFO).
   • Commence par un sommet, explore tous ses voisins avant de passer au niveau suivant.
   • Exemple : Trouver le plus court chemin dans un labyrinthe.

   from collections import deque
   def bfs(graphe, depart):
       file = deque([depart])
       visites = set([depart])
       while file:
           sommet = file.popleft()
           for voisin in graphe[sommet]:
               if voisin not in visites:
                   visites.add(voisin)
                   file.append(voisin)
   

2. Parcours en profondeur (DFS) :

   • Utilise une pile (LIFO) ou la récursivité.
   • Explore un chemin jusqu’à son extrémité avant de revenir en arrière.
   • Exemple : Détecter un cycle dans un graphe.

   def dfs(graphe, sommet, visites=None):
       if visites is None:
           visites = set()
       visites.add(sommet)
       for voisin in graphe[sommet]:
           if voisin not in visites:
               dfs(graphe, voisin, visites)
   

Applications

• Réseaux : Trouver des connexions (ex : internet, réseaux sociaux).
• Jeux vidéo : IA pour les déplacements (ex : labyrinthe).
• Optimisation : Algorithmes de plus court chemin (Dijkstra).

Complexité

• BFS/DFS : O(V + E) où V = nombre de sommets, E = nombre d’arêtes.
• Matrice d’adjacence : O(V²) en espace.
• Liste d’adjacence : O(V + E) en espace.

Remarque : Les graphes pondérés (avec des coûts sur les arêtes) nécessitent des algorithmes spécifiques comme Dijkstra ou A*.