Liste des algorithmes de la théorie des graphes
page de liste de Wikipédia
Cette page présente une liste non exhaustive des principaux algorithmes de la théorie des graphes.
Algorithmes de parcours d'un graphe
modifier- 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)
modifierAlgorithmes d'arbres couvrants de poids minimum
modifierLemme de Minty
modifierAlgorithmes pour les flots maximums
modifierAlgorithmes pour les flots à coût minimum
modifierAlgorithmes pour les flots compatibles
modifierAlgorithmes de coloration
modifier(voir coloration de graphe)
Algorithmes divers
modifier- 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)