Parcours en profondeur de graphe

Dans cet exercice, on considère un graphe non orienté représenté sous forme de listes d’adjacence. On suppose que les sommets sont numérotés de 0 à n-1.

Ainsi, le graphe suivant:

sera représenté par la liste d’adjacence suivante:

adj = [[1, 2], [0, 3], [0], [1], [5], [4]]

On souhaite déterminer les sommets accessibles depuis un sommet donné dans le graphe. Pour cela, on va procéder à un parcours en profondeur du graphe.

Compléter les fonctions parcours et accessibles.

• La fonction parcours prend en paramètres une liste d'adjacence liste_adjacence, un entier x représentant un sommet, et la liste des sommets accessibles sommets_accessibles Elle réalise un parcours en profondeur récursif du graphe donné par les listes d'adjacence adjacence depuis le sommet x en accumulant les sommets rencontrés dans la liste sommets_accessibles

• La fonction accessibles prend en paramètres une liste d'adjacence liste_adjacence, un entier x représentant un sommet.
  Elle renvoie la liste des sommets accessibles dans le graphe donné par la listes d'adjacence liste_adjacence depuis le sommet x

Exemples

Bug

Attention, les exemples donnés correspondent à un graphe orienté qui n'est pas celui représenté dans le sujet.

🐍 Console Python

>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 0)
[0, 1, 2, 3]
>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 4)
[4, 5]

Compléter le code ci-dessous

###

Lancer # Testsbksl-nlbksl-nlassert accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 0) == [0, 1, 2, 3] # orienté erreur sujetbksl-nlassert accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 4) == [4, 5] # orienté erreeur du sujetbksl-nlbksl-nl# Autres testsbksl-nlbksl-nlassert accessibles([[1, 2], [2], [0], [0]], 0) == [0, 1, 2]bksl-nlassert accessibles([[1, 2], [0, 3], [0,], [1], [5], [4]], 0) == [0, 1, 3, 2] # non orientébksl-nlassert accessibles([[1, 2], [0, 3], [0,], [1], [5], [4]], 4) == [4, 5] # non orientébksl-nlbksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def parcours(adjacence, x, sommetspy-undaccessibles):bksl-nl if x ...: bksl-nl sommetspy-undaccessibles.append(x)bksl-nl for y in ...: bksl-nl parcours(adjacence, ...) bksl-nlbksl-nldef accessibles(adjacence, x):bksl-nl sommetspy-undaccessibles = []bksl-nl parcours(adjacence, ...) bksl-nl return sommetspy-undaccessiblesbksl-nlbksl-nlbksl-nl# Testsbksl-nlbksl-nlassert accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 0) == [0, 1, 2, 3] # graphe orienté erreur sujetbksl-nlassert accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 4) == [4, 5] # graphe orienté erreur du sujetbksl-nlassert accessible([[1, 2], [0, 3], [0,], [1], [5], [4]], 0) == [0, 1, 3, 2] # graphe non orientébksl-nlassert accessible([[1, 2], [0, 3], [0,], [1], [5], [4]], 4) == [4, 5] # graphe non orientébksl-nlbksl-nldef parcours(adjacence, x, sommetspy-undaccessibles):bksl-nl if x not in sommetspy-undaccessibles: bksl-nl sommetspy-undaccessibles.append(x)bksl-nl for y in adjacence[x]: bksl-nl parcours(adjacence, y, sommetspy-undaccessibles) bksl-nlbksl-nldef accessibles(adjacence, x):bksl-nl sommetspy-undaccessibles = []bksl-nl parcours(adjacence, x, sommetspy-undaccessibles) bksl-nl return sommetspy-undaccessiblesbksl-nlbksl-nlbksl-nl

---

---