Graphes
Graphes
- Un graphe est un ensemble de nœuds (aussi appelés sommets) reliés par des arêtes (connexions).
- Les graphes modélisent des réseaux : amis, routes entre villes, liens entre pages web.
- Un arbre est en réalité un graphe particulier ; un graphe général peut avoir des cycles et plusieurs liens par nœud.
Représentation d'un graphe : liste d'adjacence
- Une méthode courante consiste à utiliser une liste d'adjacence : un dictionnaire reliant chaque nœud à sa liste de voisins.
graph["A"]est la liste des nœuds directement connectés àA.- C'est compact lorsque chaque nœud a peu de connexions.
# A graph as a dict: each node maps to its list of neighbours
graph = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A"],
}
print(graph["A"]) # ['B', 'C'] -- A connects to B and C
print(graph["B"]) # ['A']
Ajouter une arête
- Dans un graphe non orienté, une arête
A—Bfonctionne dans les deux sens. - L'ajouter signifie donc ajouter
Bà la liste deAetAà la liste deB. - Si un nœud est nouveau, commencez-le d'abord avec une liste vide.
def add_edge(graph, a, b):
if a not in graph:
graph[a] = []
if b not in graph:
graph[b] = []
graph[a].append(b)
graph[b].append(a)
graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "A", "C")
print(graph) # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
Parcourir les voisins
- Pour explorer à partir d'un nœud, vous lisez sa liste de voisins et visitez chacun d'eux.
- Un nœud qui n'est pas dans le graphe n'a aucun voisin — retournez une liste vide, pas une erreur.
- Cette recherche de voisin est la première étape de tâches plus importantes comme rechercher tout le graphe.
Orienté vs non orienté
- Dans un graphe non orienté, une arête fonctionne dans les deux sens (une amitié).
- Dans un graphe orienté, une arête ne pointe que dans un sens (une rue à sens unique, un lien "suit").
- Pour les arêtes orientées, vous n'ajouteriez que dans un seul sens.
Erreurs courantes
- Un graphe est des nœuds reliés par des arêtes ; une arête peut être unidirectionnelle ou bidirectionnelle.
- Un arbre est un graphe sans cycles — ne pas confondre les deux.
À vous maintenant
- Implémentez les opérations de liste d'adjacence :
add_edge,neighboursetcount_edges. - Chaque tâche vérifie votre fonction sur un petit graphe.
- Appuyez sur Vérifier la réponse pour tester.
Difficulté 5/5 · 400 pièces + un petit bonus lors de la première réussite aujourd'hui
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b à graph[a] et a à graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 5/5 · 400 pièces + un petit bonus lors de la première réussite aujourd'hui
Write neighbours(graph, node) that returns the list of nodes directly connected to node. If node is not in the graph, return an empty list [] (do not raise an error).
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 5/5 · 400 pièces + un petit bonus lors de la première réussite aujourd'hui
Write count_edges(graph) for an undirected graph: count how many edges it has. Add up the lengths of every neighbour list, then divide by 2 (each edge is stored in both nodes' lists). Example: a triangle A–B–C has 3 edges.
Cliquez sur Exécuter pour voir le résultat ici.