Flashcards: Introduction aux graphes et parcours — 12 cartões

Exemples introductifs — réseaux sociaux ?

Graphe avec sommets : individus, arêtes : relations.

Graphe — définition ?

Structure de sommets reliés par des arêtes ou arcs.

Représentation Python — matrice ?

Liste de listes indiquant présence d’arête par True/False.

Représentation Python — dictionnaire ?

Clé : sommet, valeur : liste de successeurs ou voisins.

Parcours largeur — structure ?

Utilise une file d’attente et couleurs (blanc, gris, noir).

Parcours profondeur — structure ?

Utilise une pile pour explorer en profondeur.

Cycle — définition ?

Chemin fermé où le début et la fin sont identiques.

Cycle orienté — caractéristique ?

Cycle où toutes les arêtes suivent le même sens.

Cycle détecté — méthode ?

Trouvé si un successeur gris est rencontré en DFS.

Graphe non orienté — degré ?

Somme des degrés = 2 × nombre d’arêtes.

Sommet — rôle ?

Nœud dans un graphe, représentant un point ou état.

Arête vs Arc — différence ?

Arête : non orientée, arc : orientée.