Représenter un graphe en Python par un dictionnaire {sommet: [voisins]} et itérer efficacement sur les voisins d'un sommet.
Coder sous forme de dictionnaire le graphe non orienté dont les arêtes sont , , , .
Représenter un graphe en Python par un dictionnaire {sommet: [voisins]} et itérer efficacement sur les voisins d'un sommet.
À chaque sommet on associe la liste de ses voisins ; pour un graphe non orienté, et le coût d'itération sur les voisins de est proportionnel à son degré, sans balayer les sommets.
G en associant à chaque sommet une liste (initialement vide ou directement remplie) de ses voisins.G[s] et, si le graphe est non orienté, à G[t].G[s] ; je peux aussi écrire une fonction voisins(G, s) qui renvoie G[s].Coder sous forme de dictionnaire le graphe non orienté dont les arêtes sont , , , .
G en associant à chaque sommet une liste (initialement vide ou directement remplie) de ses voisins.Je commence avec un dictionnaire vide pour chaque sommet.
G = {'A': [], 'B': [], 'C': [], 'D': []}
G[s] et, si le graphe est non orienté, à G[t].J'ajoute chaque arête dans les deux sens.
aretes = [('A','B'), ('A','C'), ('B','D'), ('C','D')]
for s, t in aretes:
G[s].append(t)
G[t].append(s)
G[s] ; je peux aussi écrire une fonction voisins(G, s) qui renvoie G[s].Le dictionnaire final vaut
G = {'A': ['B','C'], 'B': ['A','D'], 'C': ['A','D'], 'D': ['B','C']}
.
Les applications suivantes et la correction guidée sont réservées aux membres Premium
La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.