Liste des algorithmes de la théorie des graphes
Cette page présente une liste non exhaustive des principaux algorithmes de la théorie des graphes.
Algorithmes de parcours d'un graphe
- Algorithme de parcours en largeur (ou BFS : Breadth First Search)
- Algorithme de parcours en profondeur (ou DFS : Depth First Search)
- Algorithme de parcours en largeur lexicographique (ou Lex-BFS)
Algorithmes de plus courts chemins (PCC)
- Algorithme de Dijkstra
- Algorithme de Dantzig
- Algorithme de Bellman-Moore
- Algorithme de Ford
- Algorithme de Floyd-Warshall
- Algorithme de Ford-Bellman
- Algorithme de Johnson
- Algorithme A*
Algorithmes d'arbres couvrants de poids minimum
Lemme de Minty
Algorithmes pour les flots maximums
Algorithmes pour les flots à coût minimum
Algorithmes pour les flots compatibles
Algorithmes de coloration
(voir coloration de graphe)
Algorithmes divers
- Algorithme du plus proche voisin
- Algorithmes de connexité
- Algorithme de détermination des composantes biconnexes
- Algorithmes de forte connexité
- Algorithme de Christofides pour l'approximation du problème du voyageur de commerce métrique
- Algorithme de Karger pour la coupe minimum (probabiliste)