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.
Testez vos connaissances avec un QCM de 8 questions sur 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 ?
Révisez le cours complet dans la fiche de révision de Introduction aux graphes et parcours efficaces.
Voir la fiche →Bases de données
Bases de données
Programmation
Programmation
Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards