Liste des algorithmes de la théorie des graphes
Apparence
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)