Qu'est-ce qu'un Graphe ?
Leçon 2 sur 14 du cours Graphes - Série Structures de données n°9 de Coddy.
Un graphe est une structure de données qui modélise un ensemble de choses et les connexions entre elles. Les choses sont appelées sommets (ou nœuds) et les connexions sont appelées arêtes.
Les graphes sont partout. Les réseaux sociaux sont des graphes (les personnes sont des sommets, les amitiés sont des arêtes). Les cartes routières sont des graphes (les intersections sont des sommets, les rues sont des arêtes). Internet, les arbres de dépendances et les cartes de jeux sont tous des graphes.
Dans ce cours, nous nous concentrons sur un graphe non orienté : si une arête connecte u et v, alors v est également connecté à u. Il n'y a pas de direction. Nous utiliserons des entiers comme clés de sommets pour simplifier les choses.
En interne, nous stockerons le graphe sous forme de liste d'adjacence : une map (dictionnaire) reliant chaque sommet à la liste de ses voisins. Cela permet de rechercher les voisins d'un sommet en un seul accès à la map, ce dont la plupart des algorithmes de graphes ont besoin.
Les opérations que nous allons construire sur notre classe Graph sont :
- addVertex : Ajouter un nouveau sommet sans encore d'arêtes.
- addEdge : Connecter deux sommets.
- hasEdge : Vérifier si deux sommets sont connectés.
- getNeighbors : Obtenir la liste des voisins d'un sommet.
- removeEdge : Déconnecter deux sommets.
- size : Compter le nombre de sommets du graphe.
Construisons une classe Graph !
Essayez vous-même
Cette leçon ne comprend pas de défi de code.