Cours NSI Terminale - Thème 5.
Nous comencerons par introduire la classe Graphe que nous allons compléter au fur à mesure de ce TP.
Elle reprend un certain nombre de notions vues lors de la découverte des graphes dans la partie Structures de données.
Un graphe y est représenté en interne par un dictionnaire d'adjacence :
Les données sont stockées dans la propriété privée __noeud
de type dictionnaire. On y accède pas directement. L'accès se fait par les méthodes (accesseurs) comme sommets()
ou voisins()
La méthode show()
permet de visualiser graphiquement le graphe à l'aide du module graphviz. On ne cherchera pas à entrer dans les détails de cette méthode mais vous pouvez tenter de l'analyser, son fonctionnement est assez basique.
from graphviz import Digraph
class Graphe():
"""Graphe implémenté à l'aide d'un dictionnaire
Exemple :
{'A': [('M', 65), ('R', 90), ('T', 80)],
'G': [('L', 70)],
'L': [('G', 70), ('P', 230), ('T', 260)],
'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)],
'P': [('L', 230), ('M', 95), ('T', 130)],
'R': [('A', 90), ('M', 90)],
'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]}
"""
def __init__(self, noeuds = None):
"""Initialisation avec un graphe vide
__noeuds est un dictionnaire
- clé = Valeur du noeud (chaine, entier)
- valeur = liste d'aretes (clé, poids)"""
if noeuds is None:
self.__noeuds = dict()
else:
self.__noeuds = noeuds
def importe_matrice(self, matrice, noms):
"""Importe une matrice d'adjacence"""
longueur = len(matrice)
for i in range(longueur):
self.__noeuds[noms[i]] = []
for j in range(longueur):
if matrice[i][j] != 0:
self.__noeuds[noms[i]].append((noms[j], matrice[i][j]))
def ajouter_noeud(self, nd):
"""Ajoute un nouveau noeud au graphe"""
if not nd in self.__noeuds:
self.__noeuds[nd] = []
def ajouter_arete(self, nd1, nd2, poids=1):
"""Ajoute une arête au graphe
si poids n'est pas renseigné, il prendra la valeur 1"""
# On s'assure que les arètes existent
self.ajouter_noeud(nd1)
self.ajouter_noeud(nd2)
# On crée la connexion nd1 -> nd2
self.__noeuds[nd1].append((nd2, poids))
def liste_noeuds(self):
"""Renvoie la liste des noeuds"""
nds = list(self.__noeuds.keys())
nds.sort()
return nds
def voisins(self, nd):
"""Renvoie la liste des noeuds voisins de nd"""
if nd in self.liste_noeuds():
return [a[0] for a in self.__noeuds[nd]]
else:
return []
def arete(self,nd1, nd2):
"""Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête"""
if nd2 not in self.voisins(nd1):
return 0
for a in self.__noeuds[nd1]:
if a[0] == nd2:
return a[1]
def show(self):
"""Représentation graphique avec graphviz"""
dot = Digraph(comment="Graphe", format='svg')
for nd in self.liste_noeuds():
dot.node(nd,nd)
for a in self.__noeuds[nd]:
# Teste si l'arête est orientée
if self.arete(a[0], nd) == self.arete(nd, a[0]) :
# dessin d'une arête non orientée
if a[0]< nd:
# On ne dessine qu'une seule arête sur les 2
if a[1] != 1:
dot.edge(nd, a[0],label=str(a[1]), dir="none")
else:
dot.edge(nd, a[0], dir="none")
else:
# dessin d'une arête orientée
if a[1] != 1:
dot.edge(nd, a[0],label=str(a[1]))
else:
dot.edge(nd, a[0])
return dot
En utilisant la commande help()
vous aurez un résumé des méthodes à votre disposition
dans cette classe.
help(Graphe)
Pour commencer, voici quelques exemples de graphes. N'hésitez pas à essayer sur ces exemples les méthodes offertes par la classe Graphe afin de bien vous en imprégner.
# Premier exemple
gr1=Graphe()
gr1.ajouter_arete("A", "B")
gr1.ajouter_arete("C", "A")
gr1.ajouter_arete("C", "B")
gr1.show()
# testez ici les méthodes sur gr1
# Deuxième exemple : le graphe du cours
matrice = [[0,1,1,0,0,0,0,0],
[1,0,0,1,1,0,0,0],
[1,0,0,1,0,0,0,0],
[0,1,1,0,1,0,0,0],
[0,1,0,1,0,1,1,0],
[0,0,0,0,1,0,1,0],
[0,0,0,0,1,1,0,1],
[0,0,0,0,0,0,1,0]]
gr2 = Graphe()
gr2.importe_matrice(matrice, ["A", "B", "C", "D", "E", "F", "G", "H"])
gr2.show()
# Testez ici quelques méthodes
Complétez la classe Graphe afin d'ajouter la méthode parcours_profondeur
. Celle-ci est déjà un peu ébauchée, vous devrez compléter le coeur de l'algorithme récursif dans la fonction dfs
.
class Graphe():
"""Graphe implémenté à l'aide d'un dictionnaire
Exemple :
{'A': [('M', 65), ('R', 90), ('T', 80)],
'G': [('L', 70)],
'L': [('G', 70), ('P', 230), ('T', 260)],
'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)],
'P': [('L', 230), ('M', 95), ('T', 130)],
'R': [('A', 90), ('M', 90)],
'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]}
"""
def __init__(self, noeuds = None):
"""Initialisation avec un graphe vide
__noeuds est un dictionnaire
- clé = Valeur du noeud (chaine, entier)
- valeur = liste d'aretes (clé, poids)"""
if noeuds is None:
self.__noeuds = dict()
else:
self.__noeuds = noeuds
def importe_matrice(self, matrice, noms):
"""Importe une matrice d'adjacence"""
longueur = len(matrice)
for i in range(longueur):
self.__noeuds[noms[i]] = []
for j in range(longueur):
if matrice[i][j] != 0:
self.__noeuds[noms[i]].append((noms[j], matrice[i][j]))
def ajouter_noeud(self, nd):
"""Ajoute un nouveau noeud au graphe"""
if not nd in self.__noeuds:
self.__noeuds[nd] = []
def ajouter_arete(self, nd1, nd2, poids=1):
"""Ajoute une arête au graphe
si poids n'est pas renseigné, il prendra la valeur 1"""
# On s'assure que les arètes existent
self.ajouter_noeud(nd1)
self.ajouter_noeud(nd2)
# On crée la connexion nd1 -> nd2
self.__noeuds[nd1].append((nd2, poids))
def liste_noeuds(self):
"""Renvoie la liste des noeuds"""
nds = list(self.__noeuds.keys())
nds.sort()
return nds
def voisins(self, nd):
"""Renvoie la liste des noeuds voisins de nd"""
if nd in self.liste_noeuds():
return [a[0] for a in self.__noeuds[nd]]
else:
return []
def arete(self,nd1, nd2):
"""Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête"""
if nd2 not in self.voisins(nd1):
return 0
for a in self.__noeuds[nd1]:
if a[0] == nd2:
return a[1]
def show(self):
"""Représentation graphique avec graphviz"""
dot = Digraph(comment="Graphe", format='svg')
for nd in self.liste_noeuds():
dot.node(nd,nd)
for a in self.__noeuds[nd]:
# Teste si l'arête est orientée
if self.arete(a[0], nd) == self.arete(nd, a[0]) :
# dessin d'une arête non orientée
if a[0]< nd:
# On ne dessine qu'une seule arête sur les 2
if a[1] != 1:
dot.edge(nd, a[0],label=str(a[1]), dir="none")
else:
dot.edge(nd, a[0], dir="none")
else:
# dessin d'une arête orientée
if a[1] != 1:
dot.edge(nd, a[0],label=str(a[1]))
else:
dot.edge(nd, a[0])
return dot
def parcours_profondeur(self, depart):
"""Parcourt l'arbre en profondeur"""
def dfs(nd):
# YOUR CODE HERE
raise NotImplementedError()
deja_vu = [] # noeuds déjà visités
dfs(depart)
return deja_vu
# Testez votre classe
matrice = [[0,1,1,0,0,0,0,0],
[1,0,0,1,1,0,0,0],
[1,0,0,1,0,0,0,0],
[0,1,1,0,1,0,0,0],
[0,1,0,1,0,1,1,0],
[0,0,0,0,1,0,1,0],
[0,0,0,0,1,1,0,1],
[0,0,0,0,0,0,1,0]]
gr2 = Graphe()
gr2.importe_matrice(matrice, ["A", "B", "C", "D", "E", "F", "G", "H"])
assert set(gr2.parcours_profondeur("A")) == {'A', 'B', 'D', 'C', 'E', 'F', 'G', 'H'}
Complétez la classe Graphe afin d'ajouter la méthode parcours_largeur
. Celle-ci aura le même comportement que la méthode parcours_profondeur
précédente.
class Graphe():
"""Graphe implémenté à l'aide d'un dictionnaire
Exemple :
{'A': [('M', 65), ('R', 90), ('T', 80)],
'G': [('L', 70)],
'L': [('G', 70), ('P', 230), ('T', 260)],
'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)],
'P': [('L', 230), ('M', 95), ('T', 130)],
'R': [('A', 90), ('M', 90)],
'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]}
"""
def __init__(self, noeuds = None):
"""Initialisation avec un graphe vide
__noeuds est un dictionnaire
- clé = Valeur du noeud (chaine, entier)
- valeur = liste d'aretes (clé, poids)"""
if noeuds is None:
self.__noeuds = dict()
else:
self.__noeuds = noeuds
def importe_matrice(self, matrice, noms):
"""Importe une matrice d'adjacence"""
longueur = len(matrice)
for i in range(longueur):
self.__noeuds[noms[i]] = []
for j in range(longueur):
if matrice[i][j] != 0:
self.__noeuds[noms[i]].append((noms[j], matrice[i][j]))
def ajouter_noeud(self, nd):
"""Ajoute un nouveau noeud au graphe"""
if not nd in self.__noeuds:
self.__noeuds[nd] = []
def ajouter_arete(self, nd1, nd2, poids=1):
"""Ajoute une arête au graphe
si poids n'est pas renseigné, il prendra la valeur 1"""
# On s'assure que les arètes existent
self.ajouter_noeud(nd1)
self.ajouter_noeud(nd2)
# On crée la connexion nd1 -> nd2
self.__noeuds[nd1].append((nd2, poids))
def liste_noeuds(self):
"""Renvoie la liste des noeuds"""
nds = list(self.__noeuds.keys())
nds.sort()
return nds
def voisins(self, nd):
"""Renvoie la liste des noeuds voisins de nd"""
if nd in self.liste_noeuds():
return [a[0] for a in self.__noeuds[nd]]
else:
return []
def arete(self,nd1, nd2):
"""Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête"""
if nd2 not in self.voisins(nd1):
return 0
for a in self.__noeuds[nd1]:
if a[0] == nd2:
return a[1]
def show(self):
"""Représentation graphique avec graphviz"""
dot = Digraph(comment="Graphe", format='svg')
for nd in self.liste_noeuds():
dot.node(nd,nd)
for a in self.__noeuds[nd]:
# Teste si l'arête est orientée
if self.arete(a[0], nd) == self.arete(nd, a[0]) :
# dessin d'une arête non orientée
if a[0]< nd:
# On ne dessine qu'une seule arête sur les 2
if a[1] != 1:
dot.edge(nd, a[0],label=str(a[1]), dir="none")
else:
dot.edge(nd, a[0], dir="none")
else:
# dessin d'une arête orientée
if a[1] != 1:
dot.edge(nd, a[0],label=str(a[1]))
else:
dot.edge(nd, a[0])
return dot
# YOUR CODE HERE
raise NotImplementedError()
# Testez votre classe
matrice = [[0,1,1,0,0,0,0,0],
[1,0,0,1,1,0,0,0],
[1,0,0,1,0,0,0,0],
[0,1,1,0,1,0,0,0],
[0,1,0,1,0,1,1,0],
[0,0,0,0,1,0,1,0],
[0,0,0,0,1,1,0,1],
[0,0,0,0,0,0,1,0]]
gr2 = Graphe()
gr2.importe_matrice(matrice, ["A", "B", "C", "D", "E", "F", "G", "H"])
assert set(gr2.parcours_largeur("A")) == {'A', 'B', 'D', 'C', 'E', 'F', 'G', 'H'}
Pour finir ce TP, vous allez implémenter la méthode cycle
qui ne prend aucun paramètres et qui renvoie un booleen selon que le graphe
contient un cycle ou non.
Vous implémenterez pour cela des parcours en largeur légèrement modifié
class Graphe():
"""Graphe implémenté à l'aide d'un dictionnaire
Exemple :
{'A': [('M', 65), ('R', 90), ('T', 80)],
'G': [('L', 70)],
'L': [('G', 70), ('P', 230), ('T', 260)],
'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)],
'P': [('L', 230), ('M', 95), ('T', 130)],
'R': [('A', 90), ('M', 90)],
'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]}
"""
def __init__(self, noeuds = None):
"""Initialisation avec un graphe vide
__noeuds est un dictionnaire
- clé = Valeur du noeud (chaine, entier)
- valeur = liste d'aretes (clé, poids)"""
if noeuds is None:
self.__noeuds = dict()
else:
self.__noeuds = noeuds
def importe_matrice(self, matrice, noms):
"""Importe une matrice d'adjacence"""
longueur = len(matrice)
for i in range(longueur):
self.__noeuds[noms[i]] = []
for j in range(longueur):
if matrice[i][j] != 0:
self.__noeuds[noms[i]].append((noms[j], matrice[i][j]))
def ajouter_noeud(self, nd):
"""Ajoute un nouveau noeud au graphe"""
if not nd in self.__noeuds:
self.__noeuds[nd] = []
def ajouter_arete(self, nd1, nd2, poids=1):
"""Ajoute une arête au graphe
si poids n'est pas renseigné, il prendra la valeur 1"""
# On s'assure que les arètes existent
self.ajouter_noeud(nd1)
self.ajouter_noeud(nd2)
# On crée la connexion nd1 -> nd2
self.__noeuds[nd1].append((nd2, poids))
def liste_noeuds(self):
"""Renvoie la liste des noeuds"""
nds = list(self.__noeuds.keys())
nds.sort()
return nds
def voisins(self, nd):
"""Renvoie la liste des noeuds voisins de nd"""
if nd in self.liste_noeuds():
return [a[0] for a in self.__noeuds[nd]]
else:
return []
def arete(self,nd1, nd2):
"""Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête"""
if nd2 not in self.voisins(nd1):
return 0
for a in self.__noeuds[nd1]:
if a[0] == nd2:
return a[1]
def show(self):
"""Représentation graphique avec graphviz"""
dot = Digraph(comment="Graphe", format='svg')
for nd in self.liste_noeuds():
dot.node(nd,nd)
for a in self.__noeuds[nd]:
# Teste si l'arête est orientée
if self.arete(a[0], nd) == self.arete(nd, a[0]) :
# dessin d'une arête non orientée
if a[0]< nd:
# On ne dessine qu'une seule arête sur les 2
if a[1] != 1:
dot.edge(nd, a[0],label=str(a[1]), dir="none")
else:
dot.edge(nd, a[0], dir="none")
else:
# dessin d'une arête orientée
if a[1] != 1:
dot.edge(nd, a[0],label=str(a[1]))
else:
dot.edge(nd, a[0])
return dot
# YOUR CODE HERE
raise NotImplementedError()
# Testez votre classe
matrice = [[0,1,1,0,0,0,0,0],
[1,0,0,1,1,0,0,0],
[1,0,0,1,0,0,0,0],
[0,1,1,0,1,0,0,0],
[0,1,0,1,0,1,1,0],
[0,0,0,0,1,0,1,0],
[0,0,0,0,1,1,0,1],
[0,0,0,0,0,0,1,0]]
gr2 = Graphe()
gr2.importe_matrice(matrice, ["A", "B", "C", "D", "E", "F", "G", "H"])
assert gr2.cycle()