Lernzettel: Notions clés des graphes et parcours

📋 Plan du Cours

1. Vocabulaire des graphes
2. Dictionnaire d'adjacence
3. Matrice d'adjacence
4. Degré, BFS et DFS
5. Pièges fréquents
6. Questions types au bac

📖 1. Vocabulaire des graphes

🔑 Notions clés & Définitions

• Sommet : Un sommet est un point du graphe représentant une entité (par exemple une ville ou une personne).
• Arête : Une arête est un lien entre deux sommets dans un graphe non orienté, sans notion de direction.
• Arc : Un arc est un lien orienté entre deux sommets, avec une direction dans un graphe orienté.
• Chemin : Un chemin est une suite de sommets reliés successivement par des arêtes (ou arcs, selon le type de graphe).
• Cycle : Un cycle est un chemin qui revient au sommet de départ.

📝 Points essentiels

• Dans un graphe non orienté, le lien A—B implique aussi B—A.
• Dans un graphe orienté, A→B n’entraîne pas B→A.
• Un graphe connexe permet d’aller de n’importe quel sommet à n’importe quel autre.

💡 Astuce mémo

Arête = sans sens, Arc = avec flèche.

📖 2. Dictionnaire d'adjacence

🔑 Notions clés & Définitions

• Dictionnaire d’adjacence : Le dictionnaire d’adjacence représente un graphe en associant à chaque sommet la liste de ses voisins.
• Voisins : Les voisins d’un sommet sont les sommets directement reliés à lui par un lien du graphe.

📝 Points essentiels

• Chaque clé du dictionnaire correspond à un sommet, et chaque valeur est la liste de ses voisins reliés.
• Dans l’exemple non orienté, le degré de A vaut len(g['A']) et correspond au nombre de voisins listés.
• Un sommet isolé doit apparaître dans le dictionnaire, même avec une liste vide comme X : [].

💡 Astuce mémo

Clé = sommet, liste = voisins.

📖 3. Matrice d'adjacence

🔑 Notions clés & Définitions

• Matrice d’adjacence : La matrice d’adjacence est un tableau où l’entrée indique s’il existe un lien entre deux sommets.

📝 Points essentiels

• Dans la matrice d’adjacence de l’exemple, la valeur 1 signifie présence d’un lien et 0 signifie absence de lien.
• L’ordre des sommets (ici A, B, C, D) fixe l’interprétation ligne/colonne pour savoir quels sommets sont reliés.

💡 Astuce mémo

Matrice = grille 1 pour lien, 0 pour rien.

📖 4. Degré, BFS et DFS

🔑 Notions clés & Définitions

• Degré : Le degré d’un sommet est le nombre d’arêtes reliées à ce sommet.
• BFS : Le BFS (parcours en largeur) explore d’abord les voisins au niveau courant avant d’aller plus loin.
• DFS : Le DFS (parcours en profondeur) explore un chemin le plus loin possible avant de revenir.

📝 Points essentiels

• Le degré d’un sommet dans un dictionnaire s’obtient par len(g[s]) et donne le nombre de voisins.
• Le BFS utilise une file et retire avec pop(0) dans l’exemple fourni.
• Le DFS récursif utilise une liste de visites et explore les voisins non encore visités.

💡 Astuce mémo

BFS = file (pop(0)), DFS = profondeur (récursion).

📖 5. Pièges fréquents

🔑 Notions clés & Définitions

• Sommet isolé : Un sommet isolé est un sommet qui n’a aucun voisin, donc sa liste de voisins est vide.

📝 Points essentiels

• Pour un graphe non orienté, si A→B est présent dans le raisonnement, il faut aussi assurer le retour B→A dans la structure du graphe.
• Il faut toujours vérifier qu’un sommet n’a pas déjà été visité avant de l’ajouter à la liste des visites (et à la file si BFS).
• Ne pas confondre les structures : BFS emploie une file alors que DFS emploie une approche de pile via la récursivité ici.

💡 Astuce mémo

Non orienté = aller-retour, sinon les parcours deviennent faux.

📖 6. Questions types au bac

🔑 Notions clés & Définitions

• Connexité par parcours : La connexité se vérifie en lançant un parcours (BFS ou DFS) depuis un sommet et en contrôlant si tous les sommets sont atteints.

📝 Points essentiels

• Pour un degré demandé, on compte les voisins du sommet dans le dictionnaire.
• Pour dessiner depuis le dictionnaire, on relie chaque clé à tous les sommets présents dans sa liste de voisins.
• Pour trouver un chemin de A à D, on suit les arêtes étape par étape en listant les sommets traversés.

💡 Astuce mémo

Bac : degré = compter, connexité = BFS/DFS, dessin = clés vers listes.

⚠️ Pièges & confusions fréquents

1. Dans un graphe non orienté, oublier d’ajouter aussi le lien réciproque (B relié à A) rend le dictionnaire incohérent.
2. Oublier d’inclure un sommet isolé dans le dictionnaire (même avec une liste vide) fausse degré et connexité.
3. Confondre BFS et DFS en utilisant la mauvaise structure (file pop(0) vs approche profondeur) peut changer l’ordre d’exploration.
4. Ajouter un voisin déjà visité sans test préalable provoque des répétitions et peut allonger inutilement le parcours.
5. Croire que “connexe” se déduit sans parcours : il faut lancer BFS/DFS et vérifier qu’on visite tous les sommets.

✅ Checklist Examen

1. Savoir définir et distinguer sommet, arête (non orientée), arc (orientée), chemin et cycle.
2. Savoir calculer le degré d’un sommet avec len(g[s]) sur un dictionnaire d’adjacence.
3. Savoir lire un dictionnaire d’adjacence : chaque clé est un sommet et sa valeur est la liste des voisins.
4. Vérifier qu’un sommet isolé figure bien dans le dictionnaire avec une liste vide.
5. Savoir dire ce qui change entre graphe non orienté et graphe orienté pour les sens A—B vs A→B.
6. Savoir exécuter un BFS en gardant une file (pop(0)) et une liste visites sans revisiter.
7. Savoir exécuter un DFS récursif en ajoutant un sommet dans visites puis en explorant ses voisins non visités.
8. Savoir déterminer si un graphe est connexe en faisant BFS/DFS depuis un sommet et en vérifiant que tous sont visités.
9. Savoir dessiner un graphe à partir du dictionnaire en reliant chaque sommet à sa liste de voisins.
10. Savoir donner un chemin de A à D en listant les sommets traversés étape par étape à partir des liens du graphe.