Graphes

#GraphesCopier le lien

#Parcours BFS (liste d’adjacence)Copier le lien

#Parcours DFS (récursif et itératif)Copier le lien

#BFS vs DFS en un coup d’œilCopier le lien

• BFS parcourt le graphe par couches croissantes de distance en utilisant une file (queue). Idéal pour trouver un plus court chemin dans un graphe non pondéré.
• DFS suit un chemin en profondeur avec une pile ou la récursion. Utile pour détecter des cycles, faire un tri topologique ou explorer des composantes connexes.

#Atelier interactif : file vs pileCopier le lien

#Arbres couvrants minimaux (MST)Copier le lien

Deux approches classiques: Kruskal (tri des arêtes + union‑find) et Prim (tas sur les coupes).

#Kruskal (Union‑Find)Copier le lien

#Kruskal en trois étapesCopier le lien

1. Trier les arêtes par poids croissant.
2. Parcourir la liste et ajouter une arête si elle ne crée pas de cycle (testé via union-find ou composants connexes).
3. Arrêter lorsque l’on a sélectionné $|V|-1$ arêtes : on obtient alors un arbre couvrant minimal.

#Prim (tas binaire)Copier le lien

#Exercice : Algorithme de Dijkstra pour les plus courts cheminsCopier le lien

Implémentez l'algorithme de Dijkstra pour trouver les plus courts chemins depuis un sommet source dans un graphe pondéré.

#InstructionsCopier le lien

1. Utilisez une file de priorité (min-heap) pour stocker les sommets à visiter.
2. Initialisez les distances à l'infini, sauf pour le sommet source (distance 0).
3. Pour chaque sommet, mettez à jour les distances de ses voisins si un chemin plus court est trouvé.
4. Marquez les sommets comme visités pour éviter les traitements multiples.

#Exemple de codeCopier le lien

1import heapq2from collections import defaultdict3 4def dijkstra(graph, start):5    # Initialisation des distances6    distances = defaultdict(lambda: float('inf'))7    distances[start] = 08    9    # File de priorité: (distance, sommet)10    pq = [(0, start)]11    visited = set()12    13    while pq:14        current_distance, current_vertex = heapq.heappop(pq)

#Tri topologique (Kahn) et détection de cyclesCopier le lien

#Kahn en pratiqueCopier le lien

1. Mettre dans la file tous les sommets de degré entrant nul.
2. Retirer un sommet, l’ajouter à l’ordre topologique, décrémenter le degré entrant de ses successeurs.
3. Dès qu’un successeur atteint le degré 0, l’ajouter dans la file.
4. S’il reste des sommets avec un degré strictement positif, le graphe avait un cycle.

#Notations et formules utilesCopier le lien

• Graphe simple: G = (V, E) avec |V| = n, |E| = m.
• Somme des degrés: additionner tous les degrés d’un graphe non orienté donne 2 · |E|.
• Matrice d’adjacence: une matrice binaire A de taille n × n où A[i][j] = 1 si l’arête (i, j) existe. La puissance A^k permet de compter les chemins de longueur k.
• Relaxation (plus courts chemins pondérés positifs): mettre à jour d(v) lorsque d(u) + w(u, v) est plus petit renforce l’invariant de Dijkstra/Bellman-Ford.
• Complexités: BFS/DFS = O(n + m); Dijkstra avec tas binaire coûte O((n + m) · log n).

#Exemple: comptage de chemins avec A^kCopier le lien

Soit un graphe non orienté à 4 sommets avec arêtes $E={(1,2),(1,3),(2,4),(3,4)}$. $A$ vaut:

10 1 1 021 0 0 131 0 0 140 1 1 0

On vérifie que $(A^2)_4=2$ (chemins de longueur 2 de 1 vers 4: 1→2→4 et 1→3→4).

#Questions types d’examenCopier le lien

• Parcours : prouver que BFS retourne un plus court chemin dans un graphe non pondéré (préciser l’invariant de distance). Variante : montrer que DFS détecte un cycle en couleurs.
• MST : justifier que l’algorithme de Kruskal ne crée jamais de cycle et qu’il termine avec $|V|-1$ arêtes.
• Topologie : expliquer pourquoi la présence d’un cycle dans un graphe orienté empêche l’existence d’un ordre topologique.
• Comptage : calculer le nombre de chemins de longueur $k$ entre deux sommets via la puissance de la matrice d’adjacence.

#Checklist « graphes » avant examenCopier le lien

• Distinguer clairement les graphes non orientés/orientés et pondérés/non pondérés.
• Savoir reconstruire un arbre BFS/DFS à partir d’un graphe et d’un sommet racine.
• Vérifier systématiquement les hypothèses de connexité ou de pondération positive.
• Citer l’invariant associé à chaque algorithme (frontal pour BFS, pile pour DFS, composantes pour Kruskal, clé minimale pour Prim).