Parcours de graphe | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

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. Un cas particulier important est le parcours d'arbre. Le mot parcours est également utilisé dans un sens différent, comme synonyme de chemin (un parcours fermé étant un circuit). 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. Les algorithmes de parcours n'ont pas une finalité intrinsèque. Ils servent comme outil pour étudier une propriété globale du graphe, comme la connexité ou la forte connexité ou l'existence d'un point d'articulation. Un parcours d'un graphe est un procédé qui permet de choisir, à partir des sommets visités, le sommet suivant à visiter. Le problème consiste à déterminer un ordre sur les visites des sommets. Une fois le choix fait, l’ordre des visites induit une numérotation des sommets visités (l'ordre de leur découverte) et un choix sur l'arc ou l’arête utilisé pour atteindre un nouveau sommet à partir des sommets déjà visités. Les arcs ou arêtes distingués forment une arborescence ou un arbre, et les numéros des sommets sont croissants sur les chemins de l’arborescence ou les chaînes de l'arbre depuis la racine. Les algorithmes de parcours servent dans la résolution d'un certain nombre de problèmes parmi lesquels : connexité et forte connexité ; existence d'un circuit ou d'un cycle (ce qu'on appelle tri topologique) ; calcul des plus courts chemins (notamment l'algorithme de Dijkstra) ; calcul d'un arbre recouvrant (notamment l'algorithme de Prim) ; algorithmes pour les flots maximaux (comme l'algorithme de Ford-Fulkerson). Pour la réalisation d'un parcours, il est en général nécessaire de mémoriser quels sont les sommets déjà explorés par l'algorithme, de sorte de ne pas répéter une visite d'un sommet déjà exploré.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Personnes associées (1)

Concepts associés (7)

Cours associés (6)

Séances de cours associées (48)

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

CS-448: Sublinear algorithms for big data analysis

In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data

CS-460: Systems for data management and data science

This course is intended for students who want to understand modern large-scale data analysis systems and database systems. The course covers fundamental principles for understanding and building syste

vignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité.

L'algorithme de parcours en largeur (ou BFS, pour Breadth-First Search en anglais) permet le parcours d'un graphe ou d'un arbre de la manière suivante : on commence par explorer un nœud source, puis ses successeurs, puis les successeurs non explorés des successeurs, etc. L'algorithme de parcours en largeur permet de calculer les distances de tous les nœuds depuis un nœud source dans un graphe non pondéré (orienté ou non orienté). Il peut aussi servir à déterminer si un graphe non orienté est connexe.

Explore les méthodes de traversée des graphes, les arbres couvrants et les chemins les plus courts en utilisant BFS et DFS.

Couvre les algorithmes graphiques, la modélisation des relations entre les objets et les techniques de traversée telles que BFS et DFS.

Explore des algorithmes de graphes comme BFS et DFS, en discutant des chemins les plus courts, des arbres couvrants et du rôle des structures de données.