Parcours dans un graphe

12.1. Parcours dans un graphe#

12.1.1. Parcours en profondeur#

def parcours(g, vus, s):
    if s not in vus:
        vus.add(s)
        for v in g.voisins(s):
            parcours(g, vus, v)

def existe_chemin(g, u ,v):
    vus = set()
    parcours(g, vus, u)
    return v in vus

12.1.2. Détection des cycles#

BLANC, GRIS, NOIR = 1, 2, 3

def parcours_cy(g, couleur, s):
    if couleur[s] == GRIS:
        return True
    if couleur[s] == NOIR:
        return False
    couleur[s] = GRIS
    for v in g.voisins(s):
        if parcours_cy(g, couleur, v):
            return True
    couleur[s] = NOIR
    return False

def cycle(g):
    couleur = {}
    for s in g.sommets():
        couleur[s] = BLANC
    for s in g.sommets():
        if parcours_cy(g, couleur, s):
            return True
    return False

12.1.3. Parcours en largeur#

def parcours(g, source):
    dist = {source: 0}
    courant = {source}
    suivant = set()
    while len(courant) > 0:
        s = courant.pop()
        for v in g.voisins(s):
            if v not in dist:
                suivant.add(v)
                dist[v] = dist[s] + 1
        if len(courant) == 0:
            courant, suivant = suivant, set()
    return dist

def distance(g, u, v):
    dist = parcours_largeur(g, u)
    return dist[v] if v in dist else None
Contenu