Profondeur-première recherche: Exploration et analyse

Cette séance de cours couvre l'algorithme DFS (Depth-First Search), qui explore systématiquement chaque bord d'un graphique, à partir de différents sommets. Il introduit le concept de découverte et de temps de finition pour chaque sommet, formant une forêt de profondeur. La séance de cours explique le pseudocode de DFS et analyse la classification des arêtes dans la forêt en profondeur, y compris les arêtes des arbres, des arrières, des avants et des traverses. Il traite également des théorèmes de Parenthèse et de Chemin blanc, fournissant des informations sur les relations entre les sommets lors de l'exploration DFS. Un exemple lié à s'habiller le matin est utilisé pour illustrer les concepts discutés.