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) modifier
Algorithmes d'arbres couvrants de poids minimum modifier
Lemme de Minty modifier
Algorithmes pour les flots maximums modifier
Algorithmes pour les flots à coût minimum modifier
Algorithmes pour les flots compatibles modifier
Algorithmes 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)