Header
🠖 Chap. 3 : Graphes, structure de donnée relationnelle

Cours

Lexique

Introduction

Les graphes sont une modélisation mathématique efficace car simple et adaptable permettant de modéliser, en vue de leur étude et de leur amélioration, par exemple :
  • des réseaux de communication (téléphone, internet, sociaux) ;
  • des réseaux de transport (routiers, aériens, maritimes, ferrovières, ...)
  • des circuits électriques ;
  • des relations biologiques (proie-prédateur, évolution, ...)
  • des relations entre entités informatiques (fichiers dans un système, tables dans une base de données, ...)
La chaîne : À la découverte des graphes de C. Laforest peut permettre d'approfondir les notions vues dans ce cours.

Vocabulaire de la théorie des graphes

Définitions : Un graphe est constitué :
  • d'un ensemble fini de points appelées sommets ou nœuds,
  • d'un ensemble fini de lignes (appelée arêtes) ou de flèches (appelées arcs) reliant les sommets. Lorsqu'un graphe est constitué d'arcs, on parle de graphe orienté, sinon il s'agit d'un graphe non-orienté.

Remarque : Il est possible d'affecter des valeurs, des poids (coefficients positifs), des couleurs, etc... aux arêtes (le plus souvent) ou bien aux sommets (parfois) : on parle de graphe valué. Ces valeurs peuvent indiquer des distances, des coûts, etc. Pour être plus précis, on peut utiliser les termes graphes pondérés pour un graphe valué par des nombres et graphe étiqueté pour un graphe valué par des chaînes de caractères.

Un peu de vocabulaire pour fixer ces notions :

  • chaque arête relie deux sommets, qui sont appelés les extrémités de l'arête (dans le cas orienté, on doit distinguer l'extrémité initiale de l'extrémité finale, marquée par la flèche),
  • si les 2 extrémités sont égales, on dit que l'arête est une boucle,
  • lorsqu'on autorise deux arêtes différentes à avoir les mêmes extrémités (on parle d'arêtes parallèles), on parle de multigraphe :
- deux sommets sont voisins (ou adjacents) s'ils sont reliés par une arète. Dans le cas orienté, X → Y, Y est adjacent à X, mais X n'est pas adjacent à Y... - le degré d'un sommet est le nombre d'arêtes dont ce sommet est l'extrémité. Attention : les boucles comptent 2. Si le graphe est orienté, on distingue le degré intérieur/extérieur (nombre de flèches qui pointent vers le / partent du sommet) ; - Un graphe est complet lorsque tous ses sommets sont adjacents :

Ce qui compte, c'est de se promener sur un graphe... :

  • Un chemin ou une chaîne est une suite d'arêtes mises bout à bout (cas orienté : l'extrémité initiale correspond à l'extrémité finale de l'arête précédente). La longueur d'un chemin est le nombre de ses arêtes.
  • Un chemin est simple lorsque toutes les arêtes qui le composent sont distinctes ;
  • Un chemin est fermé si ses extrémités sont un même sommet ;
  • Un chemin simple et fermé est un cycle.
  • Pour un graphe non-orienté : un graphe est connexe lorsque tous ses sommets peuvent être reliés par un chemin ;
    Pour un graphe orienté : un graphe est fortement connexe lorsque tous ses sommets peuvent être reliés par un chemin (qui est orienté) ;
    La composante (fortement) connexe d'un sommet est le plus grand sous-graphe (fortement) connexe qui contient ce sommet ; si un graphe est non (fortement) connexe, il peut être séparé en un nombre fini de composantes (fortement) connexes.

Dans un graphe connexe :

  • La distance entre deux sommets est la longueur minimale d'un chemin joignant ces sommets (OU BIEN : la somme du poids des arêtes constituant ce chemin pour un graphe pondéré). La plus grande distance entre deux sommets est le diamètre du graphe ;
  • L'excentricité (ou écartement) d'un sommet est la distance maximale entre ce sommet et tous les sommets du graphe.
  • Les centres d'un graphe sont les sommets qui possèdent l'excentricité minimale de tous les sommets du graphe. On nomme alors cette excentricité minimale le rayon du graphe ; pour les graphes, le diamètre n'est pas toujours le double du rayon.

1 - Ce graphe est-il complet ? Que suffirait-il de faire pour le rendre complet ?
Ce graphe n'est pas complet : A et C ne sont pas reliés directement. Si on ajoute l'arête [AC], le graphe sera complet.

2 - Les arêtes repérées en rouge forment-elles un cycle ? Pourquoi ?
Oui : un cycle est un chemin simple et fermé ; ici : ABCDEA est un cycle.

3 - Ce graphe est-il connexe ? En ajoutant seulement un sommet, est-il possible de le rendre non-connexe ? De combien de composantes connexes sera-t-il alors constitué ?
Tous les sommets sont reliés directement par un arc sauf A et C, mais A et C sont joignables par un chemin (passant par E par exemple) ; donc ce graphe est bien connexe. En ajoutant un seul sommet non relié aux autres, le graphe n'est plus connexe. Il sera constitué de deux composantes connexes : le graphe de départ (qui était connexe) et le sommet isolé qui a été ajouté.
Question 1/8 : ✓
1 min Chap. 3 : Graphes, structure de donnée relationnelle / 1 - Définitions Mémorisation 0x Réussite 0/0

Les outils de représentation

La liste d'adjacence

Pour un graphe donné, on associe à chaque sommet la liste de ses voisins (sommets adjacents). Dans le cas d'un graphe orienté, on peut aussi parler de «liste de successeurs» (flèches partant du sommet considéré) ; dans le cas orienté, on peut aussi considérer la «liste de prédécesseurs» (flèches arrivant au sommet considéré).
Lorsque le graphe est valué, on associe à chaque sommet une liste de tuples (voisin, dictionnaire), où les clés du dictionnaire (poids, couleur) permettent d'accéder à la/les donnée(s) figurant sur l'arête. Si on utilise une seule donnée, le dictionnaire n'est pas nécessaire : on le remplace dans le tuple directement par cette seule donnée.

Exemples :
GN : non-orienté 
{A:[B,D,E],
 B:[A,E],
 C:[D,E],
 D:[A,C],
 E:[A,B,C]}
GO : orienté 
{A:[B,E],
 B:[E],
 C:[D,E],
 D:[A],
 E:[]}
GW : orienté et pondéré 
{A:[(B,1), (E,2)],
 B:[(E,2)],
 C:[(D,1), (E,3)],
 D:[(A,3)],
 E:[]}
Question 1/4 : ✓
Chap. 3 : Graphes, structure de donnée relationnelle / 2 - Représentations Mémorisation 0x Réussite 0/0/9
Quelle est la bonne liste d'adjacence de ce graphe ?
Cocher la bonne réponse.

La matrice d'adjacence

La matrice d'adjacence est un tableau carré (à double entrée). Les lignes et les colonnes correspondent aux sommets (ordonnés dans l'ordre alphanumérique si rien n'est précisé).
Si le sommet X et adjacent à Y (X-->Y), on remplit dans la matrice, à l'intersection de la ligne de X et de la colonne de Y, un 1 (ou un V pour «vrai»), ou bien une donnée si le graphe est valué (il y aura alors une matrice d'adjacence selon chaque type de donnée). S'il n'y a pas de relation entre X et Y, on note un 0 (ou un F pour «faux»).
Lorsque le graphe n'est pas orienté, la matrice d'adjacence est symétrique par rapport à sa diagonale (diagonale principale : de en haut à gauche à en bas à droite) ; aussi, les boucles apparaissent sur la diagonale.

Exemples :
GN : non-orienté 
[ [0, 1, 0, 1, 1],
  [1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [1, 0, 1, 0, 0],
  [1, 1, 1, 0, 0] ]
GO : orienté 
[ [0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0] ]
GW : orienté et pondéré 
[ [0, 1, 0, 0, 2],
  [0, 0, 0, 0, 2],
  [0, 0, 0, 1, 3],
  [3, 0, 0, 0, 0],
  [0, 0, 0, 0, 0] ]
Voici la matrice d'adjacence d'un graphe H : 
[ [0, 1, 0, 1, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0],
  [1, 0, 0, 1, 0, 0, 0],
  [0, 1, 0, 0, 0, 1, 0],
  [0, 0, 0, 0, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1] ]

1 - Le graphe H est-il orienté ?
H est orienté car la matrice d'adjacence n'est pas symétrique.

2 - Donner une représentation graphique de H.
Une représentation graphique de H :

3 - Donner sa liste d'adjacence (de successeurs). 
{A:[B,D],
 B:[C],
 C:[D],
 D:[A,D],
 E:[B,F],
 F:[G],
 G:[E,G]}

4 - Donner sa liste de prédécesseurs. 
{A:[D],
 B:[A,E],
 C:[B],
 D:[A,C,D],
 E:[G],
 F:[E],
 G:[F,G]}

5 - Ce graphe est-il fortement connexe ? Sinon déterminer ses composantes fortement connexes.
H n'est pas fortement connexe : par exemple, en partant de A, on ne peut pas rejoindre G.
u=ABCD et v=EFG sont deux cycles : ils sont donc chacun dans deux composantes fortement connexes ; il n'y en a pas d'autres car u et v recouvrent tous les sommets ; comme les sommets de v ne sont pas accessibles en partant de ceux de u, les 2 composantes connexes sont exactement u et v.
Remarque : un cycle est toujours dans une composante fortement connexe, mais une composante fortement connexe peut contenir plusieurs cycles «élémentaires» (élémentaire : sans repasser par un même sommet, sauf au départ et à l'arrivée, évidemment) ; par exemple A<-->B<-->C : 2 cycles élémentaire AB et BC, mais une seule composante fortement connexe.
Il est possible de faire le graphe des composantes fortement connexes de H : v-->u ; ce graphe sera toujours acyclique (sans cycle).

En reprenant ce même graphe, mais en le rendant non-orienté H' (remplacer les flèches par des arcs simples) :
6 - Le graphe obtenu est-il connexe ?
Oui

7 - Le graphe obtenu est-il complet ?
Non

8 - Quel est son le diamètre ?
4

9 - Quels sont ses centres ?
Il n'y a qu'un centre : B.

10 - Quel est son rayon ?
2
Question 1/6 : ✓
30s Chap. 3 : Graphes, structure de donnée relationnelle / 2 - Représentations Mémorisation 0x Réussite 0/0/5

Le type abstrait graphe et son implémentation

Le type abstrait de données : Graphe

On considère ici les graphes orientés ou non et pondérés (en première approche).
  • creer_graphe construit un graphe vide, non-orienté par défaut et orienté si le booléen ori est vrai.
  • est_oriente : renvoie vrai lorsque le graphe est orienté.
  • ajouter_sommet : ajoute un sommet s au graphe G.
  • sommet_existe : renvoie vrai lorsque le sommet s est dans G.
  • ajouter_arc : ajoute un arc de poids w entre les sommets sa et sd au graphe G. (Pour un graphe non-pondéré, w peut valoir par défaut 1.)
    Dans le cas d'un graphe non-orienté, ajoute deux arcs de poids w : sd → sa et sa → sd.
  • arc_existe : renvoie vrai lorsque l'arc entre sa et sd est dans G.
  • supprimer_sommet : enlève un sommet s de G et supprime aussi ses arcs incidents.
  • supprimer_arc : enlève les arcs entre les sommets sa et sd.
Graphe
creer_graphe(ori) : vide
est_oriente(G) : booléen
ajouter_sommet(G, s) [sommet pas encore dans G] : vide
sommet_existe(G, s) : booléen
ajouter_arc(G, sd, sa, w) [sa et sd sont dans G, l'arc pas encore] : vide
arc_existe(G, sd, sa) : booléen
supprimer_sommet(G, s) [s est dans G] : vide
supprimer_arc(G, sd, sa) [sa et sd sont dans G] : vide

Implémentation


1 - Implémenter en Python POO le type abstrait de données : Graphe, d'après le spécifications précédentes.
class Graphe : def __init__(self, ori=False) : self.sommets = [] self.arcs = [] self._ori = ori def est_oriente(self) : return self._ori def sommet_existe(self, s) : return s in self.sommets def arc_existe(self, sd, sa) : trouve = False for a in self.arcs : if a[0] == sd and a[1] == sa : trouve = True return trouve def ajouter_sommet(self, s) : if not self.sommet_existe(s) : self.sommets.append(s) print(s, " ajouté") else : print(s, " est déjà présent") def ajouter_arc(self, sd, sa, poids=1) : if self.sommet_existe(sd) and self.sommet_existe(sa) and not self.arc_existe(sd, sa) : self.arcs.append((sd, sa, poids)) if not self._ori : # arc inverse si graphe non-orienté self.arcs.append((sa, sd, poids)) print((sa, sd, poids), " ajouté") else : print((sa, sd, poids), " incorrect ou déjà présent") def supprimer_sommet(self, s) : if self.sommet_existe(s) : self.sommets.remove(s) aeffacer = [] for a in self.arcs: if a[0] == s or a[1] == s: aeffacer.append(a) while aeffacer : a = aeffacer.pop() self.arcs.remove(a) print(a, " retiré") print(s, " retiré") else : print(s, "n'est pas présent") def supprimer_arc(self, sd, sa) : aeffacer = [] for a in self.arcs : if sd == a[0] and sa == a[1] : aeffacer.append(a) if not self._ori and sd == a[1] and sa == a[0] : aeffacer.append(a) while aeffacer : a = aeffacer.pop() self.arcs.remove(a) print(a, " retiré") else : print(a, "n'est pas présent") # ------------------------------------------------------------------------------ # Création d'un graphe orienté (True) ou non (False ou rien) G = Graphe() print("G est orienté ? : ", G.est_oriente()) # Création des sommets for s in "ABCDEF": G.ajouter_sommet(s) # Création des arcs au hasard : from random import choice, randrange for _ in range(10) : G.ajouter_arc(choice(G.sommets), choice(G.sommets), randrange(1,3)) # Affichage print("\nSOMMETS : \n", G.sommets) print("\nARCS : ") print("SUPPRIMER SOMMET : ") G.supprimer_sommet("A") print("\nARCS : ") for line in G.arcs : print(line)

2 - Ajouter à cette classe une méthode voisins(G, s) qui retourne la liste des voisins du sommet s dans G.
def voisins(self, s): """Listes des voisins.""" voisins = [] if self.sommet_existe(s) : for a in self.arcs : if a[0] == s : voisins.append(a[1]) return voisins

3 - Ajouter à cette classe une méthode voisins_poids(G, s) qui retourne une liste de tuples (v, p) avec les voisins d'un sommet s et le poids de l'arête.
def voisins_poids(self, s): """Listes des voisins avec leur poids respectifs.""" voisins = [] if self.sommet_existe(s) : for a in self.arcs : if a[0] == s : voisins.append((a[1],a[2])) return voisins

4 - Ajouter à cette classe deux méthodes liste_adj qui retourne la liste d'adjacence et matrice_adj qui retourne la matrice d'adjacence du graphe.
def liste_adj(self) : ls = [] for s in self.sommets : ls.append((s, self.voisins(s))) return ls def liste_adj_poids(self) : ls = [] for s in self.sommets : ls.append((s, self.voisins_poids(s))) return ls def matrice_adj(self) : taille = len(self.sommets) mat = [[0 for _ in range(taille)] for _ in range(taille)] for arc in self.arcs : mat[self.sommets.index(arc[0])][self.sommets.index(arc[1])] = mat[self.sommets.index(arc[0])][self.sommets.index(arc[1])] + arc[2] return mat

Algorithmes de parcours des graphes

Wikipédia est une bonne ressource dans ce domaine :

Algorithme de parcours en largeur (BFS)

L'algorithme de parcours en largeur (ou BFS, pour Breadth First Search en anglais) permet le parcours d'un graphe ou d'un arbre de la manière suivante : on commence par explorer un nœud source, puis ses successeurs, puis les successeurs non-explorés des successeurs, etc. L'algorithme de parcours en largeur permet de calculer les distances de tous les nœuds depuis un nœud source dans un graphe non-pondéré (orienté ou non-orienté). Il peut aussi servir à déterminer si un graphe non-orienté est connexe.

Principe : Cet algorithme diffère de l'algorithme de parcours en profondeur par le fait que, à partir d'un nœud source S, il liste d'abord les voisins de S pour ensuite les explorer un par un. Ce mode de fonctionnement utilise donc une file dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés.
Les nœuds déjà visités sont marqués afin d'éviter qu'un même nœud soit exploré plusieurs fois. Dans le cas particulier d'un arbre, le marquage n'est pas nécessaire.
Étapes de l'algorithme :
  1. Mettre le nœud source dans la file.
  2. Retirer le nœud du début de la file pour le traiter.
  3. Mettre tous les voisins non-explorés dans la file (à la fin).
  4. Si la file n'est pas vide reprendre à l'étape 2.
Remarque : L'utilisation d'une pile au lieu d'une file transforme l'algorithme du parcours en largeur en l'algorithme de parcours en profondeur.

Pseudo code : L'algorithme s'implémente à l'aide d'une file.

ParcoursLargeur(Graphe G, Sommet s)
    f = CreerFile()
    f.enfiler(s)
    marquer(s)
    tant que la file est non-vide
        s = f.defiler()
        afficher(s)
        pour tout voisin t de s dans G
            si t non-marqué
                f.enfiler(t)
                marquer(t)

Complexité : La complexité en temps dans le pire cas est en `O( | S | + | A | )` où `| S |` est le nombre de sommets et `| A |` est le nombre d'arcs. En effet, chaque arc et chaque sommet est visité au plus une seule fois.

Implémenter cet algorithme en Python en complétant la classe Graphe déjà construite.
def bfs(self, sd) : vus = [] laFile = [sd] while laFile : s = laFile.pop(0) if s not in vus : vus.append(s) laFile.extend(self.voisins(s)) return vus

Algorithme de parcours en profondeur (DFS)

L'algorithme de parcours en profondeur (ou DFS, pour Depth-First Search) correspond à la méthode intuitive qu'on utilise pour trouver la sortie d'un labyrinthe sans tourner en rond.
Principe :

L'exploration d'un parcours en profondeur depuis un sommet S fonctionne comme suit : on suit un chemin dans le graphe jusqu'à un cul-de-sac ou alors jusqu'à atteindre un sommet déjà visité. On revient alors sur le dernier sommet où on pouvait suivre un autre chemin puis on explore un autre chemin. L'exploration s'arrête quand tous les sommets depuis S ont été visités. Bref, l'exploration progresse à partir d'un sommet S en s'appelant récursivement pour chaque sommet voisin de S.
Le nom d'algorithme en profondeur est dû au fait que, contrairement à l'algorithme de parcours en largeur, il explore en fait « à fond » les chemins un par un : pour chaque sommet, il marque le sommet actuel, et il prend le premier sommet voisin jusqu'à ce qu'un sommet n'ait plus de voisins (ou que tous ses voisins soient marqués), et revient alors au sommet père.
Si G n'était pas un arbre, l'algorithme pourrait a priori tourner indéfiniment si on continuait l'exploration depuis un sommet déjà visité. Pour éviter cela, on marque les sommets que l'on visite, de façon à ne pas les explorer à nouveau. Dans le cas d'un arbre, le parcours en profondeur est utilisé pour caractériser l'arbre.

Pseudo code : Durant l'exploration, on marque les sommets afin d'éviter de re-parcourir des sommets parcourus. Initialement, aucun sommet n'est marqué. 
explorer(graphe G, sommet s)
    marquer le sommet s
    afficher(s)
    pour tout sommet t voisin du sommet s
        si t n'est pas marqué alors
              explorer(G, t);
                   
parcoursProfondeur(graphe G, sommet s)
    pour tout sommet du graphe G en partant du sommet s
        si s n'est pas marqué alors
              explorer(G, s)
Implémenter cet algorithme en Python en complétant la classe Graphe déjà construite.
def dfs(self, sd) : vus = [] laPile = [sd] while laPile : s = laPile.pop() if s not in vus : vus.append(s) laPile.extend(self.voisins(s)) return vus
Complexité : La complexité en temps dans le pire cas est en `O( | S | + | A | )` où `| S |` est le nombre de sommets et `| A |` est le nombre d'arcs.
Liste de composantes connexes
En première approche, on ne considèrera que des graphes non-orientés.
En démarrant DFS sur chaque sommet du graphe, il est possible d'obtenir une liste des composantes connexes de ce graphe. On pourra utiliser le type set pour désigner une composante connexe.
Implémenter cet algorithme en Python en complétant la classe Graphe déjà construite. Chaque composante sera représentée par la liste de ses sommets.
def composantes_connexes(self) : ls = [] for s in self.sommets : comp = set(self.dfs(s)) if comp not in ls : ls.append(comp) return ls

La recherche de cycles dans un graphe

La recherche de cycles dans un graphe permet de traiter un grand nombre de problèmes dont par exemple :
  • La recherche d'un cycle eulérien dans un graphe, c'est-à-dire un cycle qui permet de parcourir tout les sommets du graphe, en bref un circuit touristique : cf problème des sept ponts de Königsberg.
  • Dans une langue donnée : chaque mot de la langue est représenté par un sommet ; pour chaque sommet représentant un mot M, on trace des flèches reliant le sommet M aux sommets qui représentent les mots apparaîssant dans la définition de M dans un dictionnaire fixé. Le graphe obtenu contient-il des cycles ? Comment interpréter cela ? Cela dépend-il fortement du dictionnaire utilisé ? Est-ce que ces cycles apparaîssent dans toutes les langues ?
  • ...etc...
Implémenter cet algorithme en python en complétant la classe déjà construite.
Conseils :
  • s'appuyer sur DFS ;
  • les cycles ABCA et BCAB sont-ils les mêmes ?
def recherche_cycles(self, **arguments) : # ??? à faire

Algorithmes du plus cours chemin

Ces algorithmes sont utilisés pour traiter des problèmes d'optimisation (transports, câblage électrique ou réseau, déplacements de pnj dans un jeu vidéo, ...).

Illustration de ces algorithmes sur une carte réelle avec : Pathfinding.

L'algorithme de Dijkstra

graphe_dijkstra.png
  1. Après avoir regardé le vidéo de [RévisionsBac.com], réappliquer l'algorithme de Dijkstra à partir du sommet A.
    A ; B ; C ; D ; E ; F ; G A,0 ; - ; - ; - ; - ; - ; - ; A,2 ; A,1 ; - ; - ; - ; - ; A,2; ; C,5 ; C,4 ; C,6 ; - ; ; ; B,3 ; C,4 ; C,6 ; - ; ; ; ; C,4 ; C,6 ; D,8 ; ; ; ; ; E,5 ; D,8 ; ; ; ; ; ; F,7
  2. Représenter l'arbre couvrant des plus courts chemins en partant de A.
    graphe_dijkstra_arbre_couvrant_A.png
  3. Appliquer l'algorithme de Dijkstra à partir du sommet C.
    A ; B ; C ; D ; E ; F ; G - ; - ;C,0; - ; - ; - ; - C,1; C,2 ; ; C,4 ; C,3 ; C,5 ; - ; C,2 ; ; C,4 ; C,3 ; C,5 ; - ; ; ;B,3; C,3 ; C,5 ; - ; ; ; ; C,3; C,5 ; D,9 ; ; ; ; ;E,4;D,9 ; ; ; ; ; ;F,6
  4. Représenter l'arbre couvrant des plus courts chemins en partant de C.
    graphe_dijkstra_arbre_couvrant_C.png
Implémenter en python l'algorithme de Dijkstra en complétant la classe Graph déjà construite. Conseils : Définir deux fonctions :
  • def dijkstra(self, sd): Pour créer le tableau de l' arbre couvrant (arbre qui recouvre tous les sommets d'un graphe) issu du sommet de départ
  • def chemin_dijkstra(self, sd, sa): Pour extraire le plus court chemin de ce tableau.
Dans la première fonction, créer trois variables pour stocker :
  • le tableau de l'arbre couvrant, des plus courts chemins,
  • la liste des sommets résolus pour ne pas y repasser,
  • le sommet courant à partir duquel on explore l'arbre et sa distance au sommet de départ.
def dijkstra(self, sd): pcc = {sd:(sd,0)} # Plus courts chemins vus = [sd] # Sommets finis s_min, d_min = (sd, 0) # Sommet courant le plus proche while True: for v, d in self.voisins_poids(s_min): if not v in vus: d_tot = d_min + d if not v in pcc or d_tot < pcc[v][1]: pcc[v] = (s_min, d_tot) # Choisi le sommet le plus proche du sd a_exp = [(s,c[1]) for s,c in pcc.items() if not s in vus] if a_exp : s_min, d_min = min(a_exp, key=lambda x: x[1]) vus.append(s_min) else : return pcc def chemin_dijkstra(self, sd, sa): pcc = self.dijkstra(sd) # Plus courts chemins chemin = [sa] d = pcc[sa][1] while sa != sd: sa = pcc[sa][0] chemin.insert(0, sa) return chemin, d

L'algorithme A* (A star)

Le principe doit être vu à titre culturel et peut être travaillé comme approfondissement.

On pourra à ce titre consulter l'article : A*.

L'algorithme A* est performant et très courant mais il nécessite que les nœuds soient étiquetés avec leurs coordonnées, ce qui lui permet d'aller plus directement d'un point A à un point B contrairement à l'algorithme de Dijkstra qui doit explorer le graphe sans savoir vers où se trouve l'arrivée.

La bibliothèque networkx (hors-BAC)

Cette bibliothèque permet une gestion avancée des graphes. Pour l'importer : import networkx as nx (nx est souvent l'abréviation consacrée).
Lorsque l'import renvoie une erreur, il faut l'installer, entrer dans un shell : pip install networkx ou bien pip3 install networkx.
La classe Graphe que nous avons implémentée est petite en regard des 4 classes de graphes (Graph, DiGraph, MultiGraph, MultiDiGraph) utilisés par networkx. Dans un premier temps, on peut remarquer que créer une arête crée aussi les sommets mentionnés, même s'ils ne sont pas présents dans le graphe.
#!/usr/bin/env python # -*- coding: utf-8 -*- import matplotlib.pyplot as plt # pour les dessins import networkx as nx # Créer un objet graphe (Graph) G = nx.Graph() # G = nx.DiGraph() # pour les graphes orientés # G = nx.MultiGraph() # avec arêtes parallèles # G = nx.MultiDiGraph() # avec arêtes parallèles orientées # Ajouter un sommet / une arête (tout objet hashable sauf None) : G.add_node("A") G.add_edge("A", "B") # le sommet "B" est ajouté directement # Ajouter depuis un conteneur plusieurs sommets/arêtes (ici : list, aussi : dict, set, Graph, fichier, ...) G.add_nodes_from(["B", "C", "D"]) G.add_edges_from([("B", "C"), ("C", "D"), ("A", "C"), ("E","E")]) # On peut ajouter des étiquettes { : } sur les arêtes : # (début, fin, {clé : valeur} ) G.add_edges_from([("A", "E", {"info": 7}), ("B", "E", {"info": 8})]) print("sommets : \n", G.nodes()) print("triés : \n", sorted(G.nodes(), key=str)) print("nombre de sommets : \n",G.number_of_nodes()) print("arêtes : \n", G.edges(data=True)) print("nombre d'arêtes : \n", G.number_of_edges()) print("plus court chemin : \n", nx.shortest_path(G, "A", "D")) print("distance : \n", nx.shortest_path_length(G, "A", "D")) print("Diamètre : \n", nx.diameter(G)) print("Rayon : \n", nx.radius(G)) print("Centre : \n", nx.center(G)) print("accès à une étiquette : \n", G["A"]["E"]["info"]) # G[u][v]['width'] est identique à G.edges[u, v]['width'] # print("vue selon les étiquettes : \n", [G.edges.data("info")]) # print("liste des voisins d'un sommet : \n",[item for item in G.neighbors("E")]) # --- LISTE ET MATRICE D'ADJACENCE --- # print("liste d'adjacence : \n",[item for item in G.adjacency()]) MatAdjG = nx.adjacency_matrix(G) MatAdjG.setdiag(MatAdjG.diagonal()*2) # def : boucles comptent 2 print("matrice d'adjacence : \n", MatAdjG.todense())
Voici une figure du cours construite en utilisant conjointement et networkx et matplotlib :
#!/usr/bin/env python # -*- coding: utf-8 -*- import networkx as nx # (graphes) # import numpy as np # (matrices) import matplotlib.pyplot as plt # (figures) # CONSTRUCTION DU GRAPHE : on donne directement les arêtes # (on peut les donner en les regroupant par poids) : #G = nx.Graph() G = nx.DiGraph() G.add_edges_from([('A', 'B'),('C','D')],weight=1) G.add_edges_from([('A','E'),('B','E')],weight=2) G.add_edges_from([('C','E'),('D','A')],weight=3) # --- LISTE ET MATRICE D'ADJACENCE --- print("liste d'adjacence : \n",[item for item in G.adjacency()]) MatAdjG = nx.adjacency_matrix(G) MatAdjG.setdiag(MatAdjG.diagonal()*2) # def : boucles comptent 2 print("matrice d'adjacence : \n",MatAdjG.todense()) # --- DESSIN --- # fixe la position pour les étapes de dessin : pos = nx.spring_layout(G) # dessiner les étiquettes AVANT le graphe : edge_labels=dict([((u,v,),d["weight"]) for u,v,d in G.edges(data=True)]) options = { "edge_labels" : edge_labels } nx.draw_networkx_edge_labels(G, pos, **options) # mise en valeur de certaines arêtes (en rouge) : red_edges = [] edge_colors = ["black" if not edge in red_edges else "red" for edge in G.edges()] # dessin : options = { "node_color": "grey", "node_size": 1500, "width": 2, "edge_color" : edge_colors } nx.draw_networkx(G,pos, **options) plt.show()
Produire un graphe de 10 sommets, non-orienté, deux composantes connexes, et pondéré ; une composante connexe sera coloriée en rouge.
#!/usr/bin/env python # -*- coding: utf-8 -*- import networkx as nx # (graphes) import matplotlib.pyplot as plt # (figures) # CONSTRUCTION DU GRAPHE : on donne directement les arêtes # (on peut les donner en les regroupant par poids) : #G = nx.Graph() G = nx.Graph() G.add_edges_from([('A', 'B'),('B','C'),('B','D'),('C','D'),('A','D'),('C','D'),('B','E')],weight=1) G.add_edges_from([('F','G'),('G','H'),('G','I'),('G','J')],weight=2) # --- DESSIN --- # fixe la position pour les étapes de dessin : pos = nx.spring_layout(G) # dessiner les étiquettes AVANT le graphe : edge_labels=dict([((u,v,),d["weight"]) for u,v,d in G.edges(data=True)]) options = { "edge_labels" : edge_labels } nx.draw_networkx_edge_labels(G, pos, **options) # mise en valeur de certaines arêtes (en rouge) : red_edges = [('F','G'),('G','H'),('G','I'),('G','J')] edge_colors = ["black" if not edge in red_edges else "red" for edge in G.edges()] # dessin : options = { "node_color": "grey", "node_size": 500, "width": 5, "edge_color" : edge_colors } nx.draw_networkx(G,pos, **options) plt.show()
En anglais :
  • algorithme de parcours en profondeur : Depth-First Search (DFS) ;
  • algorithme de parcours en largeur : Breadth First Search (BFS) ;
  • Noeud : node ;
  • Arête : edge ;
  • Chemin : path ;
  • graphe représentant un réseau : network.