Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

====== Algorithmiques sur les graphes ======

===Parcours en profondeur (DFS) récursif d'un graphe représenté par liste d'adjacence===
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.

<code python>
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
</code>