Parcours de graphes

Kézako ?

Un algorithme de parcours de graphe est un algorithme qui, partant d’un sommet \(s\) d’un graphe appelé source, explore tous les sommets ou tous les arcs accessibles depuis cette source, et aucun autre.

chaque sommet \(u\), hormis la source, est associé à un sommet prédécesseur \(\mathit{pred}(u)\) tel que \((\mathit{pred}(u), u)\) est un arc du graphe
il existe un entier \(\ell\) tel que \(\mathit{pred}^\ell(u) = s\)
ainsi, \(\mathit{pred}^\ell(u), \mathit{pred}^{\ell-1}(u), \ldots, \mathit{pred}(u), u\) est un chemin de \(s\) à \(u\)

Parcours de graphe permet de calculer tous les sommets accessibles depuis la source.

La fonction \(\mathit{pred}\) détermine une arborescence: un sous-ensemble d’arcs tel que chaque sommet possède un seul arc entrant sauf la source qui n’en a pas, et ne possédant pas de cycles.

Parcours générique : sommets parcourus et frontière

Structure de données insertion-extraction

Parcours générique

Parcours en largeur : file

Parcours en largeur : pseudo-code

Parcours en profondeur : pile

Parcours en profondeur : écriture récursive