Table des Matières
Cet aide-mémoire est conçu pour deux moments : la dernière heure avant un entretien technique, et le milieu d'une session de code quand vous connaissez la forme du problème mais qu'il vous faut l'outil exact. Il est volontairement compact. Pour toute l'histoire derrière chaque algorithme, suivez les liens vers les articles approfondis, et si vous voulez un parcours structuré à travers tout cela, commencez par la feuille de route de la théorie des graphes.
Tout au long, V est le nombre de sommets (nœuds) et E le nombre d'arêtes.
Le Grand Tableau de Complexité
La chose la plus utile à connaître par cœur. Les complexités supposent l'implémentation efficace standard (tas binaire pour Dijkstra et Prim, compression de chemin et union par rang pour union-find).
| Algorithme | Idéal pour | Temps | Espace |
|---|---|---|---|
| BFS | Plus court chemin dans les graphes non pondérés, parcours par niveaux | O(V + E) | O(V) |
| DFS | Connexité, cycles, exploration de la structure | O(V + E) | O(V) |
| Dijkstra | Plus court chemin, poids non négatifs | O((V + E) log V) | O(V) |
| Bellman-Ford | Plus court chemin avec poids négatifs | O(V · E) | O(V) |
| Floyd-Warshall | Plus courts chemins entre toutes les paires, petits graphes denses | O(V³) | O(V²) |
| A* | Plus court chemin heuristique (cartes, jeux) | O(E) typique | O(V) |
| Kruskal | Arbre couvrant minimal, graphes creux | O(E log E) | O(V) |
| Prim | Arbre couvrant minimal, graphes denses | O((V + E) log V) | O(V) |
| Topological Sort | Ordonner un DAG par dépendances | O(V + E) | O(V) |
| Union-Find | Connexité dynamique, regroupement | O(α(V)) par op. | O(V) |
| Tarjan / Kosaraju | Composantes fortement connexes | O(V + E) | O(V) |
| Edmonds-Karp | Flot maximum, coupe minimum | O(V · E²) | O(V + E) |
| Besoin du vrai code ? Ce tableau liste 12 essentiels en un coup d'œil. Le Manuel des algorithmes contient les 55, chacun avec le pseudocode et sa complexité détaillée étape par étape. | |||
Note sur A* : son temps d'exécution dépend entièrement de l'heuristique. Avec une heuristique parfaite, il va presque tout droit au but ; avec une inutile, il se dégrade en Dijkstra. Le α d'union-find est la fonction d'Ackermann inverse, en pratique une petite constante pour toute entrée que vous verrez jamais. Pour le raisonnement derrière chaque ligne, voir le guide de la complexité des algorithmes de graphes.
Représentations de Graphes
Avant tout algorithme, vous choisissez comment stocker le graphe. Cette seule décision influe sur chaque complexité ci-dessus.
| Représentation | Espace | Consultation d'arête | Idéal pour |
|---|---|---|---|
| Liste d'adjacence | O(V + E) | O(degree) | Graphes creux, le choix par défaut |
| Matrice d'adjacence | O(V²) | O(1) | Graphes denses, consultations en temps constant |
Règle empirique : prenez la liste d'adjacence sauf si le graphe est dense ou que vous avez besoin de tests d'arêtes en temps constant. Une grille 2D est un graphe implicite où chaque cellule est un nœud relié à ses voisines, si bien que vous n'avez souvent besoin d'aucune représentation explicite.
Parcours : BFS et DFS
Les deux algorithmes sur lesquels tout le reste repose. Apprenez la comparaison complète dans BFS vs DFS.
- BFS utilise une file, explore niveau par niveau et trouve le plus court chemin dans un graphe non pondéré. Mots-clés : plus court, pas minimum, plus proche, parcours par niveaux.
- DFS utilise une pile (souvent la pile d'appels de la récursion), plonge en profondeur et est idéal pour la connexité, la détection de cycles et le backtracking. Mots-clés : tous les chemins, accessibilité, régions, explorer.
Plus Courts Chemins
La famille la plus courante en entretien et en pratique. Le bon choix est dicté par les poids des arêtes. L'approfondissement complet est dans comprendre les algorithmes de plus courts chemins.
| Situation | Utiliser | Pourquoi |
|---|---|---|
| Arêtes non pondérées | BFS | La première arrivée est le plus court chemin |
| Poids non négatifs | Dijkstra | Glouton avec un tas-min, toujours correct ici |
| Poids négatifs | Bellman-Ford | Relâche les arêtes V-1 fois, détecte les cycles négatifs |
| Toutes les paires d'un coup | Floyd-Warshall | Trois boucles imbriquées, code minuscule, parfait sur les petits graphes |
| Vous avez une heuristique | A* | Dijkstra guidé vers le but, voir A* |
Le piège classique : n'exécutez jamais Dijkstra sur un graphe à arêtes négatives. Il fixe un nœud comme définitif trop tôt et peut renvoyer une réponse fausse. Prenez plutôt Bellman-Ford.
Arbres Couvrants Minimaux
Reliez chaque sommet au coût total d'arêtes le plus faible. Les deux algorithmes sont corrects ; choisissez selon la densité du graphe. Déroulés complets dans arbres couvrants minimaux.
- Kruskal : triez toutes les arêtes, ajoutez la moins chère qui ne forme pas de cycle, en utilisant union-find pour tester les cycles. Brille sur les graphes creux.
- Prim : faites croître un seul arbre vers l'extérieur, en ajoutant toujours l'arête la moins chère qui le quitte, avec une file de priorité. Brille sur les graphes denses.
Ordonnancement et Connexité
- Tri topologique (de Kahn ou fondé sur DFS) : produit un ordre linéaire d'un DAG pour que chaque arête pointe vers l'avant. L'outil des dépendances, de l'ordre de compilation et de l'ordonnancement. Impossible s'il existe un cycle, ce qui est justement la façon d'en détecter un.
- Union-Find (ensembles disjoints) : répond à "ces deux-là sont-ils dans le même groupe ?" et fusionne des groupes en temps quasi constant. L'épine dorsale de Kruskal et des problèmes de connexité dynamique.
- Composantes fortement connexes (Tarjan ou Kosaraju) : trouve les groupes maximaux où chaque nœud atteint tous les autres, dans un graphe orienté. Les deux s'exécutent en
O(V + E).
Les trois reviennent constamment en entretien. Voir les schémas résolus dans les algorithmes de graphes essentiels pour les entretiens de code.
Flot de Réseau
Modélisez le débit, le couplage et les goulots d'étranglement. Le résultat élégant ici est que le flot maximum égale la coupe minimum. Traitement complet dans le flot de réseau et le théorème flot-max coupe-min.
- Ford-Fulkerson : pousse à répétition du flot le long de chemins augmentants dans le graphe résiduel. Simple, mais son temps d'exécution dépend des valeurs de flot.
- Edmonds-Karp : Ford-Fulkerson qui trouve les chemins augmentants avec BFS, donnant une borne propre
O(V · E²)indépendante des capacités.
Quel Algorithme Utiliser ?
La façon la plus rapide d'utiliser cet aide-mémoire : lisez la colonne de gauche, sautez à droite.
| Si vous devez… | Prenez |
|---|---|
| Visiter ou explorer chaque nœud | BFS ou DFS |
| Trouver le plus court chemin dans un graphe non pondéré | BFS |
| Trouver le plus court chemin avec poids non négatifs | Dijkstra |
| Gérer des poids d'arêtes négatifs | Bellman-Ford |
| Obtenir les plus courts chemins entre toutes les paires | Floyd-Warshall |
| Trouver un chemin rapide avec une heuristique (cartes, jeux) | A* |
| Tout relier au coût minimum | Kruskal ou Prim |
| Ordonner des tâches selon leurs dépendances | Tri topologique |
| Vérifier si deux nœuds sont connectés, ou regrouper des éléments | Union-Find |
| Trouver des grappes dans un graphe orienté | Tarjan ou Kosaraju (SCC) |
| Maximiser le débit ou trouver un goulot d'étranglement | Edmonds-Karp (flot max) |
Transformez le tableau en intuition
Un aide-mémoire vous dit quel algorithme ; le voir tourner vous dit pourquoi. Parcourez l'un d'eux pas à pas sur un graphe en direct.
Ouvrir le visualiseur d'algorithmesFoire Aux Questions
Quelle est la complexité temporelle de l'algorithme de Dijkstra ?
Avec un tas binaire (file de priorité), l'algorithme de Dijkstra s'exécute en temps O((V + E) log V) et en espace O(V). Avec un simple tableau au lieu d'un tas, il est en O(V au carré), ce qui peut être plus rapide sur les graphes denses.
Quel algorithme de graphe utiliser pour les plus courts chemins ?
Cela dépend du graphe. Utilisez BFS pour les graphes non pondérés, Dijkstra pour les poids non négatifs, Bellman-Ford en présence de poids négatifs, Floyd-Warshall pour les plus courts chemins entre toutes les paires, et A* quand vous avez une bonne heuristique (cartes et jeux).
Faut-il utiliser une liste d'adjacence ou une matrice d'adjacence ?
Utilisez une liste d'adjacence pour les graphes creux : elle utilise O(V + E) espace et c'est le choix par défaut pour la plupart des problèmes. Utilisez une matrice d'adjacence pour les graphes denses ou quand vous avez besoin de consultations d'arêtes en O(1), au prix de O(V au carré) espace.
Quels algorithmes de graphes faut-il mémoriser pour les entretiens de code ?
Les cinq essentiels sont BFS, DFS, l'algorithme de Dijkstra, le tri topologique et union-find. Ensemble, ils couvrent la grande majorité des questions de graphes posées en entretien technique.