31 - graphe et liste
1 - Rappels sur la matrice d'adjacence
Sans rentrer dans tous les détails de l'activité précédente, voici un petit résumé des matrices d'adjacence :
Matrice d'adjacence d'un graphe non orienté
Il suffit d'identifier chaque sommet par un numéro et on indique dans la matrice
- l'existence d'une arête entre le sommet i et le sommet j en plaçant mij = 1
- l'absence d'une arête entre le sommet i et le sommet j en plaçant mij = 0
Avantages et désavantages de la matrice d'adjacence
Avantages
- Simple à utiliser
- Savoir si un arc ou une arête existe est une action à coût constant (Θ(1))
Désavantages
- Place mémoire dont le coût est quadratique (Θ(n2)), n étant le nombre de sommets, la taille du graphe.
- Enumérer les arcs sortant d'un sommet est à coût linéaire (Θ(n)) même si la matrice est peu dense : il faut lire toutes les colonnes (alors qu'elles contiennent surtout des 0...)
La matrice d'adjacence est donc principalement utilisée :
- Sur les matrices denses (un sommet mène à la plupart des autres sommets)
- Lorsqu'on désire très souvent connaître l'existence d'une arête entre deux sommets
2 - Listes
La liste
Une liste est un type abstrait de données dans laquelle :
- Les éléments forme une suite ordonnée d'éléments
- Le premier élément se nomme la tête (le 5 de l'exemple)
- La suite des éléments derrière la tête se nomme la queue (8, 2 et 3 ci-dessous)
- Exemple : 5 → 8 → 2 → 3
La liste doit être pourvue d'un certain nombre de fonctions d'interface (ou primitives) permettant de la définir en tant que liste :
Fonctions d'interface
Description de l'interface du type abstrait Liste
On nomme également ces fonctions d'interfaces les primitives.
nouvelleListe(): on crée une nouvelle liste vide.estVide(lst): renvoie un booléen qui vaut True si la liste lst transmise est une liste vide.inserer(elt, lst): on ajoute l'élément elt dans la liste lst. Plusieurs versions sont possibles : on insère uniquement une tête, on insère à la position du curseur, on insère à n'importe quelle position ou bien encore d'autres possibilités...supprimer(lst et + ?): on supprime un élément de la liste lst. Encore une fois, il existe plusieurs versions : uniquement la tête, une position fournie ou l'élément pointé par un curseur.lire(lst et + ?): on lit le contenu d'un élément précis de la liste : tête, position fournie ou pointée par un curseur.
Tous les types de données qui collent à la définition et qui possèdent des fonctions similaires sont donc des listes.
Implémentations courantes
On implémente souvent les listes sous trois formes :
- La forme p-uplet (tête, queue) : on retrouve alors une structure de données proches de celles des piles. On a une implémentation facile à comprendre mais
- la lecture et la modification sont à coût linéaire dans le pire des cas
- le rajout et la suppression est à coût linéaire dans le pire des cas
- la concaténation de deux listes à coût linéaire
- Nous avions l'exemple suivant : 5 → 8 → 2 → 3 qui peut donc être vu comme des couples tête-queue imbriqués les uns dans les autres :
- Cette structure de données est souvent implémentée à partir de tuples de deux éléments : la tête et la queue
- La forme liste contiguë : on utilise un tableau statique où les "cases" sont réellement les unes derrière les autres en mémoire :
- la lecture et la modification sont à coût constant dans le pire des cas
- le rajout et la suppression est à coût linéaire dans le pire des cas
- la concaténation de deux listes à coût linéaire
- Nous avions l'exemple suivant : 5 → 8 → 2 → 3 qui peut donc être vu comme les cases d'un tableau statique :
- Cette structure de données est souvent implémentée à partir de tableaux dont les éléments sont ceux de la lise.
- La forme liste chaînée : on utilise une succesion de cellules qui contiennent la référence de la cellule suivante :
- la lecture et la modification sont à coût linéaire dans le pire des cas
- le rajout et la suppression est à coût constant dans le pire des cas (sous condition d'avoir déjà la référece de la cellule en mémoire quand même)
- la concaténation de deux listes à coût constant (sous conditions d'avoir en mémoire la référence de la dernière cellule de la première liste)
- Nous avions l'exemple suivant : 5 → 8 → 2 → 3 qui peut donc être vu comme des cellules "valeur-suivant" qui permettent de trouver la cellule suivante :
- Cette forme de structure de données est souvent implémentée à partir d'objets-cellules dont les attributs sont la valeur et la référence de la cellule suivante.
3 - Listes d'adjacence
Alors qu'est-ce qu'une liste d'adjacence d'un graphe ?
Liste d'adjacence
L'adjectif "adjacent" appliqué des sommets indique que les deux sommets sont reliés par une arête. On dit également qu'ils sont voisins.
Une liste d'adjacence est un moyen de représenter un graphe G = (S, A).
On associe pour cela à chaque sommet une liste dont les éléments sont composés des sommets voisins (ou adjacents).
On voit que :
- le sommet d'étiquette a possède deux voisins b et c.
- le sommet d'étiquette b possède deux voisins a et c.
- le sommet d'étiquette c possède trois voisins a, b et d.
- le sommet d'étiquette d possède un seul voisin c.
On a 4 sommets, nous allons donc avoir besoin de 4 listes d'adjacence en première approche.
- Liste d'adjacence du sommet a ---- b → c
- Liste d'adjacence du sommet b ---- a → c
- Liste d'adjacence du sommet c ---- a → b → d
- Liste d'adjacence du sommet d ---- c
Deux remarques
- La liste d'adjance d'un sommet est au maximum de n-1 éléments si n est le nombre de sommets. C'est mieux qu'avec la matrice puisque chaque ligne était composée nécessairement de n éléments.
- Ce ne sont pas nécessairement de vraies listes ordonnées au sens informatique : les éléments n'ont pas d'ordre à respecter et la tête n'a pas à être particulièrement associé avec un élément plutôt qu'un autre. Il existe donc plusieurs versions possibles de la liste d'adjacence du sommet c.
- Liste valable : a → b → d
- Liste valable : a → c → d
- Liste valable : b → a → d
- Liste valable : b → d → a
- Liste valable : d → b → a
- Liste valable : d → a → b
- Ordonner les sommets et créer les listes d'adjacences selon cet ordre présente un avantage néanmoins. Cela permet de gagner du temps : si on cherche un voisin b et qu'on arrive à c dans la liste, on sait qu'on peut arrêter la recherche de b si les voisins sont ordonnés dans la liste d'adjacence : a, b, c, d
- Liste d'adjacence du sommet a ---- b → c
- Liste d'adjacence du sommet b ---- a → c
- Liste d'adjacence du sommet c ---- a → b → d
- Liste d'adjacence du sommet d ---- c
Comme la tête n'a pas réellement de sens, on pourrait la représenter de cette façon :
01° A quoi correspond le nombre d'éléments dans la liste d'adjacence d'un sommet ?
- Liste d'adjacence du sommet a ---- b → c
- Liste d'adjacence du sommet b ---- a → c
- Liste d'adjacence du sommet c ---- a → b → d
- Liste d'adjacence du sommet d ---- c
...CORRECTION...
Cela correspond à son nombre d'arêtes, et donc à son nombre de voisins ou sommets adjacents.
02° Fournir les listes d'adjacences des sommets :
...CORRECTION...
- Liste d'adjacence du sommet 1 ---- 2 → 3 → 4
- Liste d'adjacence du sommet 2 ---- 1 → 3
- Liste d'adjacence du sommet 3 ---- 1 → 2
- Liste d'adjacence du sommet 4 ---- 1 → 5 → 6
- Liste d'adjacence du sommet 5 ---- 4
- Liste d'adjacence du sommet 6 ---- 4
Nous avions travaillé avec un bout simplifié de ce plateau Pacman dans l'activité précédente.
Le graphe simplifié est alors :
03° Fournir les listes d'adjacences des différents sommets.
- Liste d'adjacence du sommet 1 ----
- Liste d'adjacence du sommet 2 ----
- Liste d'adjacence du sommet 3 ----
- Liste d'adjacence du sommet 4 ----
- ...
...CORRECTION...
- Liste d'adjacence du sommet 1 ---- 2 → 3 → 5
- Liste d'adjacence du sommet 2 ---- 1 → 3 → 4 → 6
- Liste d'adjacence du sommet 3 ---- 1 → 2 → 4
- Liste d'adjacence du sommet 4 ---- 2 → 3 → 67
- Liste d'adjacence du sommet 5 ---- 1 → 9
- Liste d'adjacence du sommet 6 ---- 2 → 7 → 8
- Liste d'adjacence du sommet 7 ---- 4 → 6
- Liste d'adjacence du sommet 8 ---- 6 → 9
- Liste d'adjacence du sommet 9 ---- 5 → 8
Vos listes contiennent donc la même information que la matrice d'adjacence correspondante :
4 - Implémentation des sommets
Il reste donc à se demander comment stocker tout cela de façon théorique. Nous allons voir qu'il existe de multiples façons d'implémenter la liste d'adjacence mais également son lien avec les sommets.
On ne se préoccupera pas vraiment de savoir comment on stocke réellement les informations sur les sommets. Dans tous les cas, nous allons avoir besoin d'un mécanisme qui permettra de faire le lien entre un sommet à sa liste d'adjacence.
Imaginons qu'on veuille encoder ceci qui pourrait être la carte d'un donjon contenant des monstres et des trésors à récupérer :
Sommet en tant que tuple
Nous pourrions utiliser des tuples où l'indice 0 serait l'étiquette de la salle-sommet et l'indice 1 un autre tuple qui contiendrait les informations sur la salle-sommet :
1
2
3
4
5
6
7
8 | |
04° Que ramène l'évaluation de a[1][3] ?
...CORRECTION...
Voici a : ("A", ("Salle de garde", 6, "Gobelin", 100)), un tuple de deux éléments.
Voici a[1] : ("Salle de garde", 6, "Gobelin", 100), un tuple de 4 éléments.
Voici a[1][3] : 100
Sommet en tant que dictionnaire
Nous pourrions utiliser des dictionnaires où chaque clé correspondrait à une information sur le sommet ou la salle :
1
2
3
4
5
6
7
8 | |
05° Que ramène l'évaluation de b["tresor"] ?
...CORRECTION...
Voici b : {"etiquette": "B", "nom": "Antre du Dragon", "nb": 1, "monstre": "Dragon", "tresor": 2000}, un dictionnaire.
Demander b["tresor"] veut donc dire de ramener la valeur associée à la clé "tresor".
On obtient donc 2000.
Sommet en tant qu'objet
Nous pourrions utiliser des objets où chaque attribut correspondrait à une information sur le sommet ou la salle :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | |
06° Que ramène l'évaluation de c.tresor ?
...CORRECTION...
La variable c fait référence à une instance de Salle
Demander c.tresor veut donc dire de ramener la valeur attribuée à l'attribut associée tresor de l'objet "c".
On obtient donc 200.
Comment mettre en mémoire l'ensemble des salles sans se soucier de l'implémentation des sommets ? Le plus simple est de créer un tableau de références qu'on pourrait nommer sommets.
1 | |
Maintenant, on voit que la salle 0 fait référence à a par exemple.
07° Quelle est la variable-salle dont l'indice dans le tableau sommets est 2 ?
...CORRECTION...
Il s'agit de c
- 0 -- a
- 1 -- b
- 2 -- c
- 3 -- d
5 - Implémentation des listes d'adjacence avec des tableaux (ou listes contiguës)
Nous avons vu qu'il y avait beaucoup de façons d'implémenter les sommets. C'est la même chose pour les listes d'adjacences. Nous allons décrire quelques implémentations courantes.
Commençons par une implémentation qui nécessite d'avoir associer un numéro à chaque sommet. Comme avec ceci :
1 | |
Nous avions vu qu'avec notre donjon d'exemple, les listes d'adjacence des salles a, b, c et d étaient :
- Liste d'adjacence du sommet a ---- b → c
- Liste d'adjacence du sommet b ---- a → c
- Liste d'adjacence du sommet c ---- a → b → d
- Liste d'adjacence du sommet d ---- c
En passant aux numéros,et en utilisant un simple tableau d'entiers en tant que liste d'adjacence, on obtient alors ceci :
- Liste d'adjacence du sommet 0 ---- 1 → 2
- Liste d'adjacence du sommet 1 ---- 0 → 2
- Liste d'adjacence du sommet 2 ---- 0 → 1 → 3
- Liste d'adjacence du sommet 3 ---- 2
Si on décide d'utiliser de simples tableaux en tant que liste (on utilise donc des listes contiguës), nous obtenons alors une représentation qui ressemble à ceci :
En Python, cela pourrait donner :
1
2
3
4
5
6
7 | |
Avantage par rapport à la matrice d'adjacence : les listes d'adjacence ne contiennent que les informations sur les sommets adjacents. Elles prennent donc moins de place.
Désavantage par rapport à la matrice d'adjacence : le numéro du sommet dans la liste d'adjacence n'a aucune raison d'être le même que le numéro du sommet dans le tableau sommets. A titre d'exemple, ligne 7, le sommet 2 apparaît à l'indice 0 dans la dernière liste d'adjacence.
08° Dans le pire des cas (l'arête n'existe pas), quel est le coût d'une recherche d'arête entre deux sommets connus dans le cadre d'un encodage par liste d'adjacence ? Fournir une justification.
- Constant : Θ(1)
- Logarithmique : Θ(log n)
- Linéaire : Θ(n)
- Quasi-linénaire : Θ(n log n)
Pour rappel, le coût est constant dans le cas d'une matrice d'adjacence.
...CORRECTION...
Il va falloir lire les éléments de la liste d'adjacence un par un jusqu'à trouver, ou pas, le sommet voulu.
Le coût de la recherche d'arête est donc linéaire avec une liste d'adjacence.
On voit donc que :
- Matrice d'adjacence : coût constant pour la recherche d'arête mais coût quadratique en mémoire pour stocker la matrice
- Liste d'adjacence sous forme de liste contiguë : coût linéaire pour la recherche d'arête mais le coût en mémoire est beaucoup plus faible.
Mais selon les problèmes, la liste d'adjacence d'un sommet peut avoir une taille limitée. Prenons le cas de PacMan :
Si on crée un graphe où chaque sommet est bien un point (et pas une zone comme dans la version simplifiée précédente), chaque sommet ne peut avoir au pire que 4 voisins : en haut, en bas, à gauche, à droite.
Cette fois, quelque soit le nombre de cases sur le plateau, chaque liste d'adjacence à au pire une longueur de 4 !
09° Dans le cadre du jeu Pacman, quel est le coût dans le pire des cas de cette recherche d'existence d'arête entre deux sommets connus ? Fournir une justification.
- Constant : Θ(1)
- Logarithmique : Θ(log n)
- Linéaire : Θ(n)
- Quasi-linénaire : Θ(n log n)
...CORRECTION...
Dans le pire des cas, il faudra faire 4 recherches. On obtient donc un coût constant. Quatre fois plus d'opérations que dans le cadre d'une matrice d'adjacence où il suffit de lire le contenu de la bonne case, mais 4 opérations quelque soit le nombre réel de cases du plateau.
Le coût de l'opération est donc indépendant du nombre de cases.
Le coût est constant sur ce cas particulier du Pacman.
10° Si le jeu évolue en cours de travail, quel va être le coût d'une suppression ou d'un ajout d'une nouvelle arête entre deux sommets si on utilise des tableaux statiques (listes contiguës) pour répresenter les listes d'adjacences ?
- Constant : Θ(1)
- Logarithmique : Θ(log n)
- Linéaire : Θ(n)
- Quasi-linénaire : Θ(n log n)
...CORRECTION...
Un tableau statique possède un nombre fixé d'éléments.
Nous avions vu lors de l'implémentation des listes que supprimer un élément oblige à déplacer les éléments de façon à ce qu'il n'y ai pas de trou dans le tableau.
Ici, la supression est donc à coût linéaire dans la cadre d'un graphe quelconque.
Remarque : dans le cadre du Pacman, on retrouve des listes d'au maximum 4 éléments et donc on retrouve un coût constant (mais 4 fois plus néanmoins qu'avec une matrice).
Bilan de la liste d'adjacence sous forme de tableaux statiques
- Avantage 1 : Facile à mettre en oeuvre
- Avantage 2 : Gain de place mémoire par rapport à une matrice si la matrice correspondante est plutôt creuse (comporte peu d'arêtes)
- Désavantage 1 : Supprimer ou rajouter une arête est à coût linéaire dans le pire des cas
- Désavantage 2 : on perd l'intérêt des tableaux à savoir pouvoir atteindre à coût constant une case particulière. Autant utiliser les listes chaînées non ?
Il existe également une variante de cette implémentation où il n'existe que deux tableaux faisant office de listes d'adjacence et pas autant de listes d'adjacence que de sommets :
- Un tableau debut_fin qui contient l'indice permettant de savoir où commencer la recherche des adjacents et
- un tableau adjacents qui contient la concaténation de toutes les listes précédentes.
1
2
3
4
5 | |
Regardons comment trouver la liste d'adjacence du sommet b.
On voit dans sommets que b est le sommet d'indice 1.
On lit alors debut_fin[1] pour trouver le début de notre liste d'adjacence : l'indice 2.
On lit alors debut_fin[2] pour trouver le début de la prochaine liste d'adjacence : l'indice 4.
On en déduit que la liste d'adjacence de b est composé des indices 2 et 3 du tableau adjacents.
A titre de comparaison, voici la version un tableau pour chaque liste d'adjacence :
1
2
3
4
5 | |
6 - Implémentation des listes d'adjacence avec des listes chaînées)
Puisqu'on perd l'avantage de l'accès direct aux éléments en utilisant des tableaux statiques, autant passer par des listes chaînées. L'ensemble sera donc plus lourd à coder SI le langage ne possède pas de types natifs permettant de les gérer. C'est donc ennuyeux avec Python mais ce défaut n'apparaît pas dans les langages où les listes chainées sont naturellement présentes de base.
Cette partie ne sera pas faite avec Python : il faudrait importer l'une des nos anciennes implémentations et l'utiliser. Nous verrons comment réaliser une liste d'adjacence avec Python dans la prochaine partie justement.
Nous allons donc réfléchir sur les avantages de cette méthode de façon théorique.
Nous travaillons toujours avec ce graphe :
Et voici la représentation des arêtes sous forme de listes d'adjacence implémentées sous forme de listes chaînées cette fois.
11° Dans le pire des cas, quel est le coût de la recherche d'une arête entre deux sommets connus avec cette implémentation ?
- Constant : Θ(1)
- Logarithmique : Θ(log n)
- Linéaire : Θ(n)
- Quasi-linénaire : Θ(n log n)
...CORRECTION...
Il s'agit d'une liste chaînée : on part de la tête et on doit ensuite suivre la chaîne en passant progressivement par toutes les cellules jusqu'à tomber sur la bonne.
Le coût est donc linéaire.
12° On désire transformer le graphe en rajoutant une arête entre le sommet a et le sommet d. On la rajoute au début de la liste d'adjacence. Quel est le coût de cette opération si on connaît la référence de la tête ?
- Constant : Θ(1)
- Logarithmique : Θ(log n)
- Linéaire : Θ(n)
- Quasi-linénaire : Θ(n log n)
...CORRECTION...
Il s'agit juste de un modifications : faire pointer l'ancienne dernière cellule vers la nouvelle cellule (3).
13° On désire transformer le graphe en rajoutant une arête entre le sommet a et le sommet d. On la rajoute à la fin de la liste d'adjacence. Quel est le coût de cette opération si on connaît la référence de la dernière cellule de la liste d'adjacence ?
- Constant : Θ(1)
- Logarithmique : Θ(log n)
- Linéaire : Θ(n)
- Quasi-linénaire : Θ(n log n)
...CORRECTION...
Il s'agit juste de faire deux modifications :
- Faire pointer la nouvelle cellule (3) vers l'ancienne tête (1)
- Faire pointer la référence de la liste vers la nouvelle tête (3)
Le coût est donc constant. Avec un tableau statique, le coût aurait été linéaire.
14° Voici un graphe non orienté possèdant des boucles. Fournir les listes d'adjacences qui permettraient de le représenter correctement.
On utilisera juste les numéros des sommets. Début de la rédaction :
...CORRECTION...
7 - Graphe orienté
Et sur les graphes orientés ?
L'une des solutions est de créer deux listes :
- La liste des successeurs pour les arcs sortants
- La liste des prédécesseurs pour les arcs entrants
Changeons de thème et partons vers les graphes permettant de représenter un ensemble de routes, certaines étant à sens unique :
Cette fois, il faut donc définir deux listes.
Commençons par liste des successeurs : on voit qu'il n'y a que les arcs (a,b) et (a,d) en sortie du sommet a.
- Liste des successeurs du sommet a ---- b → d
- Liste des successeurs du sommet b ---- c
- Liste des successeurs du sommet c ---- a
- Liste des successeurs du sommet d ---- a → e → f
- Liste des successeurs du sommet e ---- a
- Liste des successeurs du sommet f ---- a
Listes des successeurs
L'étude de ces listes permet de trouver facilement les culs de sacs (les sommets à partir desquelles on ne peut plus aller nulle part) ou au contraire les sommets menant à une grande partie des autres sommets.
Il faut ensuite créer les listes des prédécesseurs.
- Liste des prédécesseurs du sommet a ---- c → d → e → f
- Liste des prédécesseurs du sommet b ---- a
- Liste des prédécesseurs du sommet c ---- b
- Liste des prédécesseurs du sommet d ---- a
- Liste des prédécesseurs du sommet e ---- d
- Liste des prédécesseurs du sommet f ---- d
Listes des prédécesseurs
L'étude de ces listes permettrait par exemple de connaitre les conséquences de la fermeture d'une route. Ainsi, fermer l'accès à d empêche l'accès à e et f.
Cela ne sera pas aborder cette année (ou alors sur un thème de grand oral) mais l'étude des ces deux listes permet d'en apprendre énormément sur la topologie du graphe : quelles sont les zones connexes du graphe, quelles sont les ponts entre les zones ? y-a-t-il des points critiques à surveiller pour garantir le transport ? ...
15° Voici un graphe non orienté. Fournir les listes de successeurs et des prédécesseurs qui permettraient de le représenter correctement.
...CORRECTION...
- Liste des successeurs du sommet 0 ---- 1 → 4
- Liste des successeurs du sommet 1 ---- 2 → 4
- Liste des successeurs du sommet 2 ---- 3 → 4
- Liste des successeurs du sommet 3 ---- 0
- Liste des successeurs du sommet 4 ---- 2
Listes des successeurs
- Liste des successeurs du sommet 0 ---- 3
- Liste des successeurs du sommet 1 ---- 0
- Liste des successeurs du sommet 2 ---- 1 → 4
- Liste des successeurs du sommet 3 ---- 2
- Liste des successeurs du sommet 4 ---- 0 → 1 → 2
Listes des prédécesseurs
8 - Graphe pondéré
Si le graphe est pondéré (comme dans le cas d'une représentation d'un système autonome sous OSPF), il faut rajouter le poids de l'arête ou de l'arc en plus de sa simple existence.
L'un des moyens de faire cela est de stocker un tableau ou un tuple (destination, poids) plutôt que juste la destination de l'arc ou l'arête.
Prenons par exemple ce petit système autonome qu'on peut représenter par un graphe non orienté:
Pour représenter correctement ce système avec une liste d'adjacence, il faut donc une liste correspondant à ceci :
- Liste d'adjacence du sommet a ---- (b, 1) → (c, 1) → (d, 10)
- Liste d'adjacence du sommet b ---- (a, 1) → (c, 10)
- Liste d'adjacence du sommet c ---- (a, 1) → (b, 10) → (d, 1)
- Liste d'adjacence du sommet d ---- (a, 10) → (c, 1)
Attention néanmoins, cette façon simple de régler le problème peut poser problème si on ne modifie pas en même temps les deux informations portant la même information normalement.
16° Quelle est ou quelles sont les modifications à faire si le graphe du réseau autonome devient ceci :
...CORRECTION...
Il faut modifier ici les informations de l'arête (a,d) à deux endroits.
- Liste d'adjacence du sommet a ---- (b, 1) → (c, 1) → (d, 100)
- Liste d'adjacence du sommet b ---- (a, 1) → (c, 10)
- Liste d'adjacence du sommet c ---- (a, 1) → (b, 10) → (d, 1)
- Liste d'adjacence du sommet d ---- (a, 100) → (c, 1)
Nous avons vu comment encoder une liste d'adjacence contenant les numéros des sommets.
Il existe une autre manière de faire utilisant la programmation orientée objet. On peut en effet créer une classe Sommet et une classe Arete ou Arc.
Les instances des sommets contiennent alors des listes contenant les références des arêtes ou des arcs.
Cette fois, l'information sur le poids est simplement stockée dans l'instance de l'arête.
Nous verrons cette façon de faire en DM.
9 - Et en Python ?
Lorsqu'on veut encoder une liste d'adjacence, nous avons donc vu qu'on pouvait utiliser :
- des tableaux statiques
- facile à mettre en place en Python
- recherche d'un arc connaissant les sommets à coût linéaire dans le pire des cas
- ajout et suppression d'un arc à coût linéaire dans le pire des cas
- des listes chaînées
- plus difficile à mettre en place en Python
- recherche d'un arc connaissant les sommets à coût linéaire dans le pire des cas
- ajout et suppression d'un arc à coût constant dans le pire des cas si on connaît la réference
Néanmoins, il reste une structure de données que nous pouvons utiliser avec Python : les dictionnaires.
Si vous vous souvenez du début d'année :
- La lecture ou la modification d'une valeur connaissant sa clé se fait à temps quasi-constant pourvu qu'il n'y ai pas de collusion sur les clés
- Le rajout ou la suppression d'une valeur connaissant sa clé se fait à temps quasi-constant pourvu qu'il n'y ai pas de collusion sur les clés
Bref, lorsqu'on veut implémenter rapidement des graphes via des listes d'adjacence en Python, son créateur, Guido van Rossum, conseille d'utiliser des dictionnaires.
Voyons par exemple comment représenter un graphe non orienté et non pondéré comme celui-ci représentant les liaisons sociales entre plusieurs personnes :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | |
Si on utilise ce code, voici comment obtenir la valeur de l'arête entre a et b :
>>> graphe[1]['a']['b']
1
Le problème vient du fait que lorsqu'on demande une clé inexistante à un dictionnaire, cela lève une exception...
>>> graphe[1]['a']['d']
KeyError: 'd'
17° Créer la fonction arete qui renvoie None ou le poids de l'arête entre les sommets s1 et s2:
1
2 | |
g est bien entendu le tuple encodant le graphe.
Notez bien que, dans le prototype de la fonction, on signale qu'on désire les clés des sommets sous forme de strings uniquement car ici ce sont des strings. De la même façon, le poids est un entier, on renvoie donc celui-ci. 1 dans le cas d'un graphe non pondéré par exemple. Mais nous aurions pu renvoyer True si l'arête existe et False sinon.
Exemple :
>>> arete(graphe, 'a', 'b')
1
>>> arete(graphe, 'a', 'd')
...CORRECTION...
1
2
3
4
5
6
7
8
9 | |
18° Créer la fonction nb_arete qui renvoie None ou le nombre d'arêtes liées à ce sommet:
1
2 | |
g est bien entendu le tuple encodant le graphe.
>>> nb_arete(graphe, 'a')
2
>>> nb_arete(graphe, 'c')
3
>>> nb_arete(graphe, 'z')
...CORRECTION...
1
2
3
4 | |
19° On veut en réalité détecter les erreurs en cas de mauvais sommet. Enlever les protections éventuelles sur votre fonction : elle doit lever une exception seule si on lui envoie un mauvais sommet.
1
2 | |
La seule différence dans l'énoncé vient donc de la nature de l'information renvoyée : la fonction renvoie bien un entier ou plante...
>>> nb_arete(graphe, 'a')
2
>>> nb_arete(graphe, 'c')
3
>>> nb_arete(graphe, 'z')
KeyError: 'z'
...CORRECTION...
1
2 | |
20° Créer la fonction amis_communs qui renvoie un tableau contenant les amis que deux sommets s1 et s2 ont en commun.
1
2 | |
La seule différence dans l'énoncé vient donc de la nature de l'information renvoyée : la fonction renvoie bien un entier ou plante...
>>> amis_communs(graphe, 'a', 'b')
['c']
>>> amis_communs(graphe, 'a', 'd')
['c']
...CORRECTION...
Deux façons de faire.
1
2
3
4
5
6
7
8
9
10
11
12
13 | |
10 - FAQ
Rien pour le moment
Activité publiée le 08 04 2021
Dernière modification : 26 04 2021
Auteur : ows. h.