Graphs · Graphes
Graphs
- A graph is a set of nodes (also called vertices) joined by edges (connections).
- Graphs model networks: friends, roads between cities, links between web pages.
- A tree is really a special graph; a general graph can have cycles and many links per node.
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.
Representing a graph: adjacency list
- One common way is an adjacency list: a dictionary mapping each node to its list of neighbours.
graph["A"]is the list of nodes directly connected toA.- This is compact when each node has only a few connections.
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']
Adding an edge
- In an undirected graph, an edge
A—Bgoes both ways. - So adding it means appending
BtoA's list andAtoB's list. - If a node is new, start it with an empty list first.
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']}
Walking the neighbours
- To explore from a node, you read its neighbour list and visit each one.
- A node that is not in the graph has no neighbours — return an empty list, not an error.
- This neighbour lookup is the first step of bigger jobs like searching the whole graph.
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.
Directed vs undirected
- In an undirected graph an edge works both ways (a friendship).
- In a directed graph an edge points one way only (a one-way street, a "follows" link).
- For directed edges you would append in one direction only.
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.
Common mistakes
- A graph is nodes joined by edges; an edge can be one-way or two-way.
- A tree is a graph with no cycles — do not confuse the two.
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.
Now you try
- Build the adjacency-list operations:
add_edge,neighbours, andcount_edges. - Each task checks your function on a small graph.
- Press Check answer to test it.
À 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.
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b to · à graph[a] and · et a to · à graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place. · Écrivez add_edge(graph, a, b) pour un graphe non orienté stocké comme un dict de listes de voisins. Ajoutez b à graph[a] et a à graph[b]. Si un nœud n'est pas encore dans le graphe, donnez-lui d'abord une liste vide []. Modifiez le dict en place.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
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). · Écrivez neighbours(graph, node) qui retourne la liste des nœuds directement connectés à node. Si node n'est pas dans le graphe, retournez une liste vide [] (ne pas lever d'erreur).
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
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. · Écrivez count_edges(graph) pour un graphe non orienté : comptez combien il a d'arêtes. Additionnez les longueurs de chaque liste de voisins, puis divisez par 2 (chaque arête est stockée dans les listes des deux nœuds). Exemple : un triangle A–B–C a 3 arêtes.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.