Intermédiaire
🧠 Fondamentaux
20 XP
0 personnes ont réussi
Representation par liste d'adjacence
Un graphe, c'est un ensemble de points (les noeuds) relies par des lignes (les aretes). Pense a un reseau social : chaque personne est un noeud, et chaque amitie est une arete.
Pour stocker un graphe en Python, la méthode la plus courante est la liste d'adjacence : un dictionnaire ou chaque clé est un noeud, et la valeur est la liste de ses voisins.
Pour un graphe non oriente (l'amitie va dans les deux sens), si A est ami avec B, alors B est aussi ami avec A. Il faut donc ajouter l'arete dans les deux sens.
Écris une classe Graphe avec : __init__() : initialise un dictionnaire vide ajouter_arete(u, v) : ajoute une arete entre u et v (dans les deux sens) voisins(noeud) : retourne la liste des voisins d'un noeud (liste vide si le noeud n'existe pas)
Exemple : g = Graphe() g.ajouter_arete('A', 'B') g.ajouter_arete('A', 'C') g.voisins('A') contient 'B' et 'C'
Tests (2/4)
Voisins simples
g = Graphe()
g.ajouter_arete('A', 'B')
assert 'B' in g.voisins('A')
assert 'A' in g.voisins('B')
class Graphe:
def __init__(self):
self.adjacence = {}
def ajouter_arete(self, u, v):
if u not in self.adjacence:
self.adjacence[u] = []
if v not in self.adjacence:
self.adjacence[v] = []
self.adjacence[u].append(v)
self.adjacence[v].append(u)
def voisins(self, noeud):
return self.adjacence.get(noeud, [])