Implémentation des graphes

Nous avons vu dans le cours sur les graphes, deux façons de représenter un graphe : par matrice d’adjacence ou par liste d’adjacence. Nous allons utiliser ces deux implémentations ici.

Matrice d’adjacence

Nous utiliserons le même graphe que le précédent :

1. Créez en Python la matrice d’adjacence de ce graphe.

2. (Dificile) Proposez une fonction matrice_largeur permettant de parcourir en largeur ce graphe. On utilisera une liste pour enregistrer les nœuds visités.

3. (Plus dificile) Proposez une fonction matrice_profondeur permettant de parcourir en profondeur ce graphe.

Liste d’adjacence

Nous utiliserons ici le même graphe que précédement.

4. Créez en Python les listes d’adjacence de ce graphe. (On utilisera un tableau à deux dimensions)

5. (Dificile) Proposez une fonction listes_largeur permettant de parcourir en largeur ce graphe. On utilisera une liste pour enregistrer les nœuds visités.

6. (Plus dificile) Proposez une fonction listes_profondeur permettant de parcourir en profondeur ce graphe.