Introduction
En théorie des graphes, un parcours de graphe est un algorithme consistant à explorer les sommets d'un graphe de proche en proche à partir d'un sommet initial.
Le mot parcours est également utilisé dans un sens différent, comme synonyme de chemin (un parcours fermé étant un circuit).
Algorithmes de parcours
Il existe de nombreux algorithmes de parcours. Les plus couramment décrits sont le parcours en profondeur et le parcours en largeur. L'algorithme de Dijkstra et l'algorithme de Prim font également partie de cette catégorie.
| Informatique théorique |
| Théorie du calcul | | Calculabilité | Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Récursivement énumérable | | Modèle de calcul | Automate fini • Automate cellulaire • Machine de Turing • Thèse de Church | | Modes de calcul | Concurrence • Parallèlisme • Théorie de l'ordonnancement | | Mesure et échelle de complexité | Réduction polynomiale • Problème NP-complet | |
| Logique, syntaxe et sémantique | | Logique mathématique | Assistant de preuve • Calcul des prédicats • Correspondance de Curry-Howard • Fonction récursive • Lambda-calcul • Théorème d'incomplétude de Gödel • Théorie des types | | Grammaire formelle et systèmes de réécriture | Compilation • Expression rationnelle • Grammaire formelle • Langage rationnel • Théorie des langages | | Sémantique | Sémantique des langages de programmation • Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle | | Spécifier, vérifier et concevoir des programmes | Interprétation abstraite • Méthodes formelles • Model checking | |
| Algorithmique, complexité et mathématiques discrètes | | Algorithmique | Algorithme génétique • Algorithme glouton • Algorithme probabiliste • Complexité algorithmique • Diviser pour régner • Heuristique • Programmation dynamique | | Problèmes et algorithmes numériques | Algorithme du simplexe • Géométrie algorithmique • Algorithme d'Euclide • Test de primalité | | Problèmes et algorithmes non-numériques | Algorithmes de la théorie des graphes • Arbre (structure de données) • Liste (informatique) • Table de hachage • Tas (informatique) | | Théorie des graphes | Coloration de graphe • Problèmes de cheminement | | Recherche opérationnelle | Optimisation • Optimisation combinatoire • Théorie de l'ordonnancement | | Données et codage | Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information | |
