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[modifier | modifier le code]
- 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)[modifier | modifier le code]
- Algorithme de Dijkstra
- Algorithme de Dantzig
- Algorithme de Bellman-Ford-Moore
- Algorithme de Floyd-Warshall
- Algorithme de Johnson
- Algorithme A*
Algorithmes d'arbres couvrants de poids minimum[modifier | modifier le code]
Lemme de Minty[modifier | modifier le code]
Algorithmes pour les flots maximums[modifier | modifier le code]
Algorithmes pour les flots à coût minimum[modifier | modifier le code]
Algorithmes pour les flots compatibles[modifier | modifier le code]
Algorithmes de coloration[modifier | modifier le code]
(voir coloration de graphe)
Algorithmes divers[modifier | modifier le code]
- 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)
