Exercices

Exercice 1 : matrice d'adjacence et liste d'adjacence⚓︎

Question 1. Matrice d'adjacence

Donner la liste de listes représentant la matrice d'adjacence du graphe suivant :

Solution

[
[0, 1, 1, 1, 0, 0],
[1, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 0],
]

Question 2. liste d'adjacence avec dictionnaire

Compléter la fonction conversion_dico qui prend en paramètres une liste de listes m qui représente la matrice d'adjacence d'un graphe, et qui renvoie la liste d'adjacence correspondante, implémentée à l'aide d'un dictionnaire.

Par exemple, pour le graphe suivant :

>>> m = [[0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [0, 0, 0, 0]]
>>> conversion_dico(m)
{0: [1, 3], 1: [0, 2, 3], 2: [1], 3: []}
>>>

###

# Testsbksl-nlm = [[0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [0, 0, 0, 0]]bksl-nlassert conversionpy-unddico(m) == {0: [1, 3], 1: [0, 2, 3], 2: [1], 3: []}bksl-nlbksl-nl# Autres testsbksl-nlm2 = [[1, 0, 1, 0], [1, 0, 0, 0], [1, 1, 1, 0], [1, 1, 0, 1]]bksl-nlassert conversionpy-unddico(m2) == {0: [0, 2], 1: [0], 2: [0, 1, 2], 3: [0, 1, 3]}bksl-nlbksl-nl 5/5

def conversionpy-unddico(m):bksl-nl ...bksl-nlbksl-nl# Testsbksl-nlm = [[0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [0, 0, 0, 0]]bksl-nlassert conversionpy-unddico(m) == {0: [1, 3], 1: [0, 2, 3], 2: [1], 3: []}bksl-nlbksl-nldef conversionpy-unddico(m):bksl-nl g = {}bksl-nl for i in range(len(m)):bksl-nl g[i] = []bksl-nl for j in range(len(m[i])):bksl-nl if m[i][j] == 1:bksl-nl g[i].append(j)bksl-nl return gbksl-nl bksl-nl

Question 3. liste d'adjacence avec une liste

Compléter la fonction conversion_liste qui prend en paramètres une liste de listes m qui représente la matrice d'adjacence d'un graphe, et qui renvoie la liste d'adjacence correspondante, implémentée à l'aide d'une liste.

Par exemple, pour le graphe suivant :

>>> m = [[0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [0, 0, 0, 0]]
>>> conversion_liste(m)
[[1, 3], [0, 2, 3], [1], []]
>>>

###

# Testsbksl-nlm = [[0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [0, 0, 0, 0]]bksl-nlassert conversionpy-undliste(m) == [[1, 3], [0, 2, 3], [1], []]bksl-nlbksl-nl# Autres testsbksl-nlm2 = [[1, 0, 1, 0], [1, 0, 0, 0], [1, 1, 1, 0], [1, 1, 0, 1]]bksl-nlassert conversionpy-undliste(m2) == [[0, 2], [0], [0, 1, 2], [0, 1, 3]]bksl-nlbksl-nl 5/5

def conversionpy-undliste(m):bksl-nl ...bksl-nlbksl-nl# Testsbksl-nlm = [[0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [0, 0, 0, 0]]bksl-nlassert conversionpy-undliste(m) == [[1, 3], [0, 2, 3], [1], []]bksl-nlbksl-nldef conversionpy-undliste(m):bksl-nl liste = []bksl-nl for i in range(len(m)):bksl-nl liste.append([])bksl-nl for j in range(len(m[i])):bksl-nl if m[i][j] == 1:bksl-nl liste[i].append(j)bksl-nl return listebksl-nlbksl-nl

Exercice 2 : parcours en largeur⚓︎

parcours de graphe

Question

Donner la liste des sommets par parcours en largeur du graphe ci-dessus si le sommet de départ est B en conservant l'ordre alphabétique.

Solution

['B', 'A', 'D', 'E', 'C', 'F', 'G', 'H']

Question

Ecrire le code d'une fonction parcours_BFS qui parcourt en largeur un graphe à partir du sommet depart et dont sa liste d'adjacence graphe est representée par un dictionnaire nommé graphe

Cette fonction renverra la liste des sommets parcourus à partir du sommet depart.

Compléter le script ci-dessous, en ajoutant le test correspondant au graphe ci-dessus :

###

def parcourspy-undBFS(graphe, depart):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testbksl-nlmonpy-undgraphe = {"A":["B", "C"], "B":["A", "D", "E"], "C":["A", "D"],bksl-nl"D":["B", "C", "E"], "E":["B", "D", "F", "G"], "F":["E", "G"], "G":["E", "F", "H"],bksl-nl"H":["G"]}bksl-nlassert parcourspy-undBFS(monpy-undgraphe, "B") == ...bksl-nlprint("Bravo !")bksl-nlbksl-nl

Solution

Voir la leçon sur les parcours de graphes ... 😂

🐍 Script Python

# Test
mon_graphe = {"A":["B", "C"], "B":["A", "D", "E"], "C":["A", "D"],
"D":["B", "C", "E"], "E":["B", "D", "F", "G"], "F":["E", "G"], "G":["E", "F", "H"],
"H":["G"]}
assert parcours_BFS(mon_graphe, "B") == ['B', 'A', 'D', 'E', 'C', 'F', 'G', 'H']

Exercice 3 : parcours en profondeur⚓︎

parcours de graphe

Question

Donner une liste des sommets par parcours en profondeur du graphe ci-dessus si le sommet de départ est A.

Solution

['A', 'B', 'D', 'C', 'E', 'F', 'G', 'H']
['A', 'C', 'D', 'E', 'G', 'H', 'F', 'B']
et beaucoup d'autres possibilités ...

Question

Ecrire le code d'une fonction parcours_DFS qui parcourt en profondeur un graphe à partir du sommet depart et dont sa liste d'adjacence graphe est representée par un dictionnaire nommé graphe

Cette fonction renverra la liste des sommets parcourus à partir du sommet depart.

Compléter le script ci-dessous, en ajoutant le test correspondant au graphe ci-dessus :

###

def parcourspy-undDFS(...):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testbksl-nlmonpy-undgraphe = {"A":["B", "C"], "B":["A", "D", "E"], "C":["A", "D"],bksl-nl"D":["B", "C", "E"], "E":["B", "D", "F", "G"], "F":["E", "G"], "G":["E", "F", "H"],bksl-nl"H":["G"]}bksl-nlprint(parcourspy-undDFS(monpy-undgraphe, "A"))bksl-nlbksl-nlbksl-nl

Solution

Voir la leçon sur les parcours de graphes ... 😂