Karteikarten: Introduction aux graphes et parcours efficaces — 16 Karten

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.