Graphe — définition ?
Ensemble de sommets reliés par des arêtes.
Graphe orienté — rôle ?
Les arêtes ont une direction spécifique.
Graphe non orienté — rôle ?
Les arêtes relient deux sommets sans direction.
Voisinage — définition ?
Sommets directement reliés à un sommet.
Degré — rôle ?
Nombre d'arêtes incidentes à un sommet.
Chemin — définition ?
Suite de sommets reliés par des arêtes.
Cycle — rôle ?
Chemin fermé sans répéter de sommet.
Distance — définition ?
Longueur du plus court chemin entre deux sommets.
Connexité — rôle ?
Graphe où chaque sommet est accessible depuis un autre.
Représentation Python — matrices ?
Tableau 2D indiquant présence d'arêtes.
Représentation Python — listes d'adjacence ?
Liste de listes de voisins pour chaque sommet.
Dictionnaire — rôle ?
Modélise graphes avec libellés et voisins.
Liste d'arêtes — avantage ?
Facile pour certains algorithmes comme Bellman-Ford.
Parcours de graphe — principe ?
Explorer tous les sommets selon un ordre.
BFS — mécanisme ?
Utilise une file pour explorer par niveaux.
DFS — mécanisme ?
Utilise une pile pour explorer en profondeur.
Test your knowledge with 8 questions on Introduction aux graphes et parcours efficaces.
1. Comment peut-on utiliser la différence entre un graphe orienté et un graphe non orienté pour modéliser un réseau de transport ?
2. Comment utiliser la notion de distance pour déterminer la proximité entre deux sommets dans un graphe ?
Review the complete course in the revision sheet for Introduction aux graphes et parcours efficaces.
See revision sheet →Import your course and AI generates flashcards in 30 seconds.
Flashcard generator