Le parcours en profondeur (Depth First Search, ou DFS) permet d'explorer un graphe en allant le plus loin possible sur chaque chemin avant de revenir en arrière. On utilise un ensemble (ou une liste) pour mémoriser les sommets déjà visités, afin de ne pas les visiter plusieurs fois et éviter une boucle infinie.

graphe = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
}
 
def parcours_profondeur(graphe, sommet, visites=None):
    """
    Objectif :
    Parcourt un graphe en profondeur (DFS) de façon récursive à partir d'un sommet donné.
    Entrée :
    graphe  : dict : le graphe représenté par une liste d'adjacence
    sommet  : str : le sommet de départ du parcours
    visites : set ou None : l'ensemble des sommets déjà visités (initialisé automatiquement si absent)
    Sortie :
    visites : set : l'ensemble des sommets visités à l'issue du parcours
    """
    if visites is None:  #premier appel de la fonction : on crée l'ensemble des sommets visités
        visites = set()
 
    if sommet not in visites:  #on ne visite le sommet que s'il n'a pas déjà été visité
        visites.add(sommet)
        print(sommet)
        for voisin in graphe[sommet]:  #on explore chaque voisin du sommet
            parcours_profondeur(graphe, voisin, visites)
 
    return visites
 
parcours_profondeur(graphe, "A")  #affiche successivement A, B, D, C