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-Ford-Moore
- Algorithme de Floyd-Warshall
- Algorithme de Johnson
- Algorithme A*
Algorithmes d'arbres couvrants de poids minimum
- Algorithme de Kruskal
- Algorithme de Prim
- Algorithme de Borůvka
Lemme de Minty
- Lemme de Minty
Algorithmes pour les flots maximums
- Algorithme de Ford-Fulkerson
Algorithmes pour les flots à coût minimum
- Algorithme de Busacker et Gowen
- Algorithme de Klein
Algorithmes pour les flots compatibles
- Algorithme de recherche de 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)
- Portail de l'informatique théorique