Comment représenter et parcourir un graphe en Python ?
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']}
.
Écrire une fonction voisins(G, s) qui renvoie la liste des voisins de , et la tester sur le graphe précédent.
Compter le nombre d'arêtes d'un graphe non orienté codé par dictionnaire de listes.
Coder sous forme de dictionnaire d'adjacence le graphe non orienté à sommets d'arêtes , , , et . Puis écrire une fonction qui renvoie le degré d'un sommet.
Écrire une fonction existe_arete(G, u, v) qui, pour un graphe non orienté codé par dictionnaire d'adjacence, renvoie True si l'arête existe, False sinon. Tester sur le graphe d'arêtes .
Crée ton compte pour accéder à la fiche et aux exercices