Données Graphes 3

Identification

Infoforall

31 - graphe et liste

⏪

⏬

⏩

1 - liste

2 - Lst Adj.

3 - Sommet

4 - Tableaux

5 - lst cha.

6 - orienté

7 - Pondéré

8 - Python

9 - Sujets

10 - FAQ

Documents de cours : open document ou pdf

1 - Listes

⇩ ⇧ ⤊

(Rappel) 1er partie de la définition de Liste : l'idée générale

(Rappel)..A Propriétés générales d'organisation

Le type abstrait Liste a les propriétés suivantes :

  • Le mot Element désigne une valeur de la Liste.
  • Le mot Place fait référence au conteneur dans lequel on stocke un Element individuel de la Liste. On pourrait utiliser également le mot Emplacement, mais c'est plus long à écrire. On peut le voir comme un dossier suspendu ou comme un casier...
  • Une Liste une structure linéaire composée d'une séquence finie et ordonnée de Places.
  • On doit pouvoir insérer et supprimer au moins une Place (dont la situation est à choisir : cela peut être au début, ou à la fin, ou partout...)
  • On doit pouvoir accéder à toutes les Places.
  • On doit pouvoir lire un Elément en connaissant la Place qu'il occupe
  • On doit pouvoir trouver le successeur unique de chaque Place.

On peut résumer cela en disant qu'il s'agit d'une structure de données dans laquelle on peut accéder librement à n'importe quelle donnée.

Vous pouvez appréhender le type abstrait Liste en faisant une analogie avec des dossiers suspendus :

Analogie des dossiers suspendus
(Rappel)..B Vocabulaire
  • On désigne la première Place de la Liste sous le nom de tête (head en anglais). On ordonne les autres Places à partir du nombre de sauts nécessaires pour les atteindre à partir de la tête : la tête est à la distance 0, la suivante à 1...
  • L'ensemble des autres Places de la Liste porte le nom de queue (tail en anglais).
  • La dernière Place de la Liste porte le nom de fin. Attention, on trouve parfois également le mot queue pour désigner la fin. Ici, nous utiliserons bien uniquement fin.
  • La Liste est homogène si tous les éléments stockés sont de même type. Sinon elle est inhomogène.
(Rappel)..C Exemple

Deux façons de voir graphiquement une liste contenant une tête dont l'élément est 5 suivie d'une queue contenant les éléments 8, 2 et 3.

  • 5 → 8 → 2 → 3
  • 3 ← 2 ← 8 ← 5
Analogie des dossiers suspendus
(Rappel)..D Propriétés mathématiques ?

Le choix a été fait ici de définir les propriétés sous forme de phrases informelles.

On pourrait formaliser tout cela de façon rigoureuse et établir précisément toutes les propriétés mathématiques que doit avoir le type Liste.

Avantage de la définition globale : facile à comprendre.

Désavantage de la définition globale : pas de formalisme mathématique, les preuves et démonstrations manquent de rigueur.

(Rappel) 2nd partie de la définition de Liste : spécifications des primitives

(Rappel)..A Dépendances du type abstrait Liste

Les dépendances de type sont les autres types abstraits qui font apparaître dans les signatures des primitives du type étudié. Il faut définir et clarifier ces autres types pour éviter toute ambiguïté sur le nouveau type.

Pour définir notre Liste, nous allons avoir besoin des autres types suivants :

  • Vide pour référencer l'absence d'information,
  • Booléen,
  • Entier Naturel,
  • Elément (le type des données que nous allons pouvoir ranger dans la Liste),
  • Place (le conteneur permettant de stocker un Elément). On décide du fait qu'une Place ne peut pas être vide : si elle existe, c'est qu'elle contient un Element.

On peut donc voir la Liste comme une sorte de conteneur de Places, chaque Places contenant elle-même un Element.

(Rappel)..B Spécifications : définition

Voici les primitives d'une Liste immuable. Nous allons voir que toutes ne sont pas nécessaires mais qu'il faut pouvoir les recréer avec celles que vous avez au départ.

Fondamentales

  1. nouvelleListeVide() → Liste

    2. DESCRIPTION : Renvoie une nouvelle Liste VIDE initialement.

  2. estListeVide(lst:Liste) → Booléen

    3. DESCRIPTION : Renvoie VRAI si la liste lst fournie est vide, FAUX sinon.

  3. inserer(lst:Liste, elt:Elément, ...) → Liste

    4. DESCRIPTION : Renvoie une nouvelle Liste comportant le nouvel élément à une position définie : en tête de liste, en fin de liste, à un indice i précis. Certaines valeurs seront donc décalées par rapport à la Liste initiale.

    Voici plusieurs versions qui pourraient convenir, la dernière étant la plus générique :

    insererTete(lst:Liste, elt:Elément) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste où l'élément est placé en tête de liste, provoquant le décalage des autres élements.

    insererFin(lst:Liste, elt:Elément) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste où l'élément est placé en fin de liste.

    inserer(lst:Liste, elt:Elément, i:Entier Naturel) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste comportant le nouvel élément à la position indiquée par l'indice fourni. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

    • Pour insérer comme nouvelle Tête, on doit donc envoyer i valant 0.
    • Pour insérer juste avant la fin, on doit envoyer longueur -1.
    • Pour insérer comme nouvelle fin, on doit envoyer longueur qui correspond à un indice "vide" pour la liste de départ.

    PRECONDITIONS :

    • l'indice i (s'il existe) caractérise un indice valide pour l'insertion
    • elt doit avoir un type compatible avec le reste des Eléments si la Liste est homogène.

    POSTCONDITION : la Liste renvoyée possède un emplacement en plus mais lst est inchangée.

    Exemples d'utilisation

    lstA = nouvelleListeVide()
    lstB = inserer(lstA, 5, 0)
    lstB contient alors (5, () ) qu'on pourrait noter simplement (5, ).

    lstC = inserer(lstB, 15, 0)
    lstC contient alors (15, (5, () )) qu'on pourrait noter (15, 5, ).

    lstD = inserer(lstC, 25, 1)
    lstD contient alors (15, (25, (5, () ))) qu'on pourrait noter (15, 25, 5, ).

    lstE = inserer(lstD, 50, 3)
    lstE contient alors (15, (25, (5, (50, () )))) qu'on pourrait noter (15, 25, 5, 50, ).

  4. supprimer(lst:Liste, ...) → Liste

    5. DESCRIPTION : Renvoie une nouvelle Liste dans laquelle on a supprimé un emplacement prédéfini dans la Liste NON VIDE reçue. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

    Voici plusieurs versions qui pourraient convenir, la dernière étant la plus générique :

    supprimerTete(lst:Liste) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste dans laquelle on a supprimé l'ancien emplacement en tête de liste. Certains emplacements sont donc décalés par rapport à la Liste initiale.

    supprimerFin(lst:Liste) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste dans laquelle on a supprimé l'ancien emplacement en fin de liste. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

    supprimer(lst:Liste, i:Entier Naturel) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste dans laquelle on a supprimé l'ancien emplacement ayant cet indice. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

    • Pour supprimer l'élément de Tête, on doit donc envoyer i valant 0.
    • Pour supprimer l'élément de fin, on doit envoyer longueur -1.

    PRECONDITION :

    • la Liste est NON VIDE.
    • l'indice i (s'il existe) est un indice VALIDE.

    POSTCONDITION : la Liste renvoyée possède un emplacement en moins mais lst est inchangée.

    Exemple d'utilisation

    Partons de lstE contenant (15, (25, (5, (50, () )))) ou simplement (15, 25, 5, 50, ).
    lstF = supprimer(lstE, 1)
    lstF contient alors (15, (5, (50, () ))) ou simplement (15, 5, 50, ).

    lstG = supprimer(lstF, 2)
    lstG contient alors (15, (5, () )) ou simplement (15, 5, ).

Importante si on utilise les indices

  1. longueur(lst:Liste) → Entier Naturel

    2. DESCRIPTION : Renvoie le nombre d'éléments stockés dans la liste.

Interactions avec les Places

  1. acces(lst:Liste, ...) → Place

    2. DESCRIPTION : Renvoie la Place correspondant à une position définie.

    PRECONDITION : la Liste reçue doit être NON VIDE.

    Voici plusieurs versions qui pourraient convenir, la dernière étant la plus générique :

    accesTete(lst:Liste) → Place

    DESCRIPTION : Renvoie la Place correspondant à la tête.

    accesFin(lst:Liste) → Place

    DESCRIPTION : Renvoie la Place correspondant à la fin.

    acces(lst:Liste, i:Entier Naturel) → Place

    DESCRIPTION : Renvoie la Place correspondant à l'indice i fourni.

    PRECONDITION :

    • la Liste est NON VIDE.
    • l'indice i (s'il existe) est un indice VALIDE.

    POSTCONDITION : la Liste est inchangée.

    Les deux dernières primitives interagissent directement avec une Place. Attention, dans l'esprit de ce type abstrait Liste, la connaissance d'une Place doit venir de l'utilisation de acces().

  2. contenu(plc:Place) → Elément

    3. DESCRIPTION : Renvoie l'Elément référencé par plc.

    PRECONDITION : plc est une Place valide, contenant un élément compatible avec les autres si la Liste est homogène.

    POSTCONDITION supplémentaire : si la Liste est homogène le type de l'Elément est compatible avec ceux de la Liste.

  3. successeur(plc:Place) → Place

    4. DESCRIPTION : Renvoie la Place qui succède à plc, une Place NON FIN.

    PRECONDITION : plc est une Place qui ne doit pas être la dernière de la Liste, la Fin.

L'une des spécificités du type abstrait Liste est que sa définition est plutôt large car

  • on n'explique pas vraiment ce qu'est une Place. Il faut juste que votre type Place soit lui clairement défini.
  • on n'impose pas spécifiquement d'endroit où agir. Il faut juste que votre version soit claire à ce sujet.

Toutes les structures de données qui collent à la définition et qui possèdent ces primitives sont donc des Listes.

Résumé : les 8 types de primitives qu'il faudra avoir ou reconstruire à partir des autres :

Fondamentales

  1. nouvelleListeVide() → Liste VIDE
  2. estListeVide(lst:Liste) → Booléen
  3. inserer(lst:Liste, elt:Elément, i:Entier Naturel INDICE VALIDE) → Liste NON VIDE
  4. supprimer(lst:Liste NON VIDE, i:Entier Naturel INDICE VALIDE) → Liste

Importante si on utilise les indices

  1. longueur(lst:Liste) → Entier Naturel

Interactions avec les Places

  1. acces(lst:Liste NON VIDE, i:Entier Naturel INDICE VALIDE) → Place
  2. contenu(plc:Place) → Elément
  3. successeur(plc:Place NON FIN) → Place
(Rappel) Implémentations courantes

On implémente souvent les listes sous trois formes.

Tuple (élément de tête, queue) [tuple immuable en Python]

Avec la forme p-uplet (tête, queue), on obtient une structure de données proche d'une pile. Implémentation facile à comprendre mais

  • lecture et modification à coût linéaire (mais constant en tête)
  • rajout et suppression à coût linéaire sur la fin (mais constant en tête)
  • concaténation de deux listes à coût linéaire
    • Serpent Tête et Queue
    Image libre de droit

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 :

5 →
8 →
2 →
3 → X
Le tableau dynamique [list muable en Python]

La forme liste contiguë. On n'utilise pas de tableau statique car les performances sont alors mauvaises. Par contre, on peut utiliser un tableau dynamique, où les "cases" sont réellement les unes derrière les autres en mémoire. Avec ce tableau dynamique :

  • lecture et modification à coût constant dans le pire des cas
  • rajout et suppression à coût linéaire (mais constant sur la dernière case).
  • concaténation de deux listes à coût linéaire.

Considèrons cette liste :

5 → 8 → 2 → 3

Elle correspondrait à une zone mémoire où toutes les cases ont la même largeur d'octets et sont situées les unes derrière les autres.

5 8 2 3
Liste chaînée [non native en Python]

La forme liste chaînée utilise une succesion de Cellules qui contiennent une valeur ET la référence de la queue : une liste NON VIDE ou une liste VIDE si la Cellule est la Fin de la liste.

  • lecture et modification à coût linéaire (mais constant sur la tête)
  • le rajout et la suppression est à coût linéaire (mais constant sur la tête, parfois la liste intégre une référence vers la Cellule de fin)
  • concaténation de deux listes à coût constant (si on accepte les modifications directes)

Considèrons cette liste :

5 → 8 → 2 → 3

Elle peut donc être vue comme cet ensemble de Cellules :

Liste chaînée

2 - Listes d'adjacence

⇩ ⇧ ⤊

Alors qu'est-ce qu'une liste d'adjacence d'un graphe ?

2.1 Généralités sur la liste d'adjacence

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 adjacents.

Matrice exemple pour la liste d'adjacence

Sur l'exemple, on a 4 sommets donc 4 listes d'adjacence.

  1. Liste d'adjacence du sommet a ---- b → c
  2. Liste d'adjacence du sommet b ---- a → c
  3. Liste d'adjacence du sommet c ---- a → b → d
  4. Liste d'adjacence du sommet d ---- c
Place mémoire

La liste d'adjacence d'un sommet possède au maximum n éléments si n est le nombre de sommets.

C'est donc mieux qu'avec la matrice d'adjacence puisque chaque ligne possédait nécessairement n éléments.

Arité d'un sommet

L'arité d'un sommet caractérise le nombre d'arêtes liées à ce sommet.

Si on dispose d'une liste d'adjacence, il suffit de connaître la longueur de la liste d'adjacence pour connaître son arité.

Une vraie liste ordonnée ? Non

Les listes d'adjacences ne sont pas nécessairement de vraies listes au sens informatique : elles n'ont pas nécessairement d'ordre interne. La tête n'a pas à être particulièrement associée avec un élément plutôt qu'un autre. Voici deux versions possibles de la liste d'adjacence du sommet c.

  • Liste d'adjacence du sommet c ---- a → b → d
  • Liste d'adjacence du sommet c ---- b → d → a
2.2 Principe de la liste d'adjacence

Une vraie liste ? Oui !

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.

Ainsi, 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 puisqu'on a dépassé sa valeur.

Comme la tête n'a pas réellement de sens, on pourrait la représenter de cette façon :

  1. Liste d'adjacence du sommet a ---- b → c
  2. Liste d'adjacence du sommet b ---- a → c
  3. Liste d'adjacence du sommet c ---- a → b → d
  4. Liste d'adjacence du sommet d ---- c
Avec une liste ordonnée de sommets

Il suffit donc d'énumérer les sommets en leur attribuant un numéro. Ensuite, on pourra les identifier uniquement à l'aide de ce numéro.

En passant aux numéros,et en utilisant un simple tableau d'entiers en tant que liste d'adjacence, on obtient alors ceci :

  1. Liste d'adjacence du sommet a, numéro 0 ---- 1 → 2
  2. Liste d'adjacence du sommet b, numéro 1 ---- 0 → 2
  3. Liste d'adjacence du sommet c, numéro 2 ---- 0 → 1 → 3
  4. Liste d'adjacence du sommet d, numéro 3 ---- 2

Comme le numéro est un identifiant, chaque valeur ne peut être attribuée qu'à un unique sommet. Il ne s'agit donc pas d'une simple étiquette, mais bien d'une sorte de clé primaire.

01° A quoi correspond le nombre d'éléments dans la liste d'adjacence d'un sommet ?

Matrice exemple pour la liste d'adjacence
  1. Liste d'adjacence du sommet a ---- b → c
  2. Liste d'adjacence du sommet b ---- a → c
  3. Liste d'adjacence du sommet c ---- a → b → d
  4. 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 :

Graphe non orienté q6

...CORRECTION...

  1. Liste d'adjacence du sommet 1 ---- 2 → 3 → 4
  2. Liste d'adjacence du sommet 2 ---- 1 → 3
  3. Liste d'adjacence du sommet 3 ---- 1 → 2
  4. Liste d'adjacence du sommet 4 ---- 1 → 5 → 6
  5. Liste d'adjacence du sommet 5 ---- 4
  6. Liste d'adjacence du sommet 6 ---- 4

Nous avions travaillé avec un bout simplifié de ce plateau Pacman dans l'activité précédente.

Plateau Pacman

03° Fournir les listes d'adjacences des différents sommets du graphe correspondant aux liaisons entre les différentes zones du plateau du jeu :

Graphe Pacman
  1. Liste d'adjacence du sommet 1 ----
  2. Liste d'adjacence du sommet 2 ----
  3. Liste d'adjacence du sommet 3 ----
  4. Liste d'adjacence du sommet 4 ----
  5. ...

...CORRECTION...

Graphe Pacman
  1. Liste d'adjacence du sommet 1 ---- 2 → 3 → 5
  2. Liste d'adjacence du sommet 2 ---- 1 → 3 → 4 → 6
  3. Liste d'adjacence du sommet 3 ---- 1 → 2 → 4
  4. Liste d'adjacence du sommet 4 ---- 2 → 3 → 67
  5. Liste d'adjacence du sommet 5 ---- 1 → 9
  6. Liste d'adjacence du sommet 6 ---- 2 → 7 → 8
  7. Liste d'adjacence du sommet 7 ---- 4 → 6
  8. Liste d'adjacence du sommet 8 ---- 6 → 9
  9. Liste d'adjacence du sommet 9 ---- 5 → 8

Vos listes contiennent donc la même information que la matrice d'adjacence correspondante, si ce n'est qu'on n'indique pas les 0. Avec les listes d'adjacences, on ne place en mémoire que l'information "l'arête existe".

Matrice Pacman

3 - Implémenter et ordonnancer les sommets

⇩ ⇧ ⤊

Comment stocker les informations sur les sommets ? Nous allons voir qu'il existe de multiples façons d'implémenter les sommets.

Imaginons qu'on veuille encoder ceci qui pourrait être la carte d'un donjon contenant des monstres et des trésors à récupérer :

Matrice exemple pour la liste d'adjacence
3.1 Sommet vu comme un couple

Nous pourrions utiliser des couples (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
# Création des sommets avec un tuple contenant un string et un tuple a = ("A", ("Salle de garde", 6, "Gobelin", 100)) b = ("B", ("Antre du Dragon", 1, "Dragon", 2000)) c = ("C", ("Crypte", 3, "Zombie", 200)) d = ("D", ("Salle secrête", 3, "Araignée Géante", 1000)) tresor_en_salle_a = a[1][3]

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

3.2 Sommet vu comme un tuple

Nous pourrions utiliser des tuples où l'indice 0 serait l'étiquette de la salle-sommet et les autres indices contiendraientt les informations sur la salle-sommet :

1 2 3 4 5 6 7 8
# Création des sommets avec un tuple contenant toutes les infos a = ("A", "Salle de garde", 6, "Gobelin", 100) b = ("B", "Antre du Dragon", 1, "Dragon", 2000) c = ("C", "Crypte", 3, "Zombie", 200) d = ("D", "Salle secrête", 3, "Araignée Géante", 1000) tresor_en_salle_a = a[4]
3.3 Sommet vu comme un dictionnaire

Nous pourrions utiliser des dictionnaires où chaque clé correspondrait à une information sur la salle :

1 2 3 4 5 6 7 8
# Création des sommets avec des dictionnaires a = {"etiquette": "A", "nom": "Salle de garde", "nb": 6, "monstre": "Gobelin", "tresor": 100} b = {"etiquette": "B", "nom": "Antre du Dragon", "nb": 1, "monstre": "Dragon", "tresor": 2000} c = {"etiquette": "C", "nom": "Crypte", "nb": 3, "monstre": "Zombie", "tresor": 200} d = {"etiquette": "D", "nom": "Salle secrête", "nb": 3, "monstre": "Araignée Géante", "tresor": 1000} tresor_en_salle_b = b["tresor"]

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.

3.4 Sommet vu comme un objet

Nous pourrions utiliser des objets ( instances de la classe Salle) où chaque attribut correspondrait à une information sur la salle :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
# Création des sommets avec des objets class Salle: def __init__(self, e, n, nb, m, t): self.etiquette = e self.nom = n self.nb = nb self.monstre = m self.tresor = t a = Salle("A", "Salle de garde", 6, "Gobelin", 100) b = Salle("B", "Antre du Dragon", 1, "Dragon", 2000) c = Salle("C", "Crypte", 3, "Zombie", 200) d = Salle("D", "Salle secrête", 3, "Araignée Géante", 1000) tresor_en_salle_c = c.tresor

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.

3.5 Stocker les sommets pour utiliser les listes d'adjacence

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
0 1 2 3 sommmets = [a, b, c, d]

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 ?

1
sommets = [a, b, c, d]

...CORRECTION...

Il s'agit de c

1
0 1 2 3 sommets = [a, b, c, d]

4 - Implémenter les listes d'adjacence avec des tableaux

⇩ ⇧ ⤊

Il y a beaucoup de façons d'implémenter les sommets.

Il y a beaucoup de façons d'implémenter les listes d'adjacence également.

Commençons par voir une implémentation qui nécessite d'avoir associer un numéro à chaque sommet, en les plaçant dans un tableau par exemple.

4.1 Implémentation des listes d'adjacence dans un tableau de tableaux

1
sommmets = [a, b, c, d]

Nous avions vu qu'avec notre donjon d'exemple, les listes d'adjacence des salles a, b, c et d étaient :

Listes contiguës implémentant des listes d'adjacence

En Python, cela pourrait donner :

1 2 3 4 5 6 7
sommmets = [a, b, c, d] listes = [ [1, 2], [0, 2], [0, 1, 3], [2]]

Avantage par rapport à la matrice d'adjacence : les listes prennent donc moins de place puisqu'on ne gère que les arêtes qui existent.

Désavantage par rapport à la matrice d'adjacence : pour savoir si une arête existe, il faut lire la liste et c'est donc à coût linéaire par rapport à la longueur de la liste.

Néanmoins, ce n'est pas un "vrai défaut" :

  • si la matrice est dense, autant passer à la matrice
  • si la matrice est creuse, la longueur moyenne de chaque liste est bien plus petite que le nombre de sommets

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.

  1. Constant : Θ(1)
  2. Logarithmique : Θ(log n)
  3. Linéaire : Θ(n)
  4. Quasi-linénaire : Θ(n log n)

...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.

Pour rappel, savoir si une arête existe est à coût constant dans le cas d'une matrice d'adjacence.

m[ligne][colonne]

Puisque chaque accès est à coût constant, on a deux actions à coût constant, donc l'action est à coût constant.

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. Adaptée si la matrice est dense.
  • Liste d'adjacence sous forme d'un tableau : coût linéaire pour la recherche d'arête mais le coût en mémoire est beaucoup plus faible. Adaptée si la matrice est creuse.

Mais selon les problèmes, la liste d'adjacence d'un sommet peut avoir une taille limitée. Prenons le cas de PacMan :

Plateau 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 liste d'adjacence est de taille 4 au maximum puisque chaque sommet ne peut avoir que 4 voisins au maximum : en haut, en bas, à gauche, à droite.

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.

  1. Constant : Θ(1)
  2. Logarithmique : Θ(log n)
  3. Linéaire : Θ(n)
  4. Quasi-linénaire : Θ(n log n)

...CORRECTION...

Quelque soit le nombre de sommets représentant le labyrinthe, il faudra faire 4 recherches au maximum.

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.

4.2 Implémentation des listes d'adjacence dans deux tableaux

Il existe une autre implémentation basée non pas sur un tableau par sommet mais avec uniquement deux tableaux :

  • Un tableau debut qui contient l'indice où débute la liste d'adjacente du sommet voulu et
  • un tableau adjacents qui contient la concaténation de toutes les listes précédentes.
1 2 3 4 5
sommmets = [a, b, c, d] debut = [0, 2, 4, 7] adjacents = [1, 2, 0, 2, 0, 1, 3, 2]

Regardons comment trouver la liste d'adjacence du sommet b.

On voit dans sommets que b est le sommet d'indice 1.

On lit debut[1] pour trouver le début de notre liste d'adjacence : l'indice 2.

On lit debut[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ée des indices [2..3] du tableau adjacents.

A titre de comparaison, voici la version un tableau pour chaque liste d'adjacence :

1 2 3 4 5
listes = [ # Ancienne version des listes d'adjacences [1, 2], [0, 2], [0, 1, 3], [2]]
5
adjacents = [1, 2, 0, 2, 0, 1, 3, 2]

10° Contruire les deux tableaux nécessaires à ce graphe en utilisant l'implémentation sous forme d'un tableau debut et d'un tableau adjacents.

Attention de bien respecter l'ordre des sommets imposés par la variable sommets.

Rajout d'une arête
1 2 3 4 5
sommets = [b, c, d, a] debut = [] adjacents = []

...CORRECTION...

5 - Implémenter les listes d'adjacence avec des listes chaînées

⇩ ⇧ ⤊

En Python, l'ensemble sera donc plus lourd à coder puisque le langage ne possède pas de types natifs "listes chaînées".

Cette partie ne sera pas faite avec Python, nous allons juste réfléchir sur les avantages de cette méthode.

Nous travaillons toujours avec ce graphe :

Matrice exemple pour la liste d'adjacence

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.

Listes chaînées implémentant des listes d'adjacence

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 ?

  1. Constant : Θ(1)
  2. Logarithmique : Θ(log n)
  3. Linéaire : Θ(n)
  4. 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 ?

  1. Constant : Θ(1)
  2. Logarithmique : Θ(log n)
  3. Linéaire : Θ(n)
  4. Quasi-linénaire : Θ(n log n)
Rajout d'une arête Rajout d'une arête au début

...CORRECTION...

Coût constant car il suffit de :

  • Localiser la tête actuelle : coût constant.
  • Créer la nouvelle Cellule : coût constant.
  • Indiquer que la nouvelle cellule mène à la la tête actuelle : coût constant.
  • Dire que la tête de notre liste est maintenant notre nouvelle Cellule : coût constant.

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 ?

  1. Constant : Θ(1)
  2. Logarithmique : Θ(log n)
  3. Linéaire : Θ(n)
  4. Quasi-linénaire : Θ(n log n)
Rajout d'une arête Rajout d'une arête au début

...CORRECTION...

Il s'agit juste de faire ceci :

  1. Localiser la Fin de la liste d'adjacence de a : linéaire si on part de la Tête ou constant si la liste contient directement la référence de la Fin.
  2. Créer la nouvelle Cellule : coût constant.
  3. Indiquer que l'ancienne Fin mène à notre nouvelle Cellule : coût constant.
  4. Modifier éventuellement l'attribut Fin de la liste : coût constant.

Le coût est donc constant ou linéaire en fonction de la façon dont la liste a été conçue.

14° Voici un graphe non orienté (et non pur car possèdant des boucles). Fournir les listes d'adjacences qui permettraient de le représenter correctement.

Graphe avec boucle

On utilisera juste les numéros des sommets. Début de la rédaction :

Début de la réponse

...CORRECTION...

réponse

6 - Pour les graphes orientés ? 2 listes !

⇩ ⇧ ⤊

Et sur les graphes orientés ?

6.1 graphe orienté : deux listes d'adjacence

Si le graphe est orienté, il va falloir distinguer les arcs entrants et les arcs sortants.

Définitions des deux listes d'adjacence

L'une des solutions pour gérer les graphes orientés est de distinguer deux listes d'adjacence :

  1. La liste des successeurs pour les arcs sortants
  2. La liste des prédécesseurs pour les arcs entrants

Si seule la "marche avant" vous intéresse, il suffit d'implémenter uniquement la liste des successeurs.

6.2 Listes des successeurs d'un graphe orienté

Principe

Considérons ce graphe représentant un ensemble de routes, certaines étant à sens unique :

graphe orienté

On voit qu'il n'y a que les arcs (a,b) et (a,d) en sortie du sommet a.

    Listes des successeurs

  • 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

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. On parle de puit.

Exemple avec des tableaux
1 2 3 4 5 6 7
successeurs = [ [1, 3], # successeurs de a, indice 0 [2], # successeurs de b, indice 1 [0], # successeurs de c, indice 2 [0, 4, 5], # successeurs de d, indice 3 [0], # successeurs de e, indice 4 [0]] # successeurs de f, indice 5
6.3 Listes des prédécesseurs d'un graphe orienté

Principe

Pour chaque sommet, on s'intéresse aux sommets qui mènent à ce sommet.

On s'intéresse donc à une sorte de marche arrière.

graphe orienté

    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

Cette liste vous permet de voir par où on a pu arriver pour atteindre un sommet.

Exemple avec des tableaux
1 2 3 4 5 6 7
predecesseurs = [ [2, 3, 4, 5], # Prédécesseurs de a, indice 0 [0], # Prédécesseurs de b, indice 1 [1], # Prédécesseurs de c, indice 2 [0], # Prédécesseurs de d, indice 3 [3], # Prédécesseurs de e, indice 4 [3]] # Prédécesseurs de f, indice 5

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.

Graphe orienté

...CORRECTION...

    Listes des successeurs

  • 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 prédécesseurs

  • 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

7 - 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.

7 graphe pondéré : intégration du poids dans la liste

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é:

Système autonome sous OSPF

Pour représenter correctement ce système avec une liste d'adjacence, il faut donc une liste correspondant à ceci :

  1. Liste d'adjacence du sommet a ---- (b, 1) → (c, 1) → (d, 10)
  2. Liste d'adjacence du sommet b ---- (a, 1) → (c, 10)
  3. Liste d'adjacence du sommet c ---- (a, 1) → (b, 10) → (d, 1)
  4. Liste d'adjacence du sommet d ---- (a, 10) → (c, 1)

Rien de très compliqué, il suffit de comprendre que la liste d'adjacence porte maintenant deux informations dans chacune de ses cases.

16° Quelle est ou quelles sont les modifications à faire si le graphe du réseau autonome devient ceci :

Modification du graphe non orienté

...CORRECTION...

Il faut modifier ici les informations de l'arête (a,d) à deux endroits.

  1. Liste d'adjacence du sommet a ---- (b, 1) → (c, 1) → (d, 100)
  2. Liste d'adjacence du sommet b ---- (a, 1) → (c, 10)
  3. Liste d'adjacence du sommet c ---- (a, 1) → (b, 10) → (d, 1)
  4. 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.

8 - Implémenter une liste d'adjacence avec un dictionnaire

⇩ ⇧ ⤊

Lorsqu'on veut encoder une liste d'adjacence, nous avons donc vu qu'on pouvait utiliser :

  • des tableaux dynamiques
  • des listes chaînées

Néanmoins, en Python, son créateur Guido van Rossum, recommande d'utiliser une autre structure pour implémenter les listes d'adjacence : les dictionnaires.

  • lecture ou modification d'une valeur connaissant sa clé se fait à temps quasi-constant
  • rajout ou suppression d'une valeur connaissant sa clé se fait à temps quasi-constant
8.1 Graphe pondéré : Listes d'adjacence avec un dictionnaire de dictionnaires

Principe général

Voyons par exemple comment représenter un graphe non orienté pondéré comme celui-ci représentant les liaisons entre des routeurs par exemple :

Graphe de liaison entre routeurs

Nous allons définir notre graphe sous forme de deux dictionnaires :

  • Un dictionnaire sommets dont les clés correspondent à l'identifiant de chaque sommet et dont les valeurs sont les données des sommets.
  • Un dictionnaire adj dont les clés correspondent à l'identifiant de chaque sommet et donc les valeurs sont un dictionnaire {id:cout}.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
sommets = {} sommets['a'] = {'nom': 'alice', 'age':18} sommets['b'] = {'nom': 'bob', 'age': 19} sommets['c'] = {'nom': 'Charlie', 'age' : 17} sommets['d'] = {'nom': 'dana', 'age':18} adj = {} adj['a'] = {'b': 1, 'c': 1} adj['b'] = {'a': 1, 'c': 10} adj['c'] = {'a': 1, 'b': 10, 'd': 1} adj['d'] = {'c': 1} graphe = (sommets, adj)

Si on utilise ce code, voici comment obtenir la valeur de l'arête entre a et b :

>>> graphe[1]['a']['b'] 1
Récupération d'informations

Pour comprendre comment cela fonctionne, il faut y aller progressivement :

>>> graphe[1]['a']['b'] équivalent à >>> adj['a']['b'] équivalent à >>> {'b': 1, 'c': 1}['b'] équivalent à >>> 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 le poids de l'arête entre les sommets s1 et s2 (PRECONDITION : sommets qui existent bien dans le graphe):

1 2
def arete(g:tuple, s1:str, s2:str) -> int: return None

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') 0

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11
def arete(g:tuple, s1:str, s2:str) -> int: liste = g[1] # si s1 et s2 ont bien une liste d'adjacence if s1 in liste.keys() and s2 in liste.keys(): # si s1 et s2 ont bien une liste d'adjacence # si s2 est bien dans la liste de s1 et inversement if s2 in liste[s1].keys() and s1 in liste[s2].keys(): return liste[s1][s2] return 0

18° Créer la fonction nb_aretes qui renvoie le nombre d'arêtes liées à ce sommet:

1 2
def nb_aretes(g:tuple, s:str) -> int: return 0

g est bien entendu le tuple encodant le graphe.

PRECONDITON : le sommet fourni doit être un sommet du graphe.

>>> nb_aretes(graphe, 'a') 2 >>> nb_aretes(graphe, 'c') 3

...CORRECTION...

1 2 3 4
def nb_aretes(g:tuple, s:str) -> int: liste = g[1] if s in liste.keys(): # si s a bien une liste d'adjacence # si s2 est bien dans la liste de s1 et inversement return len(liste[s])

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 si on lui envoie un mauvais sommet.

1 2
def nb_aretes(g:tuple, s:str) -> int: return 0

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_aretes(graphe, 'a') 2 >>> nb_aretes(graphe, 'c') 3 >>> nb_aretes(graphe, 'z') KeyError: 'z'

...CORRECTION...

1 2
def nb_aretes(g:tuple, s:str) -> int: return len(g[1][s])

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
def amis_communs(g:tuple, s1:str, s2:str) -> list: return []
>>> 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
def amis_communs(g:tuple, s1:str, s2:str) -> list: reponse = [] for s in g[1][s1].keys(): if s in g[1][s2].keys(): reponse.append(s) return reponse def amis_communs(g:tuple, s1:str, s2:str) -> list: reponse = [] for s in g[1][s1].keys(): if s in g[1][s2].keys(): reponse = reponse + [s] return reponse
8.2 Graphe non pondéré : listes d'adjacence avec un dictionnaire de tableaux

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 :

Matrice exemple pour la liste d'adjacence
Deux dictionnaires de dictionnaires
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
sommets = {} sommets['a'] = {'nom': 'alice', 'age':18} sommets['b'] = {'nom': 'bob', 'age': 19} sommets['c'] = {'nom': 'Charlie', 'age' : 17} sommets['d'] = {'nom': 'dana', 'age':18} adj = {} adj['a'] = {'b': 1, 'c': 1} adj['b'] = {'a': 1, 'c': 1} adj['c'] = {'a': 1, 'b': 1, 'd': 1} adj['d'] = {'c': 1} graphe = (sommets, adj)
Deux dictionnaires dont un dictionnaire de tableaux

Un peu dommage d'utiliser un dictionnaire alors que la seule valeur associée sera 0...

Le plus facile serait de simplement considéré que la liste d'adjacence est un dictionnaire dont la clé est l'étiquette du sommet et la valeur associée est une liste des sommets adjacents !

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
sommets = {} sommets['a'] = {'nom': 'alice', 'age':18} sommets['b'] = {'nom': 'bob', 'age': 19} sommets['c'] = {'nom': 'charlie', 'age' : 17} sommets['d'] = {'nom': 'dana', 'age':18} adj = {} adj['a'] = ['b', 'c'] adj['b'] = ['a', 'c'] adj['c'] = ['a', 'b', 'd'] adj['d'] = ['c'] graphe = (sommets, adj)

21° Créer la fonction arete qui renvoie un booléen indiquant si l'arête existe, ou pas.

1 2
def arete(g:tuple, s1:str, s2:str) -> bool: return False

g est bien entendu le tuple encodant le graphe.

Exemple :

>>> arete(graphe, 'a', 'b') True >>> arete(graphe, 'a', 'd') False

...CORRECTION...

22° Créer la fonction nb_aretes qui renvoie le nombre d'arêtes liées à ce sommet (PRECONDTION : le sommet est bien un sommet du graphe):

1 2
def nb_aretes(g:tuple, s:str) -> int: return 0

g est bien entendu le tuple encodant le graphe.

>>> nb_aretes(graphe, 'a') 2 >>> nb_aretes(graphe, 'c') 3

...CORRECTION...

1 2 3 4
def nb_aretes(g:tuple, s:str) -> int: liste = g[1] if s in liste.keys(): # si s a bien une liste d'adjacence # si s2 est bien dans la liste de s1 et inversement return len(liste[s])

23° Créer la fonction amis_communs qui renvoie un tableau contenant les amis que deux sommets s1 et s2 ont en commun.

1 2
def amis_communs(g:tuple, s1:str, s2:str) -> list: return []
>>> 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
def amis_communs(g:tuple, s1:str, s2:str) -> list: reponse = [] for s in g[1][s1]: if s in g[1][s2]: reponse.append(s) return reponse def amis_communs(g:tuple, s1:str, s2:str) -> list: reponse = [] for s in g[1][s1]: if s in g[1][s2]: reponse = reponse + [s] return reponse

9 - Simplification lors des sujets écrits

⇩ ⇧ ⤊

Sans être compliqué lorsqu'on est à tête reposée, toutes ces implémentations restent néanmoins assez lourde à manipuler lors d'un sujet écrit "papier".

9.1 Graphe pondéré et sujet écrit

Lors d'un sujet papier, la seule information portée par chaque sommet est habituellement son nom.

Inutile alors de s'intéresser à l'ensemble des sommets !

On peut considérer que la liste d'adjacence caractérise totalement le graphe.

1 2 3 4 5 6
graphe = {} graphe['a'] = {'b': 1, 'c': 1} graphe['b'] = {'a': 1, 'c': 10} graphe['c'] = {'a': 1, 'b': 10, 'd': 1} graphe['d'] = {'c': 1}
9.2 Graphe non pondéré et sujet écrit

Lors d'un sujet papier, la seule information portée par chaque sommet est habituellement son nom.

Inutile alors de s'intéresser à l'ensemble des sommets !

On peut considérer que la liste d'adjacence caractérise totalement le graphe.

1 2 3 4 5 6
graphe = {} graphe['a'] = ['b', 'c'] graphe['b'] = ['a', 'c'] graphe['c'] = ['a', 'b', 'd'] graphe['d'] = ['c']

10 - FAQ

⇩ ⇧ ⤊

Rien pour le moment

Vous savez maintenant qu'on peut encoder les arcs et arêtes des graphes :

  • soit à l'aide d'une matrice d'adjacence
  • soit à l'aide d'une liste d'adjacence (sous forme de tableaux, de listes chaînées ou de dictionnaire)

Les dernières activités sur les graphes vous montreront comment le parcourir pour y trouver un chemin, une boucle ou une caractéristique particulière.

Activité publiée le 08 04 2021
Dernière modification : 26 04 2021
Auteur : ows. h.


⏪

⏫

⏩