C12.2 : Implémentation des graphes
Implémentation sous forme d'une matrice d'adjacence
Présentation
Une implémentation possible d'un graphe est une matrice carrée (c'est-à-dire un tableau comprenant autant de lignes que de colonnes) que l'on appelle matrice d'adjacence.
Les colonnes (comme les lignes) correspondent aux nœuds.
L'intersection entre une ligne est une colonne correspond à l'arc entre les nœuds correspondants. La cellule contient 0 si les nœuds ne sont pas reliés et 1 dans le cas contraire.
Exemple
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 |
| B | 0 | 0 | 1 | 1 |
| C | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 |
Application (sur papier)
1) Représenter les matrices des graphes n° 1, n° 2 et n° 3.
2) Comment peut-on obtenir simplement le nombre de voisins d'un nœud à partir de la matrice d'adjacence ?
3) De quelle façon peut-on implémenter une matrice d'adjacence en Python ?
Un peu de python
Dans cette partie on travaillera avec des matrices implémentées par des listes de listes. Les nœuds d'un graphe seront identifiés par un nombre entier allant de 0 à n-1, n étant la taille du graphe.
Application I.3_app1
Compléter la fonction suivante :
def nb_successeurs(matrice, noeud):
'''
Fonction qui, à partir d'un graphe représenté par une matrice d'adjacence, renvoie :
- le nombre de voisins de noeud si le graphe n'est pas orienté,
- le nombre de successeurs de noeud si le graphe est orienté.
Paramètres
matrice (liste) : liste de liste représentant la matrice d'adjacence d'un graphe
noeud (int) : entier correspondant à un nœud du graphe
Valeur renvoyée
return (int) : nombre entier correspondant au nombre de voisins
'''
passApplication I.3_app2
Compléter la fonction suivante :
def sont_lies(matrice, noeud1, noeud2):
'''
Fonction qui permet de savoir si deux nœuds d'un graphe sont liées
Paramètres
matrice : (liste) liste de liste représentant la matrice d'adjacence d'un graphe
noeud1 : (int) entier correspondant à un nœud du graphe
noeud2 : (int) entier correspondant à un nœud du graphe
Valeur renvoyée
return (bool) : True si les deux nœuds sont liés et False sinon
'''
passImplémentation sous forme d'une liste d'adjacences ou d'un dictionnaire d'adjacences
Présentation
Il est possible d'implémenter les graphes sous forme :
- - d'une liste d'adjacence : liste dont chaque élément correspond à un nœud et est une liste des voisins (des successeurs ou des prédécesseurs) de ce nœud,
- - d'un dictionnaire d'adjacence : dictionnaire dont les clés sont les étiquettes des nœuds et les valeurs les listes des voisins (des successeurs ou des prédécesseurs) du nœud.
Exemple de dictionnaires d'adjacences
{
"A" : ["B", "C", "D"],
"B" : ["C", "D"],
"C" : [],
"D" : []
}
Dictionnaire des listes de successeurs
{
"A" : [],
"B" : ["A"],
"C" : ["A", "B"],
"D" : ["A", "B"]
}
Dictionnaire des listes de prédécesseurs
Applications
Application II.2_app1
1) Représenter les dictionnaires d'adjacences (successeurs si le graphe est orienté) des graphes n°1, n°2 et n°3.
Application II.2_app2
En python, écrire une fonction qui prend en paramètre un graphe sous la forme d'un dictionnaire des listes de successeurs et renvoie un dictionnaire dont les clés sont les nœuds et les valeurs le nombre de voisins des nœuds.
Application II.2_app3
En python, écrire une fonction qui prend en paramètre un graphe sous la forme d'un dictionnaire des listes de successeurs et renvoie le même graphe sous la forme d'un dictionnaire des listes de prédécesseurs.
Conversion d'une implémentation à une autre
Dans cette partie, on travaillera avec des graphes orientés dont les nœuds ont les valeurs de 0 à n-1, n étant la taille du graphe.
Application III_app1
Écrire une fonction qui prend en paramètre un graphe sous la forme d'un dictionnaire des listes de successeurs et renvoie le même graphe sous la forme d'une matrice d'adjacence.
Application III_app2
Écrire une fonction qui prend en paramètre un graphe sous la forme d'une matrice d'adjacence et renvoie le même graphe sous la forme d'un dictionnaire des listes de successeurs.