Introduction aux graphes et parcours

📋 Plan du Cours

1. Connexité et composantes connexes
2. Parcours des graphes
3. Parcours orienté et successeurs
4. File FIFO
5. Parcours en largeur
6. Plus court chemin
7. Connexité par parcours en largeur
8. Exercice final

📖 1. Connexité et composantes connexes

🔑 Notions clés & Définitions

• Graphe connexe : Un graphe est connexe si, pour toute paire de sommets, il existe une chaîne qui permet de passer de l’un à l’autre.
• Composantes connexes : Des composantes connexes sont des sous-ensembles de sommets dans lesquels la connexité existe, même si le graphe global n’est pas connexe.

📝 Points essentiels

• Un graphe $G=(X,U)$ est connexe ssi il existe une chaîne reliant toute paire de sommets $x$ et $y$.
• Dans un graphe non connexe, on peut regrouper les sommets en composantes connexes formées par des sous-ensembles distincts.
• Pour tester la connexité, on s’appuie sur des parcours qui visent à relier des sommets via des chaînes ou chemins successifs.

📖 2. Parcours des graphes

🔑 Notions clés & Définitions

• Parcours : Un parcours est une méthode systématique qui visite des sommets et suit l’évolution de leur état jusqu’à ce que tous les sommets aient été traités.
• Ordre de prévisite : L’ordre de prévisite est la suite dans laquelle les sommets sont découverts (ouverts) au cours du parcours.
• Ordre de postvisite : L’ordre de postvisite est la suite dans laquelle les sommets sont fermés au cours du parcours.